3. 曼哈顿距离与切比雪夫距离：栅格地图的启发式代价对比
好，咱们今天聊点实在的。在栅格地图上做路径规划，启发式函数怎么选？
说白了，这就是给A*算法一个「方向感」。选对了，路径规划又快又准；选错了，要么绕远路，要么算到天荒地老。
我个人最常用的两种距离度量，就是曼哈顿距离和切比雪夫距离。它们各有各的脾气，今天我把它们的底细都给你抖出来。
3.1 曼哈顿距离：四方向移动的标配
先说说曼哈顿距离。这个名字来源于纽约曼哈顿的街道布局——你只能沿着横平竖直的街道走，不能斜穿。
公式很简单：D = |x1 - x2| + |y1 - y2|
什么时候用它？
- 你的机器人只能上下左右移动（四方向）
- 栅格地图不允许对角线移动
- 比如AGV小车在仓库里走直角路径
核心要点：曼哈顿距离是四方向移动的可采纳启发式。它永远不会高估实际代价，所以A*一定能找到最优解。
我在项目中遇到过一个问题：用曼哈顿距离做启发式，结果路径规划特别慢。后来发现，是因为地图太大，启发式值太小，导致A*扩展了太多节点。
我的小技巧：如果地图很大，可以给曼哈顿距离乘一个系数（比如1.001），稍微加速搜索。但别乘太大，否则会失去最优性保证。
3.2 切比雪夫距离：八方向移动的利器
切比雪夫距离允许你斜着走。公式是：D = max(|x1 - x2|, |y1 - y2|)
你想想看，在国际象棋里，国王走一步可以往任意方向移动一格。切比雪夫距离就是国王从一个格子到另一个格子需要的最少步数。
什么时候用它？
- 机器人可以八方向移动（上下左右+对角线）
- 比如扫地机器人、游戏中的NPC
- 对角线移动代价和直线移动一样
注意：如果对角线移动代价是√2（约1.414），而直线移动是1，那切比雪夫距离会低估实际代价。这时候需要改用对角距离：D = (√2 - 1) * min(dx, dy) + max(dx, dy)
嗯，这里要注意。我曾经踩过一个坑：在八方向地图上用了切比雪夫距离，结果A*找的路径看起来没问题，但实际走起来比最优路径长了10%。
为什么？因为我的机器人对角线移动代价是1.4，但切比雪夫距离假设对角线代价是1。启发式低估了实际代价，导致路径不是最优的。
3.3 两种距离的对比表格
| 对比维度 | 曼哈顿距离 | 切比雪夫距离 |
|---|---|---|
| 适用移动方式 | 四方向（上下左右） | 八方向（含对角线） |
| 公式 | |dx| + |dy| | max(|dx|, |dy|) |
| 是否可采纳 | 是（四方向下） | 是（对角线代价=1时） |
| 搜索效率 | 较慢（启发式值偏小） | 较快（启发式值更大） |
| 路径质量 | 最优 | 最优（条件满足时） |
| 典型应用 | 仓库AGV、迷宫 | 游戏AI、扫地机器人 |
3.4 代码实现对比
我习惯把这两种距离封装成函数，方便切换。给你看看我的代码：
# 曼哈顿距离
def manhattan_distance(a, b):
return abs(a.x - b.x) + abs(a.y - b.y)
# 切比雪夫距离
def chebyshev_distance(a, b):
dx = abs(a.x - b.x)
dy = abs(a.y - b.y)
return max(dx, dy)
# 对角距离（对角线代价为√2时用）
def diagonal_distance(a, b):
dx = abs(a.x - b.x)
dy = abs(a.y - b.y)
return (1.414 - 1) * min(dx, dy) + max(dx, dy)避坑指南：我曾经在项目中直接用切比雪夫距离，没考虑对角线代价差异。结果路径规划看起来很快，但实际路径比最优长了15%。后来改成对角距离，问题才解决。
记住：启发式函数必须和实际移动代价匹配，否则A*找到的路径可能不是最优的。
3.5 实战选择建议
说了这么多，到底怎么选？我给你几个经验法则：
- 四方向移动 → 曼哈顿距离。没得选，这是唯一正确的可采纳启发式。
- 八方向移动，对角线代价=1 → 切比雪夫距离。简单高效。
- 八方向移动，对角线代价=√2 → 对角距离。别偷懒，用这个。
- 地图超大，需要加速 → 加权启发式。比如曼哈顿距离乘以1.1，但要做好路径可能不是最优的心理准备。
我的个人习惯：在项目初期，我会先用曼哈顿距离做原型。等系统跑通了，再根据实际移动方式切换到更合适的距离度量。这样调试起来更省心。
最后说一句：距离度量没有绝对的好坏，关键看你的机器人怎么动。选对了，事半功倍；选错了，事倍功半。
下一章我们聊聊欧几里得距离和它的变种，那个更适合连续空间。到时候再给你分享几个我踩过的坑。