第211篇 A算法变体——Weighted A/ARA/D的工程应用

郑伟强dev

23人浏览 · 2026-08-19 04:28:36

郑伟强dev · 2026-08-19 04:28:36 发布

上一篇讲了启发式函数的设计。今天讲A的几个重要变体——它们在实际工程中用得比原版A还多，面试也经常考。

标准A*保证最优解，但有时候"最优"不是最重要的——"快"才是。比如移动机器人实时避障，你给它0.5秒算路径，它需要的是"一条能走的没碰撞的路"，不是"绝对最短的路"。这些变体就是在"最优性"和"速度"之间做不同的权衡。

一、Weighted A*——牺牲最优性换速度

Weighted A*是最简单的变体：把启发式乘以一个权重w > 1。

f(n) = g(n) + w * h(n)  # w > 1

w越大，搜索越"贪心"——越倾向于朝终点方向走。极端情况下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和D Lite——动态环境增量搜索

标准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优势不明显