На днях прошла новость:
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Классический Дейкстра устроен так: мы храним вершины в приоритетной очереди и итеративно выбираем ближайшую, проверяя рёбра и обновляя расстояния, если путь через текущее ребро короче. Узкое место тут как раз в необходимости постоянно поддерживать упорядоченность большой очереди вершин.
Из-за этой упорядоченности и возник так называемый «барьер сортировки». Считалось, что перебить его невозможно.
Но вот, что сделали авторы тут:
1. Делим задачу на подзадачи с ограничением по максимальному расстоянию, до которого считаем пути.
2. Сжимаем «фронтир»: из вершин на границе уже найденных путей оставляем только небольшое число ключевых (пивотов).
3. Рекурсивно обрабатываем только пивоты и их ближайшие вершины, избегая полной сортировки.
4. Для остальных вершин добиваем расстояния несколькими шагами по всем рёбрам (метод в духе Беллмана–Форда).
5. Повторяем процесс, постепенно уточняя расстояния до всех вершин.
Итого, сложность Дейкстры – O(m + n log n), а BMSSP – O(m log^(2/3) n). Во втором случае логарифм растет заметно медленнее.
Что это все значит для ML? Может показаться, что ничего. Но на самом деле алгоритм Дейкстры вездесущий. Например:
– В графовых нейросетях на основе расстояний между вершинами часто вычисляются самые важные фичи.
– Для всяких ML-алгоритмов для логистики просто незаменимо.
– И даже в RL есть применение. Например, при обучении роботов среда может быть представлена как граф состояний, в котором оптимальная политика – это кратчайший путь.
Отсюда:
Исследователи из Пекина предложили алгоритм поиска кратчайших путей, который обходит Дейкстру
Здесь основная идея — это гибрид из алгоритма Дейкстры и алгоритма Беллмана-Форда.
Но если я все правильно понял, то в общем случае
* Новый алгоритм: O(m log²/³ n)
* Алгоритм Дейкстры: O(m + n log n)
1. Разреженные графы (Sparse Graphs): В таких графах количество рёбер m сопоставимо с количеством вершин n, то есть m ≈ n.
* Новый алгоритм: O(n log²/³ n)
* Алгоритм Дейкстры: O(n + n log n) = O(n log n)
* Вывод: В этом случае n log²/³ n растёт медленнее, чем n log n, поэтому новый алгоритм быстрее. Именно это и является его главным достижением, как указано в документе.
2. Плотные графы (Dense Graphs): В таких графах количество рёбер m близко к максимально возможному, то есть m приближается к n².
* Новый алгоритм: O(n² log²/³ n)
* Алгоритм Дейкстры: O(n² + n log n) = O(n²)
* Вывод: В этом случае n² растёт медленнее, чем n² log²/³ n. Поэтому на плотных графах алгоритм Дейкстры будет быстрее.
Получается что новый алгоритм эффективнее алгоритма Дейкстры на разреженных графах. Однако для плотных графов классический алгоритм Дейкстры остаётся более быстрым решением.
Так?
