Ученые разработали сверхбыстрый алгоритм

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

До сих пор расчеты занимали гораздо больше времени, чем считывание данных о сети. Время вычислений росло быстрее, чем размер самой сети. Алгоритм Кинга устраняет эту проблему: его скорость вычислений растет пропорционально размеру сети.

В 2022 году команда Кинга доказала теоретическую обоснованность своего алгоритма. Он относится к классу «почти линейных» алгоритмов и вызвал восторг научного сообщества. Исследователи из ETH Zurich усовершенствовали свой подход и разработали новые «почти линейные» алгоритмы. Один из них решает задачу о минимальной стоимости потока для сетей, которые постепенно изменяются со временем.

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

Новый алгоритм Кинга вычисляет оптимальный маршрут в таких сетях за почти линейное время. Секрет его скорости заключается в том, что он выполняет множество мелких, эффективных вычислительных шагов вместо нескольких крупных.