Дейкстра против А * результирующий путь

Question

Когда я запускаю Dijkstra и A * на разных графиках, потому что оба являются оптимальными алгоритмами, я всегда должен ожидать найти один и тот же путь, верно?

Как для следующего графика:

Узлы: S, A, B, C, D, E, G

Края и затраты: (S, A) = 1, (A, B) = 1 (B, C) = 1, (A, E) = 8, (A, D) = 6, (D, G) = 2

эвристика: h (S) = 6, h (C) = 7, h (B) = 6, h (A) = 5, h (D) = 2, h (E) = 1, h (G) = 0

Я нахожу S-> A-> D- > G как путь для обоих. Стоимость этого пути 9 и для Дейкстры, и для А *.

Это всегда так для любого графа, потому что оба являются оптимальными? Если я хочу сравнить эти два алгоритма, то, что я должен использовать в качестве статистики, кажется, что время одинаково?

Спасибо.

Answer 1

Это всегда так для любого графа, потому что оба являются оптимальными?

A * можно рассматривать как улучшенную версию алгоритма Дейкстры. Это может быть быстрее из-за heuristi c. Но A * является оптимальным , только если функция heuristi c допустимая , в противном случае A * может найти решение, которое является правильным, но, возможно, неоптимальным по сравнению в Дейкстра. Таким образом, ответ «да», если и только если вы тщательно выберете свой heuristi c.

Если я хочу сравнить эти два алгоритма, то, что я должен использовать в качестве статистики, время, по-видимому, совпадает с хорошо?

Это зависит. Хотите проанализировать качество получаемых путей алгоритмов или скорость их выполнения? Если ваш heuristi c хороший (ie. Допустимый), изменится только время выполнения. Вы можете реализовать оба и измерить время выполнения. Вы также можете проанализировать количество исследованных узлов.

Answer 2

Если кратчайший путь уникален , то любой правильный алгоритм кратчайшего пути должен найти именно этот путь.

На графиках, где существует несколько путей между началом и целью, которые имеют при одинаковой стоимости даже разные реализации одного и того же алгоритма не гарантируют нахождение одного и того же пути, потому что могут быть тонкие различия, например:

• Порядок обработки исходящих ребер из узла, когда он "explored".
• Порядок, в котором узлы одинакового значения отбрасываются из очереди приоритетов.
• Для A * разные правильные эвристики часто приводят к разным путям (одинаковой стоимости) из-за чтобы упорядочить очередь приоритетов по-разному.

Если я хочу сравнить эти два алгоритма, что я должен использовать в качестве статистики, время, по-видимому, тоже самое?

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