Команда исследователей из Университета Цинхуа под руководством Ран Дуана разработала алгоритм, который впервые за 40 лет преодолел «барьер сортировки» в задаче поиска кратчайших путей. Новый подход работает быстрее классического алгоритма Дейкстры, созданного в 1956 году, и не требует сортировки узлов по расстоянию.
Задача поиска кратчайших путей — это как построение оптимальных маршрутов от вашего дома до работы, спортзала и супермаркета одновременно. Алгоритм Дейкстры работает интуитивно: сначала находит ближайшую точку, потом следующую по близости и так далее. Но такой подход требует постоянной сортировки точек по расстоянию, что создает фундаментальное ограничение скорости. В 1984 году Роберт Тарьян усовершенствовал алгоритм Дейкстры до этого предела, и дальнейший прогресс казался невозможным.
Прорыв произошел благодаря кардинально новому подходу. Вместо изучения всех узлов на «границе» исследованной области, алгоритм Дуана группирует соседние узлы в кластеры и рассматривает только по одному узлу из каждого кластера. Дополнительно используется модифицированный алгоритм Беллмана-Форда для выявления «влиятельных» узлов — тех, через которые проходит множество кратчайших путей, как крупные развязки в дорожной сети.
Работа продолжалась 3 года: от первоначальной идеи в 2021 году до финальной версии осенью 2024-го. Сначала команда решила задачу только для неориентированных графов (где связи работают в обе стороны), а затем при участии аспиранта Стэнфорда Сяо Мао распространила решение на направленные графы с односторонними связями. Алгоритм разрезает граф на слои и не всегда находит узлы в порядке возрастания расстояния, что позволяет обойти барьер сортировки.
Несмотря на техническую сложность, алгоритм не использует продвинутую математику — по словам эксперта Миккеля Торупа, «эта штука могла быть открыта 50 лет назад». Исследователи планируют дальнейшие оптимизации: с преодолением барьера сортировки время выполнения алгоритма больше не приближается ни к каким известным фундаментальным ограничениям.
Источник новости и обложки: www.wired.com