tgoop.com/dereference_pointer_there/9975
Create:
Last Update:
Last Update:
Исследователи из Пекина предложили алгоритм поиска кратчайших путей, который обходит Дейкстру
Почти 70 лет ученые пытались сломать барьер сортировки для этой задачи. В данной работе это получилось впервые. Разбираемся
Классический Дейкстра устроен так: мы храним вершины в приоритетной очереди и итеративно выбираем ближайшую, проверяя рёбра и обновляя расстояния, если путь через текущее ребро короче. Узкое место тут как раз в необходимости постоянно поддерживать упорядоченность большой очереди вершин.
Из-за этой упорядоченности и возник так называемый «барьер сортировки». Считалось, что перебить его невозможно.
Но вот, что сделали авторы тут:
1. Делим задачу на подзадачи с ограничением по максимальному расстоянию, до которого считаем пути.
2. Сжимаем «фронтир»: из вершин на границе уже найденных путей оставляем только небольшое число ключевых (пивотов).
3. Рекурсивно обрабатываем только пивоты и их ближайшие вершины, избегая полной сортировки.
4. Для остальных вершин добиваем расстояния несколькими шагами по всем рёбрам (метод в духе Беллмана–Форда).
5. Повторяем процесс, постепенно уточняя расстояния до всех вершин.
Итого, сложность Дейкстры – O(m + n log n), а BMSSP – O(m log^(2/3) n). Во втором случае логарифм растет заметно медленнее.
Что это все значит для ML? Может показаться, что ничего. Но на самом деле алгоритм Дейкстры вездесущий. Например:
– В графовых нейросетях на основе расстояний между вершинами часто вычисляются самые важные фичи.
– Для всяких ML-алгоритмов для логистики просто незаменимо.
– И даже в RL есть применение. Например, при обучении роботов среда может быть представлена как граф состояний, в котором оптимальная политика – это кратчайший путь.
Вот так как-то. Исторический день, получается.
Статья полностью тут, почитайте обязательно
