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