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

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

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

"Кратчайший путь — это прекрасная задача, которую может понять любой человек в мире», — говорит Миккель Торуп, специалист по информатике из Университета Копенгагена.

Интуитивно понятно, что проще всего найти кратчайший путь к близлежащим пунктам назначения. Поэтому, если вы хотите разработать самый быстрый алгоритм для решения задачи кратчайшего пути, разумнее всего начать с поиска ближайшей точки, затем следующей по близости и так далее. Но для этого вам нужно неоднократно выяснить, какая точка ближе всего. По ходу дела вы будете сортировать точки по расстоянию. Для любого алгоритма, использующего этот подход, существует фундаментальное ограничение скорости: вы не можете работать быстрее, чем время, затрачиваемое на сортировку.

Сорок лет назад исследователи, разрабатывающие алгоритмы поиска кратчайших путей, столкнулись с этим «барьером сортировки». Теперь группа исследователей разработала новый алгоритм, который его преодолевает. Он не занимается сортировкой и работает быстрее, чем любой другой алгоритм, использующий сортировку.

«Со стороны авторов было смело рассчитывать на то, что они смогут преодолеть этот барьер», — говорит Роберт Тарьян, информатик из Принстонского университета. «Это потрясающий результат».

Граница познания

Для математического анализа проблемы поиска кратчайших путей исследователи используют язык графов — сетей из точек, или узлов, соединённых линиями, или рёбрами. Каждое ребро между узлами обозначается числом, его весом, который может представлять собой длину этого участка или время, необходимое для его прохождения. Обычно между любыми двумя узлами существует множество маршрутов, и самым коротким считается тот, чьи веса складываются в наименьшее число. Если задан граф и определённый узел-источник, то цель алгоритма — найти кратчайший путь к каждому другому узлу.

Самый известный алгоритм кратчайшего пути, разработанный новатором в области компьютерных технологий Эдсгером Дейкстрой в 1956 году, начинает с исходного узла и шаг за шагом идёт наружу. Это эффективный подход, поскольку знание кратчайшего пути к близлежащим узлам может помочь вам найти кратчайшие пути к более отдалённым узлам. Но поскольку конечным результатом является отсортированный список кратчайших путей, барьер сортировки устанавливает фундаментальное ограничение на скорость работы алгоритма.

Ищем кратчайший путь

Начиная с точки А, мы видим два пути. Путь до В составляет 1 единицу, путь до С – 5. Теперь мы знаем кратчайший путь до В, но до С может существовать более короткий путь, чем прямой.

Проходим до В и вновь смотрим на то, какие там есть пути, суммируя их длину от А. Видим, что путь от А до D короче, чем от A до C.

Переходим в D и вновь изучаем пути. И вот мы нашли кратчайший путь до С.


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

В конце 1990-х — начале 2000-х годов Торуп и другие исследователи разработали алгоритмы, которые преодолели барьер сортировки, но для этого им пришлось сделать определённые предположения о весах. Никто не знал, как распространить их методы на произвольные веса. Казалось, они зашли в тупик.

«Исследования прекратились на очень долгое время», — говорит Ран Дуань, информатик из Университета Цинхуа в Пекине. «Многие люди считали, что лучшего способа не существует».

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

 Эдсгер Дейкстра разработал классический алгоритм, который находит кратчайший путь от определённой точки сети до любой другой точки.
Эдсгер Дейкстра разработал классический алгоритм, который находит кратчайший путь от определённой точки сети до любой другой точки.

Без сортировки

Интерес Дуаня к барьеру сортировки возник почти 20 лет назад, когда он учился в аспирантуре Мичиганского университета, где его советник был одним из исследователей, разработавших способ преодоления барьера в конкретных случаях. Но только в 2021 году Дуань разработал более перспективный подход.

Ключ заключался в том, чтобы сосредоточиться на том, куда алгоритм переходит на каждом шаге. Алгоритм Дейкстры берёт область, которую он уже исследовал на предыдущих шагах. Он решает, куда двигаться дальше, сканируя «границу» этого региона, то есть все узлы, подключённые к его границе. Поначалу это не занимает много времени, но по мере продвижения алгоритма он становится всё медленнее.

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

В течение следующего года Дуань дорабатывал эту базовую идею, и к осени 2022 года он был полон оптимизма, что сможет преодолеть технические препятствия. Он привлёк трёх аспирантов для проработки деталей, и через несколько месяцев они пришли к частичному решению — алгоритму, который преодолевал барьер сортировки для любых весов, но только на так называемых неориентированных графах.

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

«Может возникнуть ситуация, когда из A можно легко добраться до B, но из B нельзя легко добраться до A», — говорит Сяо Мао, аспирант факультета информатики Стэнфордского университета. «Это доставит вам массу проблем».

Перспективные пути

Летом 2023 года Мао услышал доклад Дуаня об алгоритме для неориентированных графов на конференции в Калифорнии. Он завязал разговор с Дуанем, работами которого давно восхищался.

«Я впервые встретился с ним в реальной жизни», — вспоминает Мао. «Это было очень волнительно».

После конференции Мао начал думать над этой проблемой в свободное время. Тем временем Дуань и его коллеги изучали новые подходы, которые могли бы работать с направленными графами. Они черпали вдохновение в другом старинном алгоритме решения проблемы кратчайших путей, называемом алгоритмом Беллмана-Форда, который не даёт отсортированного списка. На первый взгляд, это казалось неразумной стратегией, поскольку алгоритм Беллмана-Форда работает гораздо медленнее, чем алгоритм Дейкстры.

«Когда вы проводите исследование, вы стараетесь выбрать перспективный путь», — говорит Торуп. «Я бы назвал антиперспективным путь Беллмана-Форда, потому что он выглядит как самая глупая вещь, которую только можно сделать».

Команда Дуаня избежала медлительности алгоритма Беллмана-Форда, запуская его так, чтобы он отрабатывал только по несколько шагов за раз. Такое выборочное использование алгоритма Беллмана-Форда позволило им заранее искать наиболее ценные узлы для изучения на последующих шагах. Эти узлы похожи на перекрёстки основных магистралей в дорожной сети.

«Через них нужно пройти, чтобы получить кратчайший путь ко многим другим объектам», — говорит Торуп.

В марте 2024 года Мао придумал ещё один перспективный подход. Некоторые ключевые шаги в первоначальном подходе команды использовали случайность. Случайные алгоритмы могут эффективно решать многие задачи, но исследователи по-прежнему предпочитают неслучайные подходы. Мао придумал новый способ решения проблемы кратчайших путей без использования случайности. Он присоединился к команде, и в течение последующих месяцев они работали вместе в групповых чатах и по видеосвязи, чтобы объединить свои идеи. Наконец, осенью Дуань понял, что они могут адаптировать технику из алгоритма, который он разработал в 2018 году, преодолевшего барьер сортировки для другой задачи с графами. Эта техника была последней частью, необходимой для создания алгоритма, который работает быстрее, чем алгоритм Дейкстры, как на направленных, так и на неориентированных графах.

Готовый алгоритм нарезает граф на слои, двигаясь от источника, как и алгоритм Дейкстры. Но вместо того, чтобы рассматривать всю границу на каждом шаге, он использует алгоритм Беллмана-Форда для определения влиятельных узлов, движется вперёд от этих узлов, чтобы найти кратчайшие пути к другим, а затем возвращается к другим граничным узлам. Он не всегда находит узлы внутри каждого слоя в порядке возрастания расстояния, поэтому он не упирается в барьер сортировки. И если правильно нарезать граф, он работает немного быстрее, чем лучшая версия алгоритма Дейкстры. Он значительно сложнее, опирается на множество деталей, которые должны быть правильно подогнаны друг к другу. Но любопытно, что ни одна из этих частей не использует сложную современную математику.

«Эту вещь могли бы открыть и 50 лет назад, но этого не случилось», — говорит Торуп. «Это делает её ещё более впечатляющей».

Дуань и его команда планируют изучить, можно ли оптимизировать алгоритм, чтобы сделать его ещё быстрее. После того как барьер сортировки был побеждён, время работы нового алгоритма не приблизилось ни к какому фундаментальному пределу, о котором знают компьютерщики.

«Будучи оптимистом, я не удивлюсь, если вы сможете сократить его ещё больше», — говорит Тарджан. «Я уверен, что это не последний шаг в этом процессе».

Комментарии (3)


  1. uvelichitel
    11.08.2025 16:52

    Звучит как чудо. Этак скоро и задачу коммивояжера осилим. И на большое О проблему нашу замахнемся)
    Не вижу в тексте не описание алгоритма на пальцах, ни в псевдокоде. Невнимательно что ли читал мелкий текст)


    1. d_ilyich
      11.08.2025 16:52

      В тексте есть ссылка


  1. SadOcean
    11.08.2025 16:52

    Я правильно понял текст, что фактически речь идет об иерархическом поиске, где иерархия организуется не по геометрическому принципу, а по принципу связности кластеров?