Исследователи из ETH Zurich под руководством Расмуса Кинга разработали принципиально новый алгоритм для расчета потоков в транспортных сетях, который обещает стать революционным достижением в области теоретической информатики.
Новый алгоритм решает задачу о максимальном потоке при минимальной стоимости транспортировки грузов. Он применим к любым сетям, будь то транспортные, водные, электрические или даже интернет.
До сих пор расчеты занимали гораздо больше времени, чем считывание данных о сети. Время вычислений росло быстрее, чем размер самой сети. Алгоритм Кинга устраняет эту проблему: его скорость вычислений растет пропорционально размеру сети.
В 2022 году команда Кинга доказала теоретическую обоснованность своего алгоритма. Он относится к классу «почти линейных» алгоритмов и вызвал восторг научного сообщества. Исследователи из ETH Zurich усовершенствовали свой подход и разработали новые «почти линейные» алгоритмы. Один из них решает задачу о минимальной стоимости потока для сетей, которые постепенно изменяются со временем.
В частности, алгоритмы могут найти кратчайшие маршруты в сетях, где соединения добавляются или удаляются. Это может быть полезно для навигационных приложений, которым нужно учитывать изменения в дорожной сети, например, ремонтные работы или закрытие дорог.
Новый алгоритм Кинга вычисляет оптимальный маршрут в таких сетях за почти линейное время. Секрет его скорости заключается в том, что он выполняет множество мелких, эффективных вычислительных шагов вместо нескольких крупных.
