gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-12-04 10:29:21 25 4
gpt4 key购买 nike

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

    关于artificial-intelligence - Dijkstra vs A* 结果路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/60475458/

    25 4 0
    Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
    广告合作:1813099741@qq.com 6ren.com