A* 与 Dijkstra 相似,但成本降低

人工智能 比较 搜索 启发式 一个明星 dijkstras算法
2021-10-24 02:22:46

根据这篇维基百科文章

如果启发式h满足附加条件h(x)d(x,y)+h(y)对于每个边缘(x,y)图的(其中d表示该边的长度),然后h称为单调,或一致。在这种情况下,A可以更有效地实现——粗略地说,没有节点需要被处理超过一次(见下面的封闭集)——和A相当于以降低的成本运行 Dijkstra 算法d(x,y)=d(x,y)+h(y)h(x).

有人可以直观地解释为什么降低成本是这种形式吗?

1个回答

计算时你在做什么d(x,y)

  1. d(x,y):计算原始边缘距离xy
  2. h(y): 加上启发式y到目标
  3. h(x):减去启发式x到目标

因此,使用原始边缘值的重新计算(1.)在 Dijkstra 的算法中,您本质上是通过合并 A* 的启发式组件(2.) 转化为所遍历的边的值,并丢弃 (3.) 路径中先前节点的累积先前启发式值。

附加条件h(x)d(x,y)+h(y)确保新的边缘值严格为正。