曼哈顿寻路是否支持对角线移动？

Question

谁能解释一下曼哈顿距离度量是否支持对角线移动？

Answer 1

admissible heuristic绝不能高估距离。

考虑起点为 0,0，终点为 10,10。

曼哈顿距离度量为 10+10=20，如果允许对角线移动，则高估了真实距离。

因此，当允许对角线移动时，曼哈顿距离不是 A* 的可接受启发式。