一、什么是「状态 + 转移」

先看一个具体的东西：迷宫。 状态就是「我站在哪个格子」，转移就是「往上下左右走一格」。这两句话一写出来， 图就有了——每个格子是一个点，能走通的两个格子之间连一条边。 这个套路能套在任何地方，只要你能回答三个问题：

二、两种走法：排队还是插队

搜索的过程永远是同一套循环： 从「待看的点」里取出一个，看它是不是终点，不是就把它的邻居加进「待看的点」。 差别只在「待看的点」用哪种容器。

三、把每格的代价算进去

迷宫里的格子不是一样好走的：有的地是平路，有的是泥。Demo 给每格随机配了 1 到 5 的代价， 于是「步数最少」和「总代价最小」变成了两个不同的问题。

四、给搜索一个方向感

Dijkstra 像水波，四面均匀地扩。 可目标在右下角，往左上扩出去的格子基本白看。A 就加一项： 每格的优先级不再是「已花的代价」，而是「已花代价 + 到终点的估计」。 估计用曼哈顿距离（横竖各差多少格，加起来）。 它一定不会大于真实剩余代价，因为每走一格至少花 1。这个性质叫可采纳，有了它， A 找到的路仍然最优。 然后是最有意思的一段：Demo 里标准 A* 一格都没省，685 对 685。

五、状态一多就守不住了

上面那张地图只有 900 格。 换成八数码，状态数是 9! 等于 36 万；换成 4 乘 4 的华容道，是 16! 约两万亿。搜索算法本身没错， 是图太大了，大到存不下、也走不完。 这个现象叫组合爆炸。它才是搜索这一行真正的敌人：

六、「最优化」在计算机里指什么

这一节的标题里有「最优化」三个字，值得单独说清。它有两个意思，而且经常被混着用。

七、动手 Demo：同一张地图，四种走法

核心就是 search 这一个函数，四种走法共用它：k=0 是 Dijkstra，k=1 是标准 A， k 取 3 就是「加权 A」。广度优先和深度优先在它上面，只是把优先队列换成队列和栈。 地图是 30 乘 30、22% 的格子是墙、每格另有 1 到 5 的通行代价。 注意看输出里「看了多少格」那一列——它是这一节的关键指标。

DIRS = ((-1, 0), (1, 0), (0, -1), (0, 1))

def nbrs(p):                           # 上下左右能走的格子
    r, c = p
    for dr, dc in DIRS:
        nr, nc = r + dr, c + dc
        if 0 <= nr < SZ and 0 <= nc < SZ and not blocked[nr, nc]:
            yield (nr, nc)

def search(k=0.0):
    """k 是估计的放大倍数：k=0 是 Dijkstra，k=1 是标准 A*。"""
    g = {START: 0}                     # 起点到各点的最小代价
    prev = {START: None}               # 记录「从哪来」，用来回推路径
    pq = [(0.0, START)]                # 优先队列，按优先级出队
    done, seen = set(), 0
    while pq:
        _, p = heapq.heappop(pq)
        if p in done:
            continue
        done.add(p); seen += 1
        if p == GOAL:
            break
        for n in nbrs(p):
            nd = g[p] + int(COST[n])
            if nd < g.get(n, 1e18):
                g[n] = nd
                prev[n] = p
                h = abs(n[0] - GOAL[0]) + abs(n[1] - GOAL[1])
                heapq.heappush(pq, (nd + k * h, n))
    return seen, rebuild(prev)

实跑输出：

--------------------------------------------------------------------
在 30 乘 30 的地图上找一条路
--------------------------------------------------------------------
==============================================================

[1] 先说这张地图

  30 乘 30 共 900 个格子，其中 211 个是墙。每格另有 1 到 5 的通行代价，
  越贵越难走。从左上角 (0,0) 走到右下角 (29,29)，只能上下左右走。

  先看地图的样子（# 是墙，· 是通路，只印上面 18 行）：

    S···#··#·#··········#·······#·
    ·#··#····#·······#···#·······#
    #····#·#······#·###·#·····#··#
    ·······#·#····#·#········#····
    ·············#···##····#··#···
    ··#····#··#·#···##············
    ·#····#···············#·······
    #···##·····#···#······#·#···#·
    ·#··············###····#···#··
    ······#···#··##·······##······
    ··#·#···#·····#·#···#····#··#·
    ····#·········#·······##·····#
    ······#····#·##··##·##···#····
    ···##··········##·····##······
    ··####····###··············#·#
    ····#····##·##···#···##··#····
    ·#··········##·#·#········#·#·
    ···#······#·##····#··#·##·#·##

  **同一张图，不同的找法会走出不同的路，花不同的力气。**
  下面四种找法，看它们各自「翻了多少个格子」才找到终点。

[2] 广度优先：一层一层往外摊

  从 S 出发，先把一步能到的格子全看了，再看两步能到的，以此类推。
  它按「步数」一层层推，**第一次碰到 G 时，那条路的步数一定最少。**

    看了 685 个格子（全图 900 个），路径 58 步，代价 176

  这里的「最少」指步数，不是代价——它把 1 和 5 一视同仁。

[3] 深度优先：一条道走到黑

    看了 468 个格子，路径 150 步，代价 423

  **DFS 找到的路又长又绕**，因为它一头扎进去，撞墙才回头。
  可它有个好处：不用存「所有待看的格子」，内存只跟栈的深度有关。
  所以「有没有路」这种问题用它，**「哪条路最好」就不能用它。**

[4] Dijkstra：把代价算进去

  每次从「眼下最便宜」的格子里挑一个往外扩。
  **第一次碰到 G，那条路的代价一定最小。**

    看了 685 个格子，路径 60 步，代价 152

  跟广度优先比：步数从 58 变成 60，代价从 176 降到 152。
  多走两步，换回 24 的代价——**这就是「绕远走便宜的路」。**

  但也请注意它翻了多少格子：全图 689 个能走的格子里，它翻了 685 个，
  几乎把整张地图抄了一遍。这笔账不小。

[5] A*：给搜索加一个方向感

  Dijkstra 是四面均匀地扩，像水波。可目标在右下角，
  往左上扩出去的格子基本是白看的。

  A* 给每个格子算一个优先级：**已走代价 + 到终点的估计**。
  估计取曼哈顿距离。因为每格代价至少是 1，这个估计一定不大于真实剩余代价，
  这个性质叫「可采纳」，它保证了 A* 找到的路仍然最优。

    看了 685 个格子，路径 60 步，代价 152

  代价确实还是 152，格子却从 685 变成 685，只少了 0%。
  为什么没剪掉多少？因为这张图上每格的平均代价是 3.01，
  而曼哈顿估计是按每步 1 算的——估计值只有真实剩余代价的 33%。
  **估计太保守，队伍几乎没被压动，A* 就退化成 Dijkstra 了。**

[6] 把估计放大，看它在哪一步开始出错

  在优先级里把估计乘一个倍数 k。k=0 就是 Dijkstra，k=1 是标准 A*。

    k       看了多少格    路径代价    还是最优吗
    ----------------------------------------------
    0.0     685 个        152         最优（基准）
    0.5     685 个        152         是
    1.0     685 个        152         是
    2.0     483 个        152         是
    3.0     108 个        162         不是，多了 10
    5.0     89 个         161         不是，多了 9

  看这三段：

  k 从 0 到 1，格子数几乎不动，代价一直是 152。因为估计仍远低于真实，
  只是把出队的顺序微微调了一下。
  k 到 2，格子掉到 483 个，代价**还是** 152。
  因为真实平均代价 3.01，估计乘 2 之后依然不高估，可采纳性还没丢。
  k 到 3，格子只剩 108 个，代价涨到 162。
  这时候估计已经高估了真实剩余，可采纳性破了，**快是快了，可答案不再是最好。**

  **这一节要讲的一对矛盾就在这儿：**
  估计越贴近真实，剪得越狠；可一旦估过头，就再也保证不了最优。
  A* 的全部讲究，全落在这一条线上。

[7] 五种找法摆一起

    找法        看了多少格    路径步数    路径代价    最优吗
    ----------------------------------------------------------------
    广度优先    685 个        58          176         步数最优
    深度优先    468 个        150         423         不保证
    Dijkstra    685 个        60          152         代价最优
    A*（k=1）   685 个        60          152         代价最优
    A*（k=3）   108 个        60          162         不保证

  **这五行里没有一行是「又快又对」的免费午餐：**
  广度优先快在步数上，代价差；深度优先两样都不占；
  Dijkstra 对，但把地图翻了个遍；标准 A* 对，可这张图上没占着便宜；
  k=3 的 A* 快，代价却比最优多了 10。

  最后说这一节真正想落到的事：
  上面这四种，在算法书上叫「图搜索」，在人工智能书上叫「状态空间搜索」。
  名字不同，做的事一模一样——**都是把问题写成「状态 + 转移」，**
  再从一种状态出发沿着转移去找另一种状态。
  迷宫是这样，八数码是这样，下棋的每一步也是这样。
  **「最优化」在计算机里的第一层意思，就是在状态图上找一条最好的路。**

先把一句话记住：g[n] 记的是真实已花代价，优先队列的键可以是别的。这两件事必须分开， 否则会出大问题。我第一版就是混在一起写的：把「已花代价 + 估计」当成已花代价往下传， 结果 A* 的代价算成了 155，比 Dijkstra 的 152 还差——一个本来保证最优的算法给出了更差的答案。 这属于「参数对了、逻辑错了」，跑起来不报错，只能靠对答案发现。 第二个坑在「看了多少格」这个指标上。它算的是出队次数， 而同一个格子可能被多次塞进队列（每次找到更便宜的走法就塞一次）。 所以代码里要用 done 集合挡掉重复出队，否则这个数会虚高好几倍。 第三段那张 k 表是这一节的核心证据。k 从 0 到 1， 格子数纹丝不动——因为曼哈顿估计太保守，压不动队列。k 到 2 才见效（483），k 到 3 就翻车（162）。 这条曲线说明「启发函数的强弱」不是玄学，是可以量出来的。 最后那张五行表里没有一行是「又快又对」的免费午餐。广度优先快在步数上、代价差； 深度优先两样都不占；Dijkstra 对，但把地图翻了个遍；标准 A 对，可这张图上没占着便宜。 所以选算法从来不是选「最好的那个」，而是选「在你的数据上不吃亏的那个」。*

30 秒实验

1. 把墙的比例从 22% 调到 5%，重跑。 格子的平均代价不变，但通路变多，Dijkstra 翻的格子会变多（能到的地方更多了）， A* 和它的差距也会变。这一步能让你看见： 「看了多少格」这个指标跟地图的形状关系极大，不是算法的固有属性。
2. 把 COST 全部设成 1（每格一样贵），重跑。这时候 Dijkstra 的代价就等于步数， 和广度优先的结果完全一样——因为「代价最小」退化成了「步数最少」。顺手看 A： 每格都是 1 的时候，曼哈顿估计正好等于真实剩余代价，它会把格子数压到很低。*同一个估计函数， 换个数据，强弱完全变了。
3. 把 COST 的取值范围从 1 到 5 改成 1 到 2，重跑第三段。 平均代价从 3 掉到 1.5，标准 A* 应该开始明显省格子了。 这说明「A* 好不好用」取决于「估计跟真实差多少」，跟算法本身无关。

常见误区

1. 以为 A* 一定比 Dijkstra 快。它只是「在有好的估计函数时」更快。 估计函数弱的时候，它跟 Dijkstra 一模一样（Demo 里 685 对 685）； 估计函数估过头的时候，它更快但答案不对。
2. 以为搜索就是「遍历」。遍历是「把所有点看一遍」，搜索是「找到一个点就停」。 两者的终止条件完全不同，所以复杂度分析也不能混着说。
3. 以为「最优」是个绝对的说法。Demo 里 Dijkstra 的最优是「总代价最小」， 广度优先的最优是「步数最少」，A(k=3) 连最优都不是。 说「这个算法最优」之前，一定要先说清「按什么最优」。*
4. 以为状态空间搜索只用于游戏和迷宫。编译器做寄存器分配、快递公司排路线、芯片布线、 甚至证明数学定理，底下都是这一套。凡是「一步一步选，选到最后有个结果」的事，都能这么写。

搜索的规矩是「一步一步必须走通」， 可有些问题根本没有「一步一步」这回事——比如「找一组参数让这个函数最大」，参数连续，走不到底。 下一节的遗传算法就是为这种问题准备的：不走路，改去「繁殖」。

• ☐ （本节完，下一节 5.3 遗传算法）

相关笔记

• 图论
• 遗传算法
• 人工智能
• 📘 图解人工智能 · 索引