Исследователи из Пекина предложили алгоритм поиска кратчайших путей, который обходит Дейкстру

Почти 70 лет ученые пытались сломать барьер сортировки для этой задачи. В данной работе это получилось впервые. Разбираемся ⬇️

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

Из-за этой упорядоченности и возник так называемый «барьер сортировки». Считалось, что перебить его невозможно.

Но вот, что сделали авторы тут:

1. Делим задачу на подзадачи с ограничением по максимальному расстоянию, до которого считаем пути.
2. Сжимаем «фронтир»: из вершин на границе уже найденных путей оставляем только небольшое число ключевых (пивотов).
3. Рекурсивно обрабатываем только пивоты и их ближайшие вершины, избегая полной сортировки.
4. Для остальных вершин добиваем расстояния несколькими шагами по всем рёбрам (метод в духе Беллмана–Форда).
5. Повторяем процесс, постепенно уточняя расстояния до всех вершин.

Итого, сложность Дейкстры – O(m + n log n), а BMSSP – O(m log^(2/3) n). Во втором случае логарифм растет заметно медленнее.

Что это все значит для ML? Может показаться, что ничего. Но на самом деле алгоритм Дейкстры вездесущий. Например:

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

Вот так как-то. Исторический день, получается.

Статья полностью тут, почитайте обязательно