Чем алгоритм Дейкстры лучше алгоритма A * для поиска кратчайшего пути? - PullRequest
4 голосов
/ 13 февраля 2011

Чем алгоритм Дейкстры лучше алгоритма A * для поиска кратчайшего пути?

Ответы [ 2 ]

11 голосов
/ 13 февраля 2011

Не лучше найти кратчайший путь. Пока у вас есть допустимая эвристика для A *, она найдет закороченный путь быстрее, чем Дейкстра.

И, как отметил Мехрад в комментариях, A * превращается в Dijktras, если вы дадите ему эвристическую функцию, которая возвращает 0.

Статья в Википедии для A * содержит массу полезной информации обо всем этом.

3 голосов
/ 13 февраля 2011

Если вы хотите найти кратчайшие пути от данного исходного узла до всех узлов в графе, Dijkstra лучше, чем A *, поскольку Dijkstra в любом случае покрывает весь граф, если вы не остановитесь на конкретном цель. В отличие от простого Dijkstra A * является целевым алгоритмом и поэтому должен знать как исходный, так и целевой узел. Если вы хотите покрыть весь граф N узлами с помощью алгоритма A *, вам, в основном, нужно запустить алгоритм N раз от исходного узла.

Dijkstra также может быть лучше для поиска кратчайших путей от исходного узла до многих целей графика. В зависимости от местоположения целей (особенно расстояния от источника), количества целей M, размера графика, качества эвристики A * будет определенная точка безубыточности, в которой запуск одной Дейкстры лучше или менее эффективен, чем запуск M раз алгоритм A *.

Редактировать: Вдохновленный правильным критическим комментарием Мэтью, я перефразирую немного и добавляю замечания:

  • Дейкстра не лучше находит кратчайшие пути к всем узлам, чем A *. Правильно было бы: это не хуже, чем A *.
  • Чтобы найти кратчайшие пути к всем узлам с A *, нужно установить функцию, которая оценивает затраты для целевого узла, равными нулю (поскольку целевого узла нет). Установка функции, которая оценивает затраты для целевого узла равными нулю, делает A * идентичным Dijkstra; Дейкстра является частным случаем А *. (Сомнительно, чтобы алгоритм назывался все еще «A *» (а не просто «Dijkstra»), если функция установлена ​​в ноль, потому что наличие ненулевой функции является ядром A *.)
  • Когда мы пытаемся найти кратчайший путь ко всем узлам, мы также можем сказать: Дейкстры достаточно. Уточнение A * не является необходимым и не помогает нам здесь.
  • Последнее замечание также верно для поиска в графе, например: Найти узел, помеченный конкретным флагом, который находится ближе всего к данному исходному узлу. Поскольку вы не знаете цели заранее, невозможно определить функцию, которая оценивает затраты для искомого узла, поэтому A * (в более узком смысле ненулевой функции) неприменимо.
...