Sherfiter's wiki for fun

第 2 章 · 搜索与 A*

搜索是符号主义 AI 的发动机:把问题抽象成「状态空间中找一条从初始态到目标态的路」,剩下的是纯算法问题。迷宫、拼图、机器人路径、定理证明、乃至数独,全是同一个抽象。本章按「无信息搜索(只用问题本身)→ 有信息搜索(加上启发式)」的顺序推进,A* 是全章皇冠,也是游戏 AI 和机器人导航的行业标准。

2.1 形式化:把问题变成搜索问题

一个搜索问题四件套:

  • 状态:对世界的快照描述(迷宫里的坐标、拼图的盘面);
  • 初始状态与目标测试:从哪出发,怎样算到;
  • 动作与转移模型:每个状态能做什么,做完到哪;
  • 路径代价:每步的代价(默认 1,加权图另算)。

状态空间 = 从初始状态可达的全部状态的图。八数码难题(3×3 拼图)的状态空间 9!/2 = 181440 个状态,棋类大到天文数字——搜索的艺术一半在于「状态空间的定义」:表示得好,空间指数缩小(对称性剪枝、约束传播)。

2.2 无信息搜索:BFS、DFS、UCS

不借助任何「目标在哪」的知识,只有四种基本策略,各有明确的性能画像:

策略数据结构完备性最优性空间
BFS 广度优先队列(数据结构课第 3 章)是(分支有限)是(等步长)O(b^d) 可怕
DFS 深度优先栈/递归否(无限深)否O(bm) 省
迭代加深 IDS反复限深 DFS是是(等步长)O(bd) 兼得
UCS 一致代价优先队列(第 5 章堆)是(代价>0)是O(b^(C*/ε))

(b = 分支因子,d = 解的深度,m = 最大深度,C* = 最优代价。)

三个必懂的取舍。BFS 与 DFS 的空间之争:BFS 记住整层(指数内存),DFS 只记一条路径(线性内存)但可能掉进无限深渊;迭代加深是两者的和解:用「DFS 的空间」做出「BFS 的最优性」,代价是重复展开浅层节点(数学上重复的代价可忽略:树状展开时大头永远在最深层)。UCS 的本质:BFS 在「每步代价 1」时的特例,优先队列按路径代价 g(n) 弹出,处理加权图的最优解(数据结构课第 6 章 Dijkstra = UCS 的别名)。

2.3 启发式:给搜索装上眼睛

无信息搜索在迷宫里像无头苍蝇;启发式(heuristic)h(n) 是「从 n 到目标的估计代价」——估计,不要钱;准确,要命。好的 h 来自问题的松弛版:八数码的「错位棋子数」(忽略「一次只能移一格」的约束)、「曼哈顿距离」(忽略「不能斜穿」)。

贪心最佳优先:只按 h(n) 扩展,飞快但既不完备也不最优(一头扎向目标,可能撞墙绕远)。

UCS:只按 g(n)(已走代价),最优但瞎(均匀向四周扩散)。

A*:按 f(n) = g(n) + h(n) 扩展——「已花代价 + 预计剩余」,两者取长补短,这是 1968 年 Hart、Nilsson、Raphael 的发明,也是启发式搜索的完成式。

2.4 A* 的最优性:可采纳性定理

A* 用可采纳的启发式(never overestimate,h(n) ≤ 真实代价)保证找到最优解。证明思路(反证,第 4 章):设最优解代价 C*,但 A* 返回了代价 C > C* 的解;那么在终止前,最优路径上必有未扩展的节点 n,其 f(n) = g(n) + h(n) ≤ C*(可采纳性保证 h 不高估),而被弹出的解节点 f = C > C*,优先队列会先弹 n——矛盾。∎

**一致性(consistency)**是更强的条件:h(n) ≤ cost(n, n') + h(n')(三角不等式),一致则第一次弹出节点时即确定最优(无需重复扩展)。可采纳的 h 越大(越接近真实),剪枝越狠:h = 0 退化为 UCS,h = 真实代价直达答案。设计启发式 = 给问题找一个「松弛版的精确解」:八数码的曼哈顿距离、寻路游戏的对角线距离,全是这个套路。

2.5 实战:A* 走迷宫

网格迷宫的完整 A*(Python 伪码):

def astar(grid, start, goal):
    open_heap = [(h(start), start)]          # (f, 状态) 最小堆,第 5 章的堆
    g = {start: 0}
    while open_heap:
        f, cur = heappop(open_heap)
        if cur == goal:
            return reconstruct(g, cur)       # 回溯路径
        for nxt in neighbors(cur):           # 四方向
            ng = g[cur] + 1                  # 每步代价 1
            if ng < g.get(nxt, INF):
                g[nxt] = ng
                heappush(open_heap, (ng + manhattan(nxt, goal), nxt))

曼哈顿距离(|dx| + |dy|)在四向网格上是可采纳的(每步最多靠近一格)。工程变体:游戏地图的 JPS(跳点搜索,A* 的加速版)、机器人上动态更新(重规划 D* lite)、多目标的折中(权重 f = g + εh,牺牲一点最优换速度)。

常见认知误区

  • 「启发式是拍脑袋的猜测」。好的 h 有严格来源(松弛问题)和验证手段(可采纳性);拍脑袋的 h 会破坏最优性而不自知。
  • 「A 一定比 BFS 快」**。h = 0 时 A 就是 UCS;速度完全取决于 h 的质量。最坏情况仍是指数。
  • 忘了闭合集。已扩展节点不查重,同一节点被反复入堆,指数爆炸;g 字典就是闭合集。
  • 内存幻觉。A* 的空间仍是 O(b^d)(BFS 级);内存不够时用 IDA*(迭代加深 A*,空间线性)。

练习

  1. 手算:八数码某个盘面(画出),计算曼哈顿距离与错位棋子数两个 h 值;比较哪个更「贴」真实步数(手工推 3 步验证)。
  2. 动手:实现网格迷宫的 A*(本章代码补全:neighbors 与回溯),分别用 h = 0、h = 曼哈顿、h = 欧氏距离跑同一个 100×100 迷宫,统计扩展节点数,验证「h 质量决定速度」。
  3. 手算:证明「曼哈顿距离对四向网格可采纳」(第 4 章:每步 |dx|+|dy| 至多减 1,故真实代价 ≥ 曼哈顿距离)。
  4. 思考:无人车的路径规划为什么不能直接用 A*(提示:动态障碍、时间维度、车辆动力学约束),查一下「混合 A*」怎么改状态空间,体会「状态空间定义」的工程分量。
豫ICP备2026027944号