Исследователи построили быстрейший алгоритм поиска оптимальных потоков в сетях
![Исследователи построили быстрейший алгоритм поиска оптимальных потоков в сетях Исследователи построили быстрейший алгоритм поиска оптимальных потоков в сетях](https://images.techinsider.ru/upload/img_cache/9b8/9b8c8f96d206d3268e2075b5499f83f1_ce_1935x1290x0x646_cropped_510x340.webp)
Команда под руководством Расмуса Кинга из Швейцарской высшей технической школы Цюриха совершила настоящий прорыв в области алгоритмов сетевых потоков.
Уникальность решения заключается в том, что время вычислений растет линейно в зависимости от размера сети. Это делает возможным приложение алгоритма к очень большим и сложным сетям. До этого открытия время вычислений росло по степенному закону относительно размера сети, что ограничивало применение таких алгоритмов к действительно крупномасштабным задачам.
![Развязка Развязка](https://images.techinsider.ru/upload/img_cache/5db/5db184d2024b99319de5a05ab7fcdb8a_cropped_510x287.webp)
Разработчики предложили образное сравнение для скорости алгоритма и прошлых подходов: как между Porsche и конным экипажем. Это если и преувеличение, то небольшое.
Динамические сети
![Трехмерная сеть Трехмерная сеть](https://images.techinsider.ru/upload/img_cache/e1e/e1ec1a9dd0143da4c08117065fd95b23_cropped_510x364.webp)
Если, например, транспортная сеть меняется достаточно медленно, есть и сети, которые меняются быстро и меняются все время. В интернете постоянно возникают и прекращают работу серверы, в мозге появляются и исчезают синапсы, не говоря уже о социальных сетях или сетях внутри живой клетки. Команда Кинга разработала дополнительные алгоритмы, способные работать и с динамически сетями.
Ключ к успеху команды заключается в комбинации двух ранее реализованных подходов к решению задач о сетевых потоках. Они объединили стратегию, основанную на железнодорожных сетях (этот алгоритм был разработан еще 1970-е годы), с подходом, вдохновленным электрическими сетями (его удалось построить в 2004 году). В своем решении ученые смогли избежать полного обсчета сразу всей сети (это медленно), и свели расчет к последовательности простых и быстрых шагов.
Исследователи разработали новую структуру данных для организации сетевой информации, что позволяет быстро идентифицировать любые изменения в сетевых соединениях.
Значимость этого решения выходит далеко за рамки чисто теоретических достижений. Новые алгоритмы могут найти применение в широчайшем спектре областей — от оптимизации транспортных потоков до анализа социальных сетей и моделирования биологических процессов.