Индийский исследователь преодолел давнее ограничение в алгоритмах поиска кратчайших путей, сохранив высокую скорость

Новый этап в оптимизации поиска кратчайших маршрутов

Как сообщает НВ — Техно: Манодж Гупта, учёный из Индийского технологического института в Гандинагаре, добился прорыва в разработке алгоритмов для нахождения кратчайших путей между всеми парами узлов в больших сетях. Его работа устранила ограничение, существовавшее с 1996 года, расширив при этом теоретическую точность алгоритма, не увеличивая время вычислений. Итоги исследования были представлены на 66-м ежегодном симпозиуме по теории вычислений FOCS 2025.

Особенности задачи поиска кратчайших путей

Задача поиска кратчайших путей для всех пар вершин (APSP) заключается в определении минимального расстояния между каждой парой точек в сети. Традиционные методы решения этой задачи обычно требуют времени, пропорционального кубу количества узлов. В 1996 году группа учёных - Дор, Гальперин и Цвик - предложили алгоритм с двухкратным приближением, который гарантировал, что вычисленное расстояние не превышает реальное более чем в два раза, однако он эффективно работал только для удалённых узлов.

Применяя новый многоуровневый подход к выбору ключевых точек, Манодж Гупта сумел анализировать сеть на различных масштабах. Это позволило сохранить высокую скорость работы алгоритма при значительно улучшенном качестве оценки расстояний для близко расположенных узлов. Следует отметить, что разработка в настоящее время носит теоретический характер и не обещает немедленного ускорения существующих навигационных систем. Тем не менее, этот алгоритм открывает новые возможности для анализа масштабных сетей в таких областях, как транспорт, телекоммуникации и искусственный интеллект.

Улучшение алгоритмов поиска кратчайших путей может оказать значительное влияние на отрасли, где критично эффективное управление большими объёмами данных и ресурсами. В транспортной сфере это способно привести к:

• оптимизации маршрутов доставки,
• снижению затрат на топливо,
• уменьшению времени в пути.

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