Исследователи разрабатывают самый быстрый алгоритм сетевого потока

Два мыслителя за почти максимально быстрым алгоритмом потока: Расмус Кинг и Максимилиан Пробст Гутенберг.Кредит: Eth Zurich / Nicola Pitaro

Новаторская работа команды Кинга включает в себя так называемый алгоритм сетевого потока, который рассматривает вопрос о том, как достичь максимального потока в сети, одновременно минимизируя транспортные затраты.

Представьте, что вы используете европейскую транспортную сеть и ищете самый быстрый и дешевый маршрут, чтобы перенести как можно больше товаров из Копенгагена в Милан.Алгоритм Kyng может быть применен в таких случаях для расчета оптимального, самых низких дорожных потоков для любого вида сети-будьте рельсы, дороги, воды или Интернета.

Его алгоритм выполняет эти вычисления так быстро, что он может доставить решение в тот момент, когда компьютер читает данные, которые описывают сеть.

Перед Кингом никто никогда не смог это сделать - даже если исследователи работают над этой проблемой около 90 лет.Ранее для вычисления оптимального потока потребовалось значительно больше времени, чем обработать сетевые данные.

И по мере того, как сеть стала больше и сложнее, требуемое время вычисления увеличилось намного быстрее, сравнительно говоря, чем фактический размер вычислительной задачи.Вот почему мы также видим проблемы с потоком в сетях, которые слишком велики, чтобы компьютер даже рассчитывал.

Подход Kyng устраняет эту проблему: использование его алгоритма, вычисление времени и размера сети с той же скоростью - немного, похожее на поход и постоянно поддерживать такой же темп, как бы то ни было, как ни крутой путь.

Взгляд на необработанные фигуры показывает, как далеко мы продвинулись: до поворота тысячелетия не удалось вычислять быстрее, чем M1.5, где M обозначает количество соединений в сети, которую компьютер должен рассчитать,И просто чтение сетевых данных однажды занимает M.

В 2004 году скорость вычислений, необходимая для решения проблемы, была успешно снижена до M1.33.Используя алгоритм Kyng, «дополнительное» время вычисления, необходимое для достижения решения после чтения сетевых данных, теперь незначительно.

Таким образом, исследователи Eth Zurich разработали то, что теоретически является самым быстрым алгоритмом сетевого потока.Два года назад Кинг и его команда представили математическое доказательство своей концепции в новаторской статье.Ученые называют эти новые, почти оптимально быстрые алгоритмы «алгоритмами почти линейного времени», а сообщество теоретических компьютерных ученых отреагировало на прорыв Кинг с смесью изумления и энтузиазма.

Докторский руководитель Кинга, Даниэль А. Спилман, профессор прикладной математики и информатики в Йельском университете и сам пионер и дойен в этой области, сравнили «абсурдно быстрый» алгоритм с нагнувшим конным корабли.

А также выиграть премию за лучшую бумагу 2022 года на ежегодном симпозиуме IEEE по Фондам информатики (FOCS), их статья также была выделена в Коммуникациях Computing JournДесять крупнейших открытий в области компьютерных наук в 2022 году.

Исследователи Eth Zurich с тех пор усовершенствовали свой подход и разработали дальнейшие почти линейные алгоритмы.Например, первый алгоритм все еще был сосредоточен на фиксированных статических сетях, чьи связи направлены, что означает, что они функционируют как односторонние улицы в городских дорожных сетях.

Алгоритмы, опубликованные в этом году, теперь также могут вычислять оптимальные потоки для сетей, которые постепенно изменяются с течением времени.Молновые вычисления являются важным шагом в борьбе с очень сложными и богатыми данными сетей, которые изменяются динамически и очень быстро, такие как молекулы или мозг в биологии или дружба человека.

В четверг Саймон Мейерханс-член команды Kyng-предложил новый почти личный алгоритм на ежегодном симпозиуме ACM по теории вычислительных наук (Stoc 2024) в Ванкувере.Этот алгоритм решает минимальную проблему максимального потока для сетей, которая постепенно изменяется при добавлении новых соединений.

Кроме того, во второй статье, принятой Симпозиумом IEEE по основам информатики (FOCS) в октябре, исследователи ETH разработали еще один алгоритм, который также обрабатывает соединения, которые удаляются.

В частности, эти алгоритмы идентифицируют самые короткие маршруты в сетях, где соединения добавляются или удаляются.В реальных транспортных сетях примеры таких изменений в Швейцарии включают полное закрытие и затем частичное повторное открытие базового туннеля Готард в течение месяцев с лета 2023 года, или недавний оползень, который уничтожил часть автомагистрали A13, которая является основной альтернативойМаршрут в туннель Gotthard Road.

Столкнувшись с такими изменениями, как компьютер, услуга онлайн-карты или планировщик маршрутов рассчитывают самую дешевую и быстрое соединение между Миланом и Копенгагеном?Новые алгоритмы Kyng также вычисляют оптимальный маршрут для этих постепенных или уменьшенных изменяющихся сетей в почти линейное время-настолько быстро, что вычисление времени для каждого нового соединения, будь то добавлено путем перенаправления или создания новых маршрутов, снова нежире.

Но что именно это делает подход Кинга к вычислениям намного быстрее, чем любой другой алгоритм сетевого потока?В принципе, все вычислительные методы сталкиваются с проблемой анализа сети во множественных итерациях, чтобы найти оптимальный поток и маршрут с минимальной стоимостью.При этом они проходят через каждый из различных вариантов, из которых подключения открыты, закрыты или перегружены, потому что они достигли предела своей способности.

До Kyng компьютерные ученые имели тенденцию выбирать между двумя ключевыми стратегиями для решения этой проблемы.Один из них был смоделирован в железнодорожной сети и включал в себя вычисление целого участка сети с измененным потоком трафика в каждой итерации.Вторая стратегия, вдохновленная потоками электроэнергии в сетке электроэнергии, составила всю сеть в каждой итерации, но использовала статистические средние значения для модифицированного потока каждого раздела сети, чтобы ускорить вычисление.

Команда Kyng теперь связала соответствующие преимущества этих двух стратегий, чтобы создать радикальный новый комбинированный подход.«Наш подход основан на многих небольших, эффективных и недорогих вычислительных этапах, которые-объединенные вместе, намного быстрее, чем несколько крупных»,-говорит Максимилиан Пробст Гутенберг, лектор и член группы Kyng, который играл ключевую рольПри разработке почти линейных алгоритмов.

Краткий взгляд на историю этой дисциплины добавляет дополнительное измерение к значению прорыва Кинга: проблемы потока в сетях были одними из первых, кто был систематически решать с помощью алгоритмов в 1950 -х годах, а алгоритмы потока сыграли важную роль в созданииТеоретическая информатика как область исследований сама по себе.

Известный алгоритм, разработанный математиками Лестером Р. Фордом-младшим и Дельбертом Р. Фулкерсоном, также проистекает из этого периода.Их алгоритм эффективно решает проблему максимального потока, которая стремится определить, как перевозить как можно больше товаров через сеть, не превышая возможности отдельных маршрутов.

Эти достижения показали исследователям, что проблема с максимальным потоком, проблема с минимальной стоимостью (проблема перехода или транспорта) и многие другие важные проблемы с сетевым потоком можно рассматривать как особые случаи общей проблемы с минимальными затратами.

До исследования Kyng большинство алгоритмов могли эффективно решить одну из этих проблем, хотя они не могли сделать даже это особенно быстро и не могли быть расширены на более широкую проблему потока с минимальной стоимостью.

То же самое относится и к новаторским алгоритмам потока 1970 -х годов, для которых теоретические компьютерные ученые Джон Эдвард Хопкрофт, Ричард Мэннинг Карп и Роберт Эндре Тарджан получили награду Тьюринга, рассматриваемая как «Нобелевская премия» компьютерных наук.Карп получил его в 1985 году;Хопкрофт и Тарджан выиграли их в 1986 году.

Лишь в 2004 году математики и компьютерные ученые Даниэль Спилман и Шан-Хуа Тенг-и позже Сэмюэль Дайтч-приняли участие в алгоритмах написания, которые также обеспечивали быстрое и эффективное решение проблемы с минимальной стоимостью.Именно эта группа сместила фокус на потоки питания в электрической сетке.

Их переключение в перспективе от железных дорог к электричеству привело к ключевому математическому различию: если в железнодорожной сети перенаправляется поезд, потому что линия выходит из эксплуатации, следующий лучший маршрут в соответствии с графиком уже может быть занята другим поездом.

В электрической сетке можно частично перемещать сетевое соединение, через которое, чтобы другой ток уже течет.Таким образом, в отличие от поездов, электрический ток может, в математических терминах, быть «частично» перемещаться в новое соединение.

Это частичное перенаправление позволило Спилману и его коллегам вычислять такой маршрут, которые меняются гораздо быстрее и в то же время пересматривать всю сеть после каждого изменения.«Мы отвергли подход Спилмана в создании самых мощных алгоритмов, которые мы могли бы для всей сети», - говорит Кинг.

«Вместо этого мы применили его идею о частичном расчете маршрута к более ранним подходам Хопкрофта и Карпа».Это вычисление частичных маршрутов в каждой итерации сыграло важную роль в ускорении общего расчета потока.

Большая часть прогресса исследователей Eth Zurich сводится к решению расширить их работу за пределы разработки новых алгоритмов.Команда также использует и разрабатывает новые математические инструменты, которые еще больше ускоряют их алгоритмы.

В частности, они разработали новую структуру данных для организации сетевых данных.Это позволяет быстро идентифицировать любые изменения в сетевом соединении.И это, в свою очередь, помогает сделать алгоритмическое решение таким удивительно быстрым.

С таким количеством приложений, выстроившихся в линию для почти линейных алгоритмов времени, и для таких инструментов, как новая структура данных, общая инновационная спираль может скоро стать намного быстрее, чем раньше.

Тем не менее, закладывание оснований для решения очень больших проблем, которые ранее не могли быть эффективно вычислены, является лишь одним из преимуществ этих значительно более быстрых алгоритмов потока - потому что они также изменяют способ, которым компьютеры в первую очередь рассчитывают сложные задачи.

«За последнее десятилетие в теоретических основаниях в теоретических основаниях в теоретических компьютерных науках произошла революция в теоретических основаниях для получения доверенно быстрых алгоритмов основополагающих задач», - пишет международная группа исследователей из Калифорнийского университета, Беркли, в которую входят среди его членов Расмус Кинг иДикша Адил, исследователь Института теоретических исследований в Эт Цюрих.

More information: Li Chen et al, Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow, Proceedings of the 56th Annual ACM Symposium on Theory of Computing (2024). DOI: 10.1145/3618260.3649745

Почти линейные алгоритмы времени для декрементных графиков: поток мин.65th Symposium IEEE по фондам компьютерных наук (FOCS) 2024. FOCS.Computer.org/2024/accepte… Apers-for-focs-2024/