Есть ли более быстрые алгоритмы, чем Дейкстра?
Имеет ли ориентированный связный граф только с положительными весами ребер, существуют ли более быстрые алгоритмы для нахождения кратчайшего пути между двумя вершинами, чем Дейкстра, использующий кучу Фибоначчи?
Википедия говорит, что Дейкстра находится в O(|E| + |V| * log(|V|)) (используя кучу Фибоначчи).
Я не ищу оптимизацию, которая, например, вдвое меньше времени выполнения, а скорее алгоритмы, которые имеют разную временную сложность (например, переход от O (n * log n) к O (n)).
Кроме того, я хотел бы узнать ваше мнение о следующем подходе:
- Определите GCD всех весов ребер.
- Преобразуйте график в граф с равномерным весом ребер.
- Используйте BFS, чтобы найти кратчайший путь между двумя заданными вершинами.
Пример для пункта 2:
Представьте, что GCD равен 1. Тогда я бы преобразовал край
A--->B (вес ребра 3)
в
A->A'->A''->B (3-кратный вес ребра 1)
Это преобразование стоит постоянного времени и должно быть выполнено один раз для каждого края. Поэтому я ожидаю, что этот алгоритм будет в O(|E|) (преобразование) + O(|E| + |V|) (BFS) = O(2 * |E| + |V|) = O(|E| + |V|)
Спасибо, что нашли время, чтобы прочитать мой вопрос, и я надеюсь не тратить ваше время ^^. Хорошего дня.
4 ответа
Большой анализ, который вы сделали для своего алгоритма, глубоко ошибочен. Предположим, что все ребра являются простыми числами. Количество ребер в новом графе будет равно сумме всех весов. таким образом O(|E| + |V|) нового графика на самом деле O(W x |E| + |V|) в исходном графике, который может быть намного больше, чем O(|E| + |V| log |V|),
Есть ли более быстрые алгоритмы, чем Дейкстра?
Да. Вопрос не квалифицирован, чтобы требовать лучшей производительности во всех случаях, или даже в большинстве случаев. Для получения утвердительного ответа достаточно алгоритма с лучшей производительностью в одном случае.
Несмотря на то, что метод Беллмана-Форда обычно требует большего числа итераций по сравнению с методом Дейкстры, на практике метод Беллмана-Форда может быть лучше из-за меньших издержек на одну итерацию [Голден Б., 1976. "Алгоритмы кратчайшего пути: Сравнение, "Исследование операций, вып. 44, с. 1164-1168].
Цитата выше - от Дмитрия П. Берцекаса (март 1992 г.). "Простой и быстрый алгоритм исправления меток для кратчайших путей" (PDF). Сети, вып. 23, стр. 703-709, 1993. http://www.mit.edu/people/dimitrib/SLF.pdf. Получено 2008-10-01.
Короче говоря, моя претензия основана на интерпретации Берцекасом Голдена. Независимо от моего заключения или нет, вы можете найти Берцекаса интересным для его классификации алгоритма Дейкстры как метода установки меток, в отличие от методов коррекции меток.
Существует алгоритм, который имеет O(1): превратить веса в длины цепей и использовать кольца для ключей для узлов (реальные кольца для ключей, как те, что в вашем кармане). Соедините кольца для ключей с правильными цепями. Выберите два узла и вытяните их друг от друга.
Следуйте за туго натянутыми цепями от одного узла к другому. Это самый короткий путь.
Чтобы реализовать это как компьютерную программу, вам понадобятся два промышленных робота:)
Для более реального примера используйте оптимизацию колоний Ant, которая дает очень хорошие результаты за короткое время. Поскольку вы можете указать количество прогонов в этом алгоритме, вы можете решить, сколько времени он потратил (т. Е. Время выполнения зависит только от количества узлов), что дает вам O(n), но не гарантированный идеальный результат.
Всегда есть A*, и он происходит от иерархического A * и A* JPS.