假设您使用 A* 算法，其中启发式可能会高估剩余距离几米。最终的路径会不会比真正最短的路径长几公里？你能举一个发生这种情况的图的例子吗？它是什么样的图？ 欧氏(直线)距离可能高估剩余距离的场景是:
- 图的顶点位于平面上的 (x, y) 坐标，其中 x 和 y 是浮点型
- 图形的某些顶点之间存在某些浮点长度的弧。弧的长度不小于其顶点之间的欧几里得距离(但对于弯曲/非直弧可以更大)
- 但是，在运行 A* 算法时，您使用向下舍入的整数算术，而 A* 估计值向上舍入(这是不合理的，但这只是差异有多小的一个示例):因此您对每个弧的长度进行舍入向下舍入到整数米，然后将 A* 估计值向上舍入到整数米
是否有一个公式可以说明给定 A* 启发式高估剩余距离多少的上限，最终路径次优性的上限？
最佳答案
当 A* 检索到的部分答案(即到达目标的估计总距离最小的部分答案)实际上已达到目标时，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 的一种方法，但代价是返回更差的答案。
关于algorithm - 使用 A* 使用启发式算法可以找到多少次优路径，该启发式算法稍微高估了剩余距离？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26551024/