algorithm - 使用启发式算法的 A* 可以找到多少次优路径，它稍微高估了剩余距离？

Question

假设您使用 A* 算法，其中启发式算法可能会高估剩余距离几米。最终路径会不会比真正的最短路径长几公里？你能举一个发生这种情况的图的例子吗，它是什么样的图？欧几里德(直线)距离可以高估剩余距离的场景是:

• 图的顶点位于平面上的(x, y)坐标中，其中x和y是 float
• 图的某些顶点之间存在一些浮点长度的弧。弧的长度不小于其顶点之间的欧几里得距离(但对于弯曲/非直弧可以更大)
• 但是，在运行 A* 算法时，您使用向下舍入的整数运算，而 A* 估计值向上舍入(这是不合理的，但这只是差异有多么小的一个例子):所以您舍入每个弧的长度缩小到整数米，然后将 A* 估计向上舍入到整数米

在给定 A* 启发式算法高估剩余距离的上限的情况下，是否有一个公式可以说明最终路径次优性的上限？

Answer 1

A* 在它检索到的部分答案(这是达到目标的估计总距离最小的部分答案)实际上已经达到目标时返回。标准 A* 保证找到正确的答案，因为根据启发式的定义，所有估计的达到目标的总距离都是下限，因此没有其他答案可以做得更好。

假设实际上以总距离 T 结束的答案的启发式可以达到 KT，其中 K > 1。如果 A* 检索到成本为 KT 的答案并认为它已经成功，因为答案达到了目标，那么它可能不是最佳答案。我们知道仍然在池中的每个部分答案至少花费了 KT，但是由于启发式，具有启发式 KT 的答案实际上可能会变成总成本 T < KT 的答案(但不能变成任何更便宜成本的答案).因此，使用这种启发式算法，A* 返回的答案可能是最佳答案的 K 倍，但不会更多。

这实际上在 http://en.wikipedia.org/wiki/A 的维基百科条目中进行了总结。 _search_algorithm#Bounded_relaxation - 有意使用此类启发式算法是加速 A 的一种方法，但代价是返回更差的答案。