根据这篇维基百科文章
如果启发式满足附加条件对于每个边缘图的(其中表示该边的长度),然后称为单调,或一致。在这种情况下,可以更有效地实现——粗略地说,没有节点需要被处理超过一次(见下面的封闭集)——和相当于以降低的成本运行 Dijkstra 算法
有人可以直观地解释为什么降低成本是这种形式吗?
根据这篇维基百科文章
如果启发式满足附加条件对于每个边缘图的(其中表示该边的长度),然后称为单调,或一致。在这种情况下,可以更有效地实现——粗略地说,没有节点需要被处理超过一次(见下面的封闭集)——和相当于以降低的成本运行 Dijkstra 算法
有人可以直观地解释为什么降低成本是这种形式吗?
计算时你在做什么:
因此,使用原始边缘值的重新计算()在 Dijkstra 的算法中,您本质上是通过合并 A* 的启发式组件() 转化为所遍历的边的值,并丢弃 () 路径中先前节点的累积先前启发式值。
附加条件确保新的边缘值严格为正。