4、启发式函数设计：曼哈顿距离、欧几里得距离、切比雪夫距离、对角线距离的对比与选择

好，咱们今天聊点实在的。启发式函数，说白了就是A*算法的“导航仪”。你给它一个目标，它告诉你“大概还有多远”。选对了，路径又短又省时间；选错了，要么绕远路，要么跑断腿。

我在嵌入式平台上调A*的时候，踩过不少坑。有一次在STM32上跑路径规划，用的曼哈顿距离，结果机器人老走“L”型路线，明明直线能过去，它非要拐个直角弯。后来换了对角线距离，效果立竿见影。嗯，这里面的门道，咱们一个一个说。

4.1 四种距离的数学定义

先上公式，别怕，都是初中数学水平。

假设当前节点坐标是 (x1, y1)，目标节点是 (x2, y2)。令 dx = |x1 - x2|，dy = |y1 - y2|。

名称	公式	特点
曼哈顿距离	D * (dx + dy)	只允许上下左右移动
欧几里得距离	D * sqrt(dx² + dy²)	允许任意方向移动
切比雪夫距离	D * max(dx, dy)	允许8方向移动（国王走法）
对角线距离	D * (dx + dy) + (D2 - 2*D) * min(dx, dy)	允许8方向移动，且对角线代价更合理

这里 D 是直线移动的代价，D2 是对角线移动的代价。通常 D=1，D2=√2 ≈ 1.414。

4.2 曼哈顿距离：简单但有限制

曼哈顿距离是最常用的，也是我最早接触的。为什么？因为它没有乘法，没有开方，只有加减法。在嵌入式平台上，这简直是福音。

但你要注意，它假设你只能上下左右移动。如果你的地图允许斜着走，曼哈顿距离就会高估实际代价。高估意味着什么？意味着A*会多扩展节点，搜索变慢。

我曾经在一个四驱小车上用曼哈顿距离，结果路径规划出来全是直角弯。小车每次转弯都要减速，反而比走斜线慢。后来我改成对角线距离，路径平滑多了，时间也省了15%。

4.3 欧几里得距离：理论上最优，实际上最坑

欧几里得距离是直线距离，理论上最准确。但它在嵌入式平台上有个致命问题——开平方。

你想想看，A*算法每扩展一个节点就要算一次启发式。如果地图有1000个节点，就要算1000次sqrt。在Cortex-M4上，一次sqrt大概要几十个时钟周期。看起来不多？但A*的瓶颈往往就在这。

还有一个问题：欧几里得距离会低估实际代价（因为直线距离小于网格路径）。低估意味着A*会扩展更多节点，搜索范围变大。说白了，它既慢又不准。

4.4 切比雪夫距离：国王的走法

切比雪夫距离取 dx 和 dy 的最大值。它假设你可以像国际象棋里的国王一样，横着、竖着、斜着都能走，而且代价一样。

这个距离在8方向移动中表现不错，但有个小问题：它认为斜着走和直着走代价相同。实际上，斜着走应该比直着走远一点（√2 ≈ 1.414倍）。

所以切比雪夫距离会低估对角线移动的代价。低估的结果就是——路径可能不太平滑，算法会倾向于走斜线，哪怕直着走更合理。

4.5 对角线距离：我的首选

对角线距离是我个人最推荐的。它既考虑了8方向移动，又区分了直线和对角线的代价。

公式看起来复杂，但你可以这样理解：先走尽可能多的对角线，剩下的用直线补齐。

// 对角线距离计算（C语言实现）
float diagonal_distance(int dx, int dy) {
    const float D = 1.0f;      // 直线移动代价
    const float D2 = 1.414f;   // 对角线移动代价
    return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy);
}

这个距离是“可采纳”的，也就是说它永远不会高估实际代价。同时它又足够准确，不会像曼哈顿距离那样过度扩展节点。

4.6 如何选择？一张表说清楚

移动方式	推荐启发式	原因
4方向（上下左右）	曼哈顿距离	简单、快速、可采纳
8方向（允许斜走）	对角线距离	准确、可采纳、路径平滑
任意方向（自由移动）	欧几里得距离（带优化）	理论上最优，但需处理sqrt
8方向（代价相同）	切比雪夫距离	简单，但路径可能不平滑

4.7 嵌入式平台的实战建议

我个人在嵌入式项目中的选择顺序是这样的：

1. 首选对角线距离——大多数网格地图都是8方向移动，它最平衡。
2. 次选曼哈顿距离——如果地图是4方向，或者CPU实在跑不动。
3. 避免欧几里得距离——除非你有硬件浮点单元，或者地图非常小。
4. 切比雪夫距离作为备胎——当你需要极致的速度，且不介意路径质量时。

嗯，最后说一句。我曾经在一个项目中，把曼哈顿距离换成对角线距离，搜索节点数减少了40%，路径长度只增加了2%。这就是“性价比”的胜利。你想想看，是不是这个道理？