当我在不同的图上运行 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。
对于任何图表来说都是这样，因为两者都是最优的吗？ 如果我想比较这两种算法，我应该用什么来统计，时间似乎也一样？
谢谢。
最佳答案
如果最短路径是唯一，那么任何正确的最短路径算法都必须准确找到该路径。
在起点和目标之间存在具有相同成本的多条路径的图表中，即使同一算法的不同实现也不能保证找到相同的路径，因为可能存在细微的差异，例如:
- “探索”节点时处理节点传出边的顺序。
- 从优先级队列中弹出相同值的节点的顺序。
- 对于 A*，由于优先级队列的排序不同，不同的正确启发法通常会导致不同的路径(成本相同)。
If I want to compare these two algorithms, what should I use as statistics, time seems to be the same as well?
在足够大的图表上，当你有良好的启发式时，A* 最终会表现得更好。一个常见的例子是没有许多不可逾越的方 block 的网格，其中 Dijkstra 将大致探索一个圆圈，但 A*(如果给出适当的启发式)将近似瞄准目标并仅探索“粗线”。您可以在 this visualiation 上看到此效果的实际效果。 .
关于artificial-intelligence - Dijkstra 与 A* 结果路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/60475458/