algorithm - 为什么这个曼哈顿启发式是可以接受的？

Question

在this解释 A* 算法的文章说，对于给定的问题(找到有墙作为障碍物的两点之间的最短距离)，曼哈顿距离是 Not Acceptable 。参见 this
这是为什么？在任何情况下它都会高估距离吗？如果是，什么时候？

Answer 1

这是来自 aStarLibrary.bb 的一个 block (从您的链接中获取链接)

;算出它的G成本 如果 Abs(a-parentXval) = 1 并且 Abs(b-parentYVal) = 1 那么 addedGCost = 14 ;去对角线正方形的成本
否则
addedGCost = 10 ;去非对角正方形的成本
万一 Gcost(a,b) = Gcost(parentXval,parentYVal)+addedGCost

    ;Figure out its H and F costs and parent
    Hcost(openList(m)) = 10*(Abs(a - targetx) + Abs(b - targety)) ; record the H cost of the new square

从 (0, 0) 到 (1,1) 的移动的启发式 (Hcost) 将为 10 * (1 + 1) = 20。GCost(移动成本)将此视为单个对角线移动成本 14。所以是的，这是一个高估。