Команда под руководством Расмуса Кинга из Швейцарской высшей технической школы Цюриха совершила настоящий прорыв в области алгоритмов сетевых потоков.
Исследователи построили быстрейший алгоритм поиска оптимальных потоков в сетях
Исследователи из Швейцарской высшей технической школы Цюриха разработали самый быстрый из возможных алгоритм, способный рассчитывать оптимальные потоки в сложных сетях. Это позволит увеличить пропускную способность любых сетей — от транспорта до интернета без подключения дополнительного оборудования.
Сети в природе. Unsplash
Задаче о потоках сетях уже почти 90 лет. В той или иной степени ее решает, например, Яндекс.Навигатор, когда пытается провести вас по самому незагруженному маршруту и сэкономить ваше время. Но эта задача очень ресурсоемкая, она требует очень большого счета. То, что сделали исследователи из Цюриха, почти невероятно. Они создали настолько быстрый алгоритм решения, что быстрее, вероятно, уже нельзя.
Уникальность решения заключается в том, что время вычислений растет линейно в зависимости от размера сети. Это делает возможным приложение алгоритма к очень большим и сложным сетям. До этого открытия время вычислений росло по степенному закону относительно размера сети, что ограничивало применение таких алгоритмов к действительно крупномасштабным задачам.
Развязка
Разработчики предложили образное сравнение для скорости алгоритма и прошлых подходов: как между Porsche и конным экипажем. Это если и преувеличение, то небольшое.
Динамические сети
Трехмерная сеть
Если, например, транспортная сеть меняется достаточно медленно, есть и сети, которые меняются быстро и меняются все время. В интернете постоянно возникают и прекращают работу серверы, в мозге появляются и исчезают синапсы, не говоря уже о социальных сетях или сетях внутри живой клетки. Команда Кинга разработала дополнительные алгоритмы, способные работать и с динамически сетями.
Ключ к успеху команды заключается в комбинации двух ранее реализованных подходов к решению задач о сетевых потоках. Они объединили стратегию, основанную на железнодорожных сетях (этот алгоритм был разработан еще 1970-е годы), с подходом, вдохновленным электрическими сетями (его удалось построить в 2004 году). В своем решении ученые смогли избежать полного обсчета сразу всей сети (это медленно), и свели расчет к последовательности простых и быстрых шагов.
Исследователи разработали новую структуру данных для организации сетевой информации, что позволяет быстро идентифицировать любые изменения в сетевых соединениях.
Значимость этого решения выходит далеко за рамки чисто теоретических достижений. Новые алгоритмы могут найти применение в широчайшем спектре областей — от оптимизации транспортных потоков до анализа социальных сетей и моделирования биологических процессов.