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

Question

在这篇解释 A* 算法的文章中，它说对于给定的问题（找到有墙作为障碍物的两点之间的最短距离），曼哈顿距离是不可接受的。看到这个
为什么会这样？在任何情况下它是否高估了距离？如果是，什么时候？

Answer 1

这是来自 aStarLibrary.bb 的一个块（从您的链接开始）

;计算它的 G 成本 If Abs(a-parentXval) = 1 And Abs(b-parentYVal) = 1 Then addedGCost = 14 ;去对角方块的成本
Else
addedGCost = 10 ;去非对角方块的成本
End If Gcost(a,b) = Gcost(parentXval,parentYVal)+ addedG成本

    ;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 的单个对角线移动。所以，是的，这是一个高估。