Исследователи разрабатывают максимально быстрый потоковый алгоритм
Расмус Кинг и его команда разработали сверхбыстрый алгоритм, который, похоже, изменит целую область исследований. Новаторская работа команды Кинга включает в себя так называемый алгоритм сетевого потока, который решает вопрос о том, как достичь максимального потока в сети при одновременном снижении транспортных расходов.
Представьте, что вы пользуетесь европейской транспортной сетью и ищете самый быстрый и дешевый маршрут для перевозки как можно большего количества товаров из Копенгагена в Милан. Алгоритм Кинга может быть применен в таких случаях для расчета оптимального потока трафика с наименьшими затратами для любого вида сети – будь то железнодорожная, автомобильная, водная или Интернет. Его алгоритм выполняет эти вычисления настолько быстро, что может выдать решение в тот самый момент, когда компьютер считывает данные, описывающие сеть.
До появления данной разработки никому не удавалось добиться этого, хотя исследователи работали над этой проблемой около 90 лет. Ранее на вычисление оптимального потока данных уходило значительно больше времени, чем на обработку сетевых данных. И по мере того, как сеть становилась все больше и сложнее, требуемое время вычислений увеличивалось быстрее, чем фактический размер вычислительной задачи. Вот почему мы также сталкиваемся с проблемами потока в сетях, которые слишком велики, чтобы их мог вычислить компьютер.
Подход Кинга устраняет эту проблему: при использовании его алгоритма вычислительное время и размер сети увеличиваются с одинаковой скоростью – это немного похоже на поход и постоянное поддержание одного и того же темпа, каким бы крутым ни был путь.
Исследователи из ETH Zurich разработали, теоретически, самый быстрый из возможных сетевых алгоритмов управления потоками. Два года назад Кинг и его команда представили математическое доказательство своей концепции в новаторской статье. Ученые называют эти новые, почти оптимально быстрые алгоритмы “алгоритмами с почти линейным временем работы”, и сообщество теоретиков-компьютерщиков отреагировало на прорыв Кинга со смесью удивления и энтузиазма.
Научный руководитель Кинга, Дэниел А. Шпильман, профессор прикладной математики и компьютерных наук в Йельском университете, который сам является пионером и авторитетом в этой области, сравнил “абсурдно быстрый” алгоритм с Porsche, обгоняющим конные экипажи. Помимо того, что их статья получила награду за лучшую работу 2022 года на ежегодном симпозиуме IEEE по основам компьютерных наук (FOCS), она также была отмечена в компьютерном журнале Communications of the ACM, а редакторы научно-популярного журнала Quanta назвали алгоритм Кинга одним из десяти крупнейших открытий в области компьютерных наук в 2022 году.
С тех пор исследователи из ETH Zurich усовершенствовали свой подход и разработали новые алгоритмы с почти линейным временем работы. Например, первый алгоритм по-прежнему был ориентирован на фиксированные, статичные сети, соединения в которых являются направленными, что означает, что они функционируют как улицы с односторонним движением в городских дорожных сетях. Алгоритмы, опубликованные в этом году, теперь также способны вычислять оптимальные потоки для сетей, которые постепенно меняются с течением времени. Молниеносные вычисления – важный шаг в решении задач, связанных с очень сложными и богатыми данными сетями, которые динамично и очень быстро меняются.
Саймон Мейерханс, член команды Кинга, представил новый алгоритм с почти линейным временем работы на ежегодном симпозиуме ACM по теории вычислений (STOC) в Ванкувере. Этот алгоритм решает проблему минимальных затрат и максимального потока для сетей, которые постепенно меняются по мере добавления новых подключений. Кроме того, во второй статье, принятой на симпозиуме IEEE по основам компьютерных наук (FOCS) в октябре, исследователи ETH разработали другой алгоритм, который также обрабатывает удаляемые соединения. В частности, эти алгоритмы определяют кратчайшие маршруты в сетях, где добавляются или удаляются соединения.
Но что именно делает подход команды Кинга к вычислениям намного более быстрым, чем любой другой сетевой алгоритм? В принципе, все вычислительные методы сталкиваются с необходимостью анализа сети в нескольких итерациях, чтобы найти оптимальный поток и маршрут с минимальными затратами. При этом они проверяют каждый из различных вариантов того, какие соединения открыты, закрыты или перегружены из-за того, что они достигли предела своей пропускной способности.
До появления разработок Кинга специалисты-компьютерщики, как правило, выбирали между двумя ключевыми стратегиями решения этой проблемы. Одна из них была смоделирована на железнодорожной сети и включала в себя вычисление целого участка сети с измененным потоком трафика на каждой итерации. Вторая стратегия, основанная на потоках электроэнергии в электросети, предусматривала расчет всей сети в каждой итерации, но использовала статистические средние значения для измененного потока в каждом участке сети, чтобы ускорить вычисления.
Теперь команда Кинга объединила соответствующие преимущества этих двух стратегий, чтобы создать радикально новый комбинированный подход. “Наш подход основан на множестве небольших, эффективных и недорогостоящих вычислительных операций, которые в совокупности выполняются намного быстрее, чем несколько крупных”, – говорит Максимилиан Пробст Гутенберг, преподаватель и член группы Кинга, сыгравший ключевую роль в разработке алгоритмов с почти линейным временем выполнения.
Во многом успехи исследователей из ETH Zurich связаны с решением расширить сферу своей работы, не ограничиваясь разработкой новых алгоритмов. Команда также использует и разрабатывает новые математические инструменты, которые еще больше ускоряют их алгоритмы. В частности, они разработали новую структуру данных для организации сетевых данных; это позволяет чрезвычайно быстро идентифицировать любые изменения в сетевом подключении; это, в свою очередь, помогает сделать алгоритмическое решение удивительно быстрым. С учетом того, что появилось так много приложений для алгоритмов с почти линейным временем работы и таких инструментов, как новая структура данных, общая инновационная спираль вскоре может раскручиваться намного быстрее, чем раньше.
Тем не менее, создание основ для решения очень больших задач, которые ранее не могли быть эффективно вычислены, является лишь одним из преимуществ этих значительно более быстрых потоковых алгоритмов, поскольку они также меняют способ, с помощью которого компьютеры в первую очередь вычисляют сложные задачи. “За последнее десятилетие произошла революция в теоретических основах получения доказуемо быстрых алгоритмов для решения фундаментальных задач в области теоретической информатики”, – пишет международная группа исследователей из Калифорнийского университета в Беркли, в состав которой входят Расмус Кинг и Дикша Адиль, научный сотрудник Института теоретической информатики.
Источник: ScienceDaily.
