第5章 搜索：在无数可能中找到答案
设想你站在一座陌生建筑的入口，目标是找到二楼的一间实验室。走廊在前方分叉，每扇门后可能还有通道。你可以沿一条路走到底，走不通再退回来；也可以先查看离入口最近的所有岔路；如果手里有平面图，还可以优先走向看起来离实验室更近的方向。
这几种办法都没有改变建筑本身，也没有创造新的通道。它们改变的是一件更有限、却极其重要的事：下一步把计算花在哪里。
早期 AI 研究者发现，很多表面上完全不同的任务都能这样描述。迷宫是在通道中找出口，证明定理是在合法推导中找一条证明，下棋是在未来局面中找一着好棋，行动规划是在动作序列中找一条到达目标的路线。只要能定义“现在在哪里”“可以做什么”和“怎样算成功”，求解就可以变成搜索。
但这个转换只完成了一半工作。规则清楚，不代表答案容易找到。真正的敌人是可能性的数量。
把问题装进四个盒子
先看一个小迷宫。机器不能像人一样指着纸面说“从这里绕过去”，它需要一套可以执行的描述：
- 初始状态（initial state）：从哪个格子出发，以及钥匙、门等相关条件最初怎样；
- 动作与转移（actions and transitions）：当前允许向哪里移动，执行后进入什么状态；
- 目标测试（goal test）：判断当前状态是否为出口；
- 路径代价（path cost）：走一步算多少代价，泥地、楼梯或收费道路是否更贵。
这四项共同定义一个搜索问题。算法从初始状态出发，执行合法动作，产生后继状态，直到找到满足目标测试的状态。
这里有一个常被忽略的区别。搜索树记录的是“怎样走到这里”，同一个位置可能经由不同路线多次出现；状态图记录的是“有哪些不同状态以及它们怎样连接”。如果程序只展开树而不记得访问过哪些状态，就可能在环路中反复兜圈。一个只有 20 个格子的迷宫，也能产生无限长的“向左、向右、向左、向右”路径。
核心机制
搜索把求解分成两层：问题表示规定有哪些候选和合法变化；搜索策略规定先检查哪些候选。算法只能在表示所给出的世界里寻找答案。
这也解释了为什么同一个现实任务会因表示不同而难度悬殊。导航状态若只是“所在城市”，无法表达必须在晚上前充电；若把时间、电量和道路状态全部加入，每个位置又会分裂成大量不同状态。表示太少，计划不可靠；表示太多，搜索可能变得难以承受。
四种寻找顺序
搜索算法最直接的差别，是从尚未展开的候选中先取哪一个。这个候选集合通常叫作边界（frontier）或开放表。
广度优先：先看最近的
广度优先搜索（breadth-first search, BFS）先展开距离起点一步的所有状态，再展开两步、三步。它像水面从投入石子的地方一圈圈扩散。
如果每一步代价相同，第一次找到目标时，路径所含步数最少。只要每个状态的分支有限而且答案位于有限深度，它也最终能找到答案。代价是内存：程序必须同时保存一整层候选，层数稍深，数量就可能非常大。
深度优先：沿一条路走到底
深度优先搜索（depth-first search, DFS）优先展开最新发现的状态。它只需记住当前路径和少量待选分支，内存通常较省，也可能幸运地很快撞上深处的答案。
可是，一条很深的错误道路会拖住它。在存在无限路径或环路时，未经限制的深度优先甚至可能永远不回来。即使找到答案，也不保证路径最短。
一致代价：先走总成本最低的路线
现实中的一步往往不等价。高速公路距离长但时间短，山路距离短却耗油。一致代价搜索（uniform-cost search）不按步数，而按从起点到当前状态的累计代价 \(g(n)\) 排序，每次展开 \(g(n)\) 最小的候选。
Dijkstra 在 1959 年发表的最短路方法，正体现了这种思想。(Dijkstra 1959年) 在有限图中，当边代价非负且算法正确更新更便宜的路径时，节点以最小累计代价被确定后，后来不会再出现更便宜的路线推翻它。若搜索空间可能无限，要保证算法最终到达有限代价的目标，通常还要求每一步代价至少为某个正数 \(\epsilon\)；否则，无穷多条接近零成本的路径可能一直排在目标前面。它能找到最低代价路径，但在不知道目标方向时，仍可能向四面八方扩展。
贪心最佳优先：只看起来离目标最近
如果已经有剩余代价估计 \(h(n)\)，最直接的用法是每次展开 \(h(n)\) 最小的候选。这叫作贪心最佳优先搜索（greedy best-first search）。它不考虑走到当前节点已经付出多少，只追逐眼前看起来最接近目标的方向。
启发式准确时，贪心策略可能迅速靠近目标；但一条看似接近的路线也可能已经付出很高代价，或在前方遇到障碍。它因此通常不保证找到最低代价路径，也可能被误导而展开大量节点。“贪心”描述的是优先级只看 \(h(n)\)，不是说算法随意选择。
A*：已经花了多少，还可能要花多少
如果我们能估计当前位置离目标还有多远，就可以把已知成本与未来估计放在一起。A* 使用的优先级是：
\[ f(n) = g(n) + h(n) \]
其中 \(g(n)\) 是从起点到节点 \(n\) 已经付出的真实代价，\(h(n)\) 是从 \(n\) 到目标的估计代价。(Hart 等 1968年)
在地图上，\(h(n)\) 可以是直线距离；在八数码问题中，可以统计方块离目标位置的距离。\(h(n)=0\) 时，A* 退化为一致代价搜索。估计越能识别有希望的方向，通常需要展开的节点越少。
| 策略 | 优先展开 | 主要优势 | 主要风险 |
|---|---|---|---|
| 广度优先 | 层数最浅 | 等步长时能找最少步路径 | 边界占用大量内存 |
| 深度优先 | 最新发现 | 内存较省，可能迅速到达深处 | 可能困在深路，不保证最优 |
| 一致代价 | \(g(n)\) 最小 | 满足代价条件时找到最低成本路径 | 不知道目标方向，扩展范围大 |
| 贪心最佳优先 | \(h(n)\) 最小 | 好的启发式可能很快接近目标 | 忽略已付代价，不保证最优 |
| A* | \(g(n)+h(n)\) 最小 | 好的启发式可显著聚焦搜索 | 依赖启发式，通常仍耗内存 |
技术深潜：A* 什么时候仍能保证最优
启发式听起来像“猜”，但猜测可以有严格边界。如果对任意节点 \(n\)，\(h(n)\) 从不高估到最近目标的真实最低代价，就称它是可采纳的（admissible）。
可采纳启发式允许低估，却不允许高估。若真实最低剩余代价是 5，它可以估计为 3 或 5，不能估计为 8。低估会让程序多检查一些节点；高估则可能把一条实际更便宜的路线排到后面，从而破坏最优性保证。
为什么这种限制有用？假设 A* 即将取出一个目标节点，目标的 \(h=0\)，所以它的 \(f\) 就是完整路径代价。若边界中还藏着更便宜的完整路径，那么这条路径上的某个未展开节点，其 \(g+h\) 不会超过那条更便宜路径的真实成本，因此应该更早被取出。这与“当前目标最先被取出”矛盾。
在图搜索中，还常要求更强的一致性（consistency）：对每条从 \(n\) 到 \(n'\)、代价为 \(c(n,n')\) 的边，
\[ h(n) \leq c(n,n') + h(n') \]
它相当于要求启发式满足一种三角不等式，使沿路径的 \(f\) 值不会下降。若实现把已展开节点永久关闭，一致性保证后来不必重新打开它；若实现允许在发现更小 \(g(n)\) 时重新打开节点，可采纳启发式仍可维持最优性，但可能重复工作。算法保证因此不仅取决于公式，也取决于重复状态怎样处理。
不过，“保证最优”不等于“实际很快”。如果 \(h\) 几乎总为 0，A* 仍会展开大量节点；如果状态数本身巨大，即使启发式不错，内存也可能先耗尽。工程中常用加权 A*、迭代加深或束搜索换取速度和内存，但这些改动可能放弃最优保证。
组合爆炸不是修辞
设每个状态平均有 \(b\) 个后继，最浅答案位于 \(d\) 步之后。粗略地看，搜索树最多会出现
\[ 1+b+b^2+\cdots+b^d \]
个节点。最深一层的 \(b^d\) 很快占据主导。若每步平均有 10 种选择，深度 6 大约已有一百万条长度为 6 的分支；深度 12 则达到万亿量级。计算机每秒检查很多节点，仍追不上指数增长。
国际象棋正是早期研究者喜爱的试验场。规则完整、胜负明确，但一盘棋的可能变化远超穷举能力。香农在 1950 年讨论了两类路线：尽可能完整地搜索较浅变化，或者只考察被评价函数认为值得研究的候选。(Shannon 1950年) 后者把人的棋局知识带进了搜索控制。
这时，“好算法”至少可能来自三个地方：
- 更少的合法动作，让分支因子变小；
- 更好的状态评价，让计算集中到有希望的方向；
- 更强的剪枝规则，证明某些分支不可能影响最终选择。
仅仅换一台更快的机器，通常只是把可搜索深度向前推几层。规模扩大之后，表示和启发式仍决定能否求解。
对手也在选择：极小化极大
迷宫不会故意把出口挪走，棋手却会选择对你最不利的回应。对于确定性、完全信息、两人零和且轮流行动的游戏，常用极小化极大（minimax）描述理想化决策。
轮到我方时，选择评价最高的后继；轮到对手时，假设对手会选择让我方评价最低的后继。算法把叶节点的评价逐层向上传递：我方层取最大值，对手层取最小值。它不是断言真实对手永不犯错，而是在最坏情况下选择有保障的行动。
alpha-beta 剪枝进一步记录两条界限。alpha 是我方目前已经能保证的最好结果，beta 是对手目前能迫使我方接受的最好上界。当某个分支已经不可能改变祖先节点的选择时，就不再展开它。剪枝不会改变完整 minimax 的答案，却能显著减少实际检查的节点；效果高度依赖走法排序，先检查好棋更容易尽早形成紧界限。
技术深潜：评价函数把知识放进了哪里
棋局通常无法搜索到终局，于是程序在固定深度停止，并用评价函数 \(V(s)\) 估计局面。早期跳棋和国际象棋程序会把棋子数量、位置、机动性等特征加权：
\[ \begin{aligned} V(s) &= w_1x_1(s)+w_2x_2(s) \\ &\quad+\cdots+w_kx_k(s) \end{aligned} \]
这里的 \(x_i\) 是设计者选出的局面特征，\(w_i\) 表示相对重要性。评价函数并不证明某方会赢，它把远处看不见的终局压缩成一个当前近似。
Arthur Samuel 的跳棋研究尤其重要，因为程序不只搜索，还利用自我对弈和已有棋谱调整评价。(Samuel 1959年) 这预示了搜索与学习的结合：搜索产生决策和经验，学习改善评价，改善后的评价又引导下一次搜索。
要判断系统能力来自哪里，必须把两部分分开看。搜索算法可能完全通用，真正的棋力却主要来自特征、权重、开局库和计算预算。后来从 AlphaGo 到大模型的测试时计算，仍会反复出现同一问题：能力不是单个算法名，而是表示、评价、学习和搜索预算的共同结果。
启发式为什么有效，又为什么会误导
启发式（heuristic）不是随便猜，也不是保证正确的规则。它是利用问题结构缩小实际探索范围的线索。
地图上的直线距离有用，是因为道路距离通常不会短于两点直线；定理证明中目标公式的结构有用，是因为某些规则更可能产生所需形式；棋局中的棋子价值有用，是因为物质优势与胜率经常相关。这些线索都不是答案本身。
启发式会在三个地方失败：
第一，估计与真实目标错位。导航若只最小化距离，可能选择耗时更长的拥堵路线；内容推荐若把点击当作满意，可能学会吸引注意而非真正有用。
第二，局部进展制造陷阱。每一步都看起来更接近目标，不代表整体路线更好。山谷中的登山者若只沿局部上坡走，可能到达较低的山峰。
第三，环境改变使经验失效。昨天畅通的道路今天施工，以往可靠的棋局模式在新规则下可能无效。启发式依赖的规律必须与当前任务相符。
因此，搜索系统的评估不能只报“找到了答案”。还要问：是否总能找到？找到的是不是最低代价？用了多少时间和内存？问题变大后怎样增长？启发式在哪些分布上建立，又在哪些条件下失效？
搜索没有替机器决定什么值得找
把任务写成搜索带来强大的统一视角，也容易产生一种错觉：只要计算足够多，任何问题都能从候选中搜出答案。
可是，搜索之前已经有人作出了关键决定。地图中有哪些道路？状态是否包含风险？代价是时间、金钱还是安全？什么叫目标已经达到？如果这些问题定义错了，算法可能非常高效地找到一个不合需要的答案。
这正是早期 AI 的下一道门槛。Logic Theorist 能搜索，是因为公式和推理规则已经被写成机器可操作的符号；棋类程序能搜索，是因为棋盘和合法走法边界清楚。现实世界中的知识却不总是以这种整齐形式出现。
第 6 章将把注意力从“怎样寻找”移到“拿什么来寻找”：事实怎样表示，规则怎样匹配，行动怎样规划，以及一个在积木世界中看似能流畅对话的系统，离真实世界的常识究竟还有多远。
本章小结
- 状态、动作、目标测试和路径代价共同定义搜索问题；搜索树还必须处理重复状态和环路。
- BFS、DFS、一致代价搜索和 A* 采用不同的候选展开顺序，因此在完备性、最优性、时间和内存上各有取舍。
- A* 用 \(g(n)+h(n)\) 结合已付成本与剩余估计；可采纳和一致启发式给出最优性条件，但不保证现实规模下足够快。
- 组合爆炸来自分支因子随深度的指数增长，单靠更快硬件不能消除。
- minimax 与 alpha-beta 把搜索扩展到对抗环境；评价函数和启发式把领域知识带入计算。
- 搜索策略只负责在给定表示中分配计算，不能替我们定义世界、代价与目标。
思考问题
- 如果导航软件分别以距离、时间、费用和安全为目标，同一条道路会怎样进入不同的最优路线？
- 一个启发式偶尔高估代价，却让 A* 平均快十倍，你会在什么任务中接受它？
- 下棋程序的强大应归功于搜索、评价函数还是硬件？怎样设计实验区分它们？
延伸阅读
- 香农的论文不仅讨论国际象棋，也清楚展示了为什么完整搜索不可行，以及评价函数怎样进入程序。(Shannon 1950年)
- Hart、Nilsson 与 Raphael 的 A* 论文适合理工科读者继续阅读最优性条件和启发式精度。(Hart 等 1968年)
- Samuel 的跳棋论文连接了搜索、特征评价和从经验改进，是机器学习史上的重要一手材料。(Samuel 1959年)
- P01 将在实践部分用小型迷宫比较搜索顺序、访问节点数和路径质量；理解后续正文不依赖先完成该实践。