4. 启发式搜索：A*算法详解、启发函数的设计与变种
各位同学好，今天我们聊一个在路径规划里绕不开的话题——A*算法。说实话，我入行那会儿，第一个真正让我觉得「哇，这玩意儿有点意思」的算法就是A*。它不像Dijkstra那样盲目地往四周扩散，也不像贪心算法那样容易撞南墙。A*聪明就聪明在，它知道往哪个方向走更有可能找到目标。
嗯，咱们今天就把A*拆开揉碎了讲。从基本原理，到启发函数怎么设计，再到几个实用的变种。我保证，听完这节课，你不仅能手撕A*，还能根据实际场景调教它。
4.1 A*算法的核心思想
A*本质上是一种启发式搜索算法。它维护一个开放列表（Open List），每次从里面挑一个「代价最小」的节点来扩展。这个代价由两部分组成：
- g(n)：从起点到当前节点n的实际代价
- h(n)：从当前节点n到目标节点的估计代价（启发函数）
总代价 f(n) = g(n) + h(n)。A*每次选择f(n)最小的节点进行扩展。
这里有个关键点：h(n)必须满足可采纳性（Admissible），即它不能高估到目标的实际代价。只有这样，A*才能保证找到最优路径。我在项目中遇到过有人把h(n)设得特别大，结果A*直接退化成贪心算法，路径虽然快但经常不是最优的。
核心公式回顾：
f(n) = g(n) + h(n)
其中h(n) ≤ h*(n)，h*(n)是到目标的真实代价。
4.2 启发函数的设计
启发函数的设计，说白了就是你怎么估计「还有多远」。不同的地图类型，适合不同的距离度量。我个人的经验是，选对了启发函数，A*的效率能差出好几倍。
4.2.1 曼哈顿距离
曼哈顿距离适用于四方向移动（上下左右）的网格地图。计算公式很简单：
h(n) = |x1 - x2| + |y1 - y2|为什么叫曼哈顿？你想想看，在纽约曼哈顿的街道上开车，你只能沿着横平竖直的街道走，不能斜着穿楼。这个距离就是曼哈顿距离。
适用场景： 城市道路、仓库AGV、四方向移动的机器人。
我的小技巧： 如果地图允许对角线移动，曼哈顿距离会低估实际代价，导致A*扩展更多节点。这时候可以考虑用切比雪夫距离或者欧几里得距离。
4.2.2 欧几里得距离
欧几里得距离就是直线距离，适用于任意方向移动的场景：
h(n) = sqrt((x1 - x2)² + (y1 - y2)²)这个距离是可采纳的，因为它永远不会高估实际代价（直线是最短的）。但有个问题——它计算起来有开方运算，比曼哈顿距离慢一些。不过现在CPU算力强，这点差别基本可以忽略。
我曾经在一个无人机航迹规划项目里用过欧几里得距离。无人机可以在三维空间任意飞行，用欧几里得距离做启发函数，效果很好。但要注意，如果地图里有障碍物，直线距离可能严重低估实际绕路代价，这时候A*会扩展很多不必要的节点。
4.2.3 对角线距离
还有一种折中的方案——对角线距离，适用于八方向移动的网格：
dx = |x1 - x2|
dy = |y1 - y2|
h(n) = min(dx, dy) * D2 + (max(dx, dy) - min(dx, dy)) * D1其中D1是直线移动代价，D2是对角线移动代价。这个距离比曼哈顿更准确，又比欧几里得计算快。
| 启发函数 | 适用移动方式 | 计算速度 | 准确性 |
|---|---|---|---|
| 曼哈顿距离 | 四方向 | 快 | 中等 |
| 欧几里得距离 | 任意方向 | 慢（有开方） | 高 |
| 对角线距离 | 八方向 | 快 | 高 |
4.3 A*的变种
标准A*虽然好，但实际工程中往往需要根据需求做调整。我给大家介绍两个我常用的变种。
4.3.1 Weighted A*（加权A*）
加权A*的核心思想很简单：给启发函数加一个权重ε（ε > 1）。
f(n) = g(n) + ε * h(n)这样做的好处是：搜索速度更快，但代价是路径可能不是最优的。ε越大，算法越「贪心」，搜索越快，但路径质量越差。
我记得有一次做仓储机器人的路径规划，要求实时性很高。标准A*算一条路径要200ms，但业务要求50ms以内。我用了Weighted A*，ε取1.5，路径只比最优长了3%，但计算时间降到了30ms。这就是典型的用精度换速度。
注意： ε不能太大。我见过有人取ε=10，结果路径绕了老大一圈，机器人差点撞墙。一般建议ε在1.2到2.0之间。
4.3.2 ARA*（Anytime Repairing A*）
ARA*是Weighted A*的进阶版。它解决了一个实际问题：如果时间充裕，能不能逐步优化路径？
ARA*的思路是：
- 先用一个较大的ε（比如5）快速找到一条可行路径
- 然后逐步减小ε，在剩余时间内不断优化路径
- 时间到了，就输出当前最好的路径
这个算法在自动驾驶、机器人实时规划中非常实用。你想想看，如果车在高速上跑，你不可能停下来等A*算完最优路径。ARA*可以保证在任何时刻都有一条「可用」的路径，时间越多路径越好。
我曾经在自动驾驶项目中用过ARA*。车辆在高速上以120km/h行驶，规划周期只有100ms。我们用ARA*，初始ε=3，每次迭代ε减少0.5。结果在大多数情况下，都能在50ms内找到一条不错的路径，剩下的50ms用来优化。嗯，这个方案最终成功落地了。
4.4 本章知识体系
下面我用一张图来总结本章的核心内容。这张图展示了A*算法从基础到变种的完整脉络。
4.5 避坑指南
最后，我分享几个实际项目中踩过的坑，希望能帮你少走弯路。
- 启发函数不可采纳： 我曾经在一个项目中用了曼哈顿距离，但地图允许对角线移动。结果A*算出来的路径不是最优的，因为曼哈顿距离高估了实际代价。后来改成对角线距离就对了。
- Open List实现不当： 很多人用普通的列表来存Open List，每次找最小f(n)都要遍历一遍。当节点数上万时，这非常慢。我建议用二叉堆或者斐波那契堆来优化。
- 权重ε调得太大： 用Weighted A*时，ε=2以内通常没问题。超过3，路径质量下降很快。我建议从1.5开始试，逐步增大直到满足时间要求。
我的建议： 如果你刚开始学A*，先手写一个标准版本，用曼哈顿距离做启发函数。跑通之后，再尝试换启发函数、加权重、实现ARA*。一步一步来，别想一口吃成胖子。
好了，关于A*算法我们就讲到这里。记住，算法是死的，场景是活的。多动手、多调试，你才能真正掌握它。