Каноническая задача в информатике — поиск кратчайшего пути к каждой точке сети. Новый подход превосходит классический алгоритм, изучаемый в учебниках. Комментарий Сохранить статью Прочитать позже
Введение
Если вы хотите решить сложную задачу, часто помогает организация. Например, можно разбить задачу на части и начать с самых простых. Но такая сортировка имеет свою цену. Вы можете потратить слишком много времени на раскладывание частей по порядку.
Эта дилемма особенно актуальна для одной из самых известных задач в информатике: поиска кратчайшего пути от заданной начальной точки сети до любой другой точки. Это как улучшенная версия задачи, которую приходится решать каждый раз при переезде: найти оптимальный маршрут от нового дома до работы, спортзала и супермаркета.
«Нахождение кратчайших путей — это прекрасная задача, которая понятна любому человеку в мире», — сказал Миккель Торуп, специалист по информатике из Копенгагенского университета.
Интуитивно понятно, что проще всего найти кратчайший путь к ближайшим пунктам назначения. Поэтому, если вы хотите разработать максимально быстрый алгоритм для задачи поиска кратчайшего пути, кажется разумным начать с поиска ближайшей точки, затем следующей по близости и так далее. Но для этого вам потребуется многократно определять, какая точка ближе всего. Вы будете сортировать точки по расстоянию по мере продвижения. Существует фундаментальное ограничение скорости для любого алгоритма, использующего этот подход: вы не можете двигаться быстрее времени, необходимого для сортировки.
Сорок лет назад исследователи, разрабатывавшие алгоритмы поиска кратчайших путей, столкнулись с этим «барьером сортировки». Теперь группа исследователей разработала новый алгоритм, который его преодолевает. Он не сортирует, но работает быстрее любого алгоритма, который это делает.
«Авторы проявили дерзость, полагая, что смогут преодолеть этот барьер», — сказал Роберт Тарьян, специалист по информатике из Принстонского университета. «Это потрясающий результат».
Граница знаний
Для математического анализа задачи поиска кратчайших путей исследователи используют язык графов — сети точек, или узлов, соединённых линиями. Каждое звено между узлами обозначено числом, называемым его весом, которое может представлять длину этого сегмента или время, необходимое для его прохождения. Обычно между любыми двумя узлами существует множество маршрутов, и кратчайшим считается тот, чьи веса в сумме дают наименьшее число. При наличии графа и конкретного исходного узла цель алгоритма — найти кратчайший путь до каждого другого узла.
Самый известный алгоритм поиска кратчайших путей, разработанный пионером компьютерной науки Эдсгером Дейкстрой в 1956 году, начинается с исходного узла и постепенно расширяется. Это эффективный подход, поскольку знание кратчайшего пути к ближайшим узлам может помочь найти кратчайшие пути к более удалённым узлам. Но поскольку конечный результат — отсортированный список кратчайших путей, барьер сортировки устанавливает фундаментальное ограничение на скорость работы алгоритма.
В 1984 году Тарьян и другой исследователь улучшили исходный алгоритм Дейкстры, доведя его скорость до этого предела. Дальнейшее улучшение потребовало бы использования алгоритма, исключающего сортировку.
В конце 1990-х — начале 2000-х годов Торуп и другие исследователи разработали алгоритмы, преодолевающие барьер сортировки, но им требовалось сделать определённые предположения о весах. Никто не знал, как распространить их методы на произвольные веса. Казалось, они достигли цели.
«Исследования были приостановлены на очень долгое время», — сказал Жан Дуань, специалист по информатике из Университета Цинхуа в Пекине. «Многие считали, что лучшего пути нет».
Дуань не был одним из них. Он давно мечтал построить алгоритм поиска кратчайших путей, способный преодолеть барьер сортировки на всех графах. Прошлой осенью ему это наконец удалось.
Не в форме
Интерес Дуаня к проблеме сортировочного барьера возник почти 20 лет назад, во время его обучения в аспирантуре Мичиганского университета, где его руководителем был один из исследователей, разработавших способы преодоления барьера в конкретных случаях. Но только в 2021 году Дуан разработал более многообещающий подход.
Ключевым моментом было сосредоточиться на том, куда алгоритм движется дальше на каждом шаге. Алгоритм Дейкстры берёт область, уже исследованную на предыдущих шагах. Он решает, куда двигаться дальше, сканируя «границу» этой области, то есть все узлы, соединённые с её границей. Поначалу это занимает немного времени, но по мере развития алгоритма процесс замедляется.
Вместо этого Дуань предложил объединить соседние узлы на границе в кластеры. Тогда он рассматривал бы только один узел из каждого кластера. При меньшем количестве узлов для просеивания поиск мог бы быть быстрее на каждом шаге. Кроме того, алгоритм мог бы в конечном итоге перейти к чему-то, отличному от ближайшего узла, поэтому барьер сортировки не применялся бы. Но гарантировать, что этот подход, основанный на кластеризации, действительно ускоряет алгоритм, а не замедляет его, было бы непросто.
В течение следующего года Дуань конкретизировал эту базовую идею, и к осени 2022 года он был уверен, что сможет преодолеть технические препятствия. Он привлек трёх аспирантов для помощи в проработке деталей, и через несколько месяцев они нашли частичное решение — алгоритм, который преодолевал барьер сортировки для любых весов, но только на так называемых неориентированных графах.
В неориентированных графах каждое звено можно пройти в обоих направлениях. Специалистов по информатике обычно больше интересует более широкий класс графов с односторонними путями, но такие «ориентированные» графы часто сложнее ориентировать.
«Возможно, A легко доберётся до B, но B не сможет легко доехать до A», — сказал Сяо Мао, аспирант факультета компьютерных наук Стэнфордского университета. «Это создаст вам массу проблем».
Перспективные пути
Летом 2023 года Мао услышал доклад Дуаня об алгоритме неориентированного графа на конференции в Калифорнии. Он разговорился с Дуанем, чьими работами давно восхищался.
«Я впервые встретил его в реальной жизни, — вспоминал Мао. — Это было очень волнительно».
После конференции Мао начал размышлять над этой задачей в свободное время. Тем временем Дуань и его коллеги изучали новые подходы, которые могли бы работать с ориентированными графами. Они вдохновились другим известным алгоритмом поиска кратчайших путей, называемым алгоритмом Беллмана-Форда, который не создаёт отсортированный список. На первый взгляд, это казалось неразумной стратегией, поскольку алгоритм Беллмана-Форда гораздо медленнее алгоритма Дейкстры.
«Всякий раз, проводя исследование, вы стараетесь выбрать многообещающий путь, — сказал Торуп. — Я бы назвал выбор Беллмана-Форда почти неперспективным, потому что это выглядит совершенно глупо, что можно сделать».
Команда Дуаня избежала медлительности алгоритма Беллмана-Форда, выполняя его всего по несколько шагов за раз. Такое избирательное использование алгоритма Беллмана-Форда позволило алгоритму заранее искать наиболее ценные узлы для исследования на последующих этапах. Эти узлы подобны перекрёсткам основных магистралей в дорожной сети.
«Вам придется пройти через [них], чтобы получить кратчайший путь ко многим другим вещам», — сказал Торуп.
В марте 2024 года Мао задумался о другом многообещающем подходе. Некоторые ключевые этапы первоначального подхода команды использовали случайность. Рандомизированные алгоритмы могут эффективно решать многие задачи, но исследователи по-прежнему предпочитают неслучайные подходы. Мао разработал новый способ решения задачи поиска кратчайших путей без влияния случайности. Он присоединился к команде, и в течение следующих месяцев они работали вместе в групповых чатах и видеозвонках, объединяя свои идеи. Наконец, осенью Дуань понял, что они могут адаптировать метод из алгоритма, разработанного им в 2018 году, который преодолел барьер сортировки для другой задачи на графе. Этот метод был последним, что им было нужно для алгоритма, работающего быстрее алгоритма Дейкстры как на ориентированных, так и на неориентированных графах.
Готовый алгоритм разбивает граф на слои, двигаясь от источника наружу, как алгоритм Дейкстры. Но вместо того, чтобы обрабатывать всю границу на каждом шаге, он использует алгоритм Беллмана-Форда для определения влиятельных узлов, движется вперёд от этих узлов, чтобы найти кратчайшие пути к другим, и позже возвращается к другим граничным узлам. Он не всегда находит узлы внутри каждого слоя в порядке увеличения расстояния, поэтому барьер сортировки не применяется. И если разбить граф правильно, он работает немного быстрее, чем лучшая версия алгоритма Дейкстры. Он значительно сложнее, полагается на множество частей, которые должны быть идеально подогнаны друг к другу. Но, что любопытно, ни одна из частей не использует замысловатую математику.
«Это открытие вполне могло бы быть обнаружено 50 лет назад, но этого не произошло», — сказал Торуп. «И это делает его ещё более впечатляющим».
Дуань и его команда планируют изучить, можно ли оптимизировать алгоритм, чтобы сделать его ещё быстрее. После преодоления барьера сортировки время выполнения нового алгоритма не приближается ни к одному из известных специалистам по информатике фундаментальных пределов.
«Будучи оптимистом, я не удивлюсь, если вы сможете сделать это ещё короче», — сказал Тарьян. «Я определённо не думаю, что это последний шаг в этом процессе».
Источник: www.quantamagazine.org
