上一篇讲了启发式函数的设计。今天讲A的几个重要变体——它们在实际工程中用得比原版A还多，面试也经常考。
标准A*保证最优解，但有时候"最优"不是最重要的——"快"才是。比如移动机器人实时避障，你给它0.5秒算路径，它需要的是"一条能走的没碰撞的路"，不是"绝对最短的路"。这些变体就是在"最优性"和"速度"之间做不同的权衡。
一、Weighted A*——牺牲最优性换速度
Weighted A*是最简单的变体：把启发式乘以一个权重w > 1。
f(n) = g(n) + w * h(n) # w > 1w越大，搜索越"贪心"——越倾向于朝终点方向走。极端情况下w=无穷大，退化成贪心最佳优先搜索（只看h(n)）。
有界次优性：Weighted A*找到的路径代价不超过最优路径的w倍。这是它的理论保证，也是工程上敢用的原因。
# Weighted A* 示例 def weighted_astar(graph, start, goal, heuristic, w=2.0): open_set = [(0, start)] g_score = {start: 0} came_from = {} while open_set: f, current = heapq.heappop(open_set) if current == goal: return reconstruct_path(came_from, current) for neighbor, cost in graph[current]: tentative_g = g_score[current] + cost if tentative_g < g_score.get(neighbor, float('inf')): came_from[neighbor] = current g_score[neighbor] = tentative_g f_score = tentative_g + w * heuristic(neighbor, goal) heapq.heappush(open_set, (f_score, neighbor)) return None工程上w通常取1.5-5.0。w=2是个不错的起点——速度快一倍，路径长度增加不超过100%。实际测试中w=2通常路径只增加10-30%，但搜索时间减少50%以上。
二、ARA*——动态调整权重
ARA（Anytime Repairing A）的思路很巧妙：先用大的w快速找到一个可行解，然后逐步减小w，在已有解的基础上改进。
# ARA* 伪代码 w = 5.0 # 初始权重 while w > 1.0: path = weighted_astar(graph, start, goal, h, w) if time_exceeded(): break w -= 0.5 # 逐步减小权重 # 返回当前最好的路径ARA*的特点：
- anytime算法——任何时候中断都能返回一个可行解
- 解的质量随时间逐步提高
- 适合有时间限制的场景（比如"给你2秒，尽量找到最好的路径"）
ARA的每一轮迭代叫做一个"inflation"——用当前权重w跑一遍Weighted A，然后减小w再跑。每轮迭代都利用上一轮的结果，不用从头搜索。这使得ARA比"多次独立跑Weighted A"效率高很多。
工程上ARA用得相对少一些——大多数场景要么需要最优解（用A），要么需要快速可行解（用Weighted A）。ARA适合那种"时间充裕但想尽量优化"的场景，比如离线路径优化。
三、D和DLite——动态环境增量搜索
标准A*有个大问题：环境一变，就得从头搜索。在动态环境中（比如移动机器人遇到新障碍物），这太浪费了。
D* Lite解决了这个问题。核心思想：增量搜索——环境变化后，只更新受影响的部分，不用从头来。
D* Lite的工作方式：
- 从终点反向搜索到起点（和A*方向相反）。为什么反向？因为机器人移动时起点在变，终点不变。反向搜索只需要一次，正向移动时增量更新。
- 机器人沿路径移动时，如果发现新障碍物（传感器检测到），只更新局部地图中受影响的节点
- 基于更新后的地图，增量修改搜索树——只重新计算"不一致"的节点
增量搜索的核心概念是每个节点维护两个值：g(s)（当前估计的最短距离）和rhs(s)（一步lookahead的最短距离）。当g(s) != rhs(s)时，节点是"不一致"的，需要重新计算。环境变化只影响变化点附近的节点，所以增量更新很快。
# D* Lite的核心概念 # 每个节点维护两个值： # g(s): 当前估计的最短距离 # rhs(s): 一步 lookahead 的最短距离 # rhs(s) = min(cost(s, s_next) + g[s_next]) for all successors # 当 g(s) != rhs(s) 时，节点"不一致"，需要更新 def is_consistent(s): return g[s] == rhs[s] def update_vertex(s): rhs[s] = min(cost(s, s_next) + g[s_next] for s_next in successors(s)) if g[s] != rhs[s]: add_to_queue(s)D* Lite的优势：
- 环境变化后，重新规划的时间远小于从头搜索
- 在变化不大的环境中，增量更新只需修改很少的节点
- 是自动驾驶和移动机器人最常用的全局规划算法之一
- 理论完备——有最优性和复杂度的严格证明
四、工程选型
| 场景 | 推荐算法 | 原因 |
|---|---|---|
| 静态环境，需要最优解 | A* | 保证最优 |
| 静态环境，速度优先 | Weighted A* | 快，有次优保证 |
| 有时间限制，越算越好 | ARA* | anytime特性 |
| 动态环境，频繁变化 | D* Lite | 增量更新 |
| 动态环境，变化很大 | 重新跑A* | D* Lite优势不明显 |
之前做移动机器人的项目，用的是D* Lite。仓库环境里偶尔会有人临时放的货物箱，传感器检测到新障碍物后，D* Lite只需要更新障碍物周围的十几个节点，而重新跑A*要搜索几千个节点。差距非常明显。
五、面试实战
Q：Weighted A*的次优保证是什么意思？A：找到的路径代价 <= w * 最优代价。比如w=2，最优路径长度100，Weighted A*找到的路径长度不超过200。
Q：DLite和A的主要区别是什么？** A：A每次环境变化都从头搜索。DLite从终点反向搜索，环境变化后增量更新。在变化不大的动态环境中，D* Lite比A*快很多。
Q：什么时候该用DLite而不是重新跑A？** A：当环境变化很小时（比如只有一两个格子变了），D* Lite的增量更新很快。当环境变化很大时（比如一半地图都变了），D* Lite的增量更新可能比重新搜索还慢。经验法则：变化量小于10%用D* Lite，大于10%重新搜索。
Q：ARA*的anytime特性是什么意思？A：anytime算法在任何时刻中断都能返回一个可行解。ARA*先用大权重快速找到解，然后逐步改进。如果时间到了就返回当前最好的解。这个特性在嵌入式系统中很有用——中断信号来了就停，不会"算到一半什么都没有"。
小结
A的变体在"最优性"和"速度"之间做不同的权衡。Weighted A最简单——乘以权重就行，工程上最常用。ARA是anytime算法——越算越好，适合离线优化。DLite适合动态环境——增量更新避免重复搜索，是移动机器人导航的标配。
工程上根据场景选择：静态环境用A或Weighted A，动态环境用D* Lite，有时间限制用ARA。大多数实际项目用Weighted A或D* Lite就够了。
下一篇讲D* Lite算法——动态环境中的增量路径规划，展开讲具体细节和实现。
如果这篇文章对你有帮助，欢迎点赞、在看、转发三连。 你的支持是我持续更新的最大动力。
「机器人软件开发面试·从入门到精通」连载系列
上一篇：第210篇 启发式函数设计——曼哈顿/欧几里得/对角线距离的选型
下一篇预告：第212篇 D* Lite算法——动态环境中的增量路径规划
有任何问题欢迎评论区留言，我会尽量回复。
