artificial-intelligence - Dijkstra vs A* 结果路径

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 作为两者的路径。
对于 Dijkstra 和 A*，这条路径的成本都是 9。

任何图形都是如此，因为两者都是最优的吗？
如果我想比较这两种算法，我应该使用什么作为统计数据，时间似乎也一样？

谢谢。

Answer 1

如果最短路径是唯一的，那么任何正确的最短路径算法都必须准确地找到该路径。

在起点和目标之间有多条路径具有相同成本的图上，即使同一算法的不同实现也不能保证找到相同的路径，因为可能存在细微的差异，例如:

在“探索”节点时处理来自节点的输出边的顺序。

从优先级队列中弹出等值节点的顺序。

对于 A*，由于优先级队列的排序不同，不同的正确启发式通常会导致不同的路径(等成本)。

If I want to compare these two algorithms, what should I use as statistics, time seems to be the same as well?

在足够大的图上并且当你有一个很好的启发式时，A* 最终会表现得更好。一个常见的例子是一个没有许多不可通行瓷砖的网格，其中 Dijkstra 将粗略地探索一个圆圈，但 A*(如果给出适当的启发式)将大致瞄准目标并仅探索“粗线”。您可以在 this visualiation 上看到这种效果。 .