3. 启发函数：距离度量的四种武器

聊到A*算法，启发函数绝对是灵魂所在。我刚开始学A*的时候，总觉得随便选个距离公式就行，结果跑出来的路径要么绕远路，要么干脆卡死。后来踩的坑多了，才明白——选对启发函数，比调参重要十倍。

说白了，启发函数就是给算法一个「方向感」。它告诉算法：目标大概在哪个方向，离我们还有多远。选得好，路径又短又快；选得不好，算法可能像个无头苍蝇。

3.1 曼哈顿距离（Manhattan Distance）

这是我最常用的距离度量，尤其是在网格地图里。它的定义很简单：

h(n) = |x1 - x2| + |y1 - y2|

你想想看，在只能上下左右移动的网格里，从A点到B点，最短路径不就是横着走几步、竖着走几步吗？曼哈顿距离算的就是这个。

适用场景：

• 四方向移动的网格地图（上下左右）
• 城市道路规划（街区式布局）
• 棋盘类游戏（如八数码问题）

3.2 欧几里得距离（Euclidean Distance）

这个大家最熟悉，就是直线距离：

h(n) = sqrt((x1 - x2)² + (y1 - y2)²)

嗯，这里要注意——欧几里得距离虽然直观，但在网格地图里反而容易出问题。为什么？因为实际路径不可能走直线，所以它总是低估距离。低估本身不是坏事，但会导致算法探索太多节点。

适用场景：

• 自由移动的连续空间（如无人机飞行）
• 八方向移动的网格（允许对角线移动）
• 3D空间路径规划

3.3 切比雪夫距离（Chebyshev Distance）

这个距离的定义很有意思：

h(n) = max(|x1 - x2|, |y1 - y2|)

说白了，就是取横纵坐标差的最大值。它模拟的是「国王在棋盘上移动」——国王可以横、竖、斜任意方向走，每步走一格，所以最短步数就是两个方向中较大的那个。

适用场景：

• 八方向移动的网格（允许对角线移动）
• 棋盘类游戏（国际象棋王、后的移动）
• 仓库机器人调度（可以斜向移动）

3.4 对角线距离（Diagonal Distance）

这个其实是切比雪夫距离的「修正版」。它考虑了斜向移动的成本：

dx = |x1 - x2|
dy = |y1 - y2|
h(n) = (dx + dy) + (√2 - 2) * min(dx, dy)

公式看着有点复杂，但逻辑很简单：先走对角线，剩下的再走直线。如果对角线移动成本是√2（约1.414），直线移动成本是1，那这个公式算的就是精确的最短路径长度。

适用场景：

• 八方向移动且对角线成本为√2的网格
• 需要精确启发值的场景
• 对路径质量要求高的应用

3.5 四种距离对比

距离类型	公式	适用移动方式	是否可采纳	搜索效率
曼哈顿距离	|dx| + |dy|	四方向	是	高
欧几里得距离	√(dx² + dy²)	任意方向	是	低（低估严重）
切比雪夫距离	max(|dx|, |dy|)	八方向（成本1）	是	高
对角线距离	dx+dy+(√2-2)*min(dx,dy)	八方向（成本√2）	是	中

3.6 知识体系总览

下面这张图，是我梳理的启发函数选择逻辑。你可以把它当作决策树来用：

这张图的核心逻辑很简单：先看你的地图允许什么移动方式，再决定用哪种距离。我个人习惯是——四方向无脑用曼哈顿，八方向优先切比雪夫，除非你对路径精度有变态要求才上对角线距离。

最后说一句：启发函数没有绝对的好坏，关键看你的应用场景。选对了，A*跑得又快又好；选错了，再好的算法也白搭。嗯，这就是我这些年总结出来的经验。

---

公众号:蓝海资料掘金营，微信deep3321