Есть ли более быстрые алгоритмы, чем Dijkstra?
Необходимо думать RoboWar. О, насколько прекрасный это.
Все еще существует, хотя сообщество медленно умирает.
http://robowar.sourceforge.net/RoboWar5/index.html http://tech.groups.yahoo.com/group/robowar/
3 ответа
Большой анализ, который вы провели для своего алгоритма, глубоко ошибочен. Предположим, что все ребра - простые числа. Количество ребер в новом графе будет равно сумме всех весов. Таким образом, O (| E | + | V |) из нового графа на самом деле является O (W x | E | + | V |) в исходном граф, который может быть намного больше, чем O (| E | + | V | log | V |) .
Существуют ли более быстрые алгоритмы, чем Дейкстра?
Да. Вопрос не так квалифицирован, чтобы требовать лучшей производительности во всех случаях или даже в большинстве случаев. Алгоритм с лучшей производительностью в одном случае достаточно, чтобы получить утвердительный ответ.
Несмотря на обычно большее количество итераций, требуемых алгоритмом Метод Беллмана-Форда по методу Дейкстры, на практике метод Беллмана-Форда может быть лучше из-за меньших накладных расходов на итерацию [Golden, B., 1976. «Алгоритмы кратчайшего пути: сравнение», Operations Research, Vol. 44, pp. 1164-1168].
Цитата выше взята из Димитрия П. Бертсекаса (март 1992 г.). «Простой и быстрый алгоритм исправления меток для кратчайших путей» (PDF). Сети, Vol. 23, pp. 703-709, 1993. http://www.mit.edu/people/dimitrib/SLF.pdf . Проверено 1 октября 2008.
Короче говоря, мое утверждение основано на интерпретации Голдена Бертсекасом. Независимо от того, подтвердится мой вывод или нет, вы можете найти Бертсекаса интересным тем, что он классифицировал алгоритм Дейкстры как метод установки меток , в отличие от методов исправления меток .
Существует алгоритм, который имеет O (1): превратите веса в длины цепочки и используйте кольца для ключей для узлов (настоящие кольца для ключей, как те, что в вашем кармане). Соедините кольца для ключей с правильными цепочками. Выберите два узла и отодвиньте их друг от друга.
Следуйте туго натянутым цепям от одного узла к другому. Это кратчайший путь.
Чтобы реализовать это в виде компьютерной программы, вам понадобятся два промышленных робота:)
Для более реального примера используйте Оптимизацию колонии муравьев , которая дает очень хорошие результаты в короткие сроки. Поскольку вы можете указать количество прогонов в этом алгоритме, вы можете решить, сколько времени он потратил (т.е. время выполнения зависит только от количества узлов), что даст вам O (n), но не гарантирует идеальный результат.