搜索：在可能性空间里找路

导读：先说清“最好”指什么

从青桥去海门，要求“最少经过车站”“总用时最短”和“换乘最少”，可能得到三条不同路线。搜索算法并不理解乘客的完整处境；它只在建模者给出的状态、动作、目标和代价中安排检查顺序。经典教材也把这些要素作为搜索问题的基本部件。[1, Ch. 3, §§3.1–3.5]

本章要分开三个问题：完备性（completeness）问“若解存在，算法最终能否找到”；最优性（optimality）问“找到的解是否在指定代价下最好”；时间和内存代价则问“是否算得动”。这些性质都附带条件，不是算法名字自带的勋章，更不是机器具有通用思考能力的证据。

案例边界　青桥交通图、站名、边权和滑块局面均为本项目原创教学构造，不对应真实城市，也不提供出行建议。正文默认动作确定、环境已知；不确定性、对手和长期规划留待后章。

5.1 状态、动作、初始状态与目标

状态（state）是解决当前问题所保留的一份情形描述。地铁问题可以把“当前在青桥”作为状态；动作（action）是可从一个状态执行的操作，例如沿一段线路到相邻站；初始状态是出发情形；目标检验判断是否到达海门。由初始状态按允许动作可达的全部状态及其连接，构成状态空间（state space）。

状态不等于搜索节点（search node）。状态可能只写“在柳岸”，节点还记录由哪条路径抵达、父节点、深度和累计代价。两条路线可以到达同一状态：把每条路径都当新节点得到搜索树；识别重复状态得到图搜索。后者少做重复工作，却要用内存保存“已达”记录，而且代价搜索不能因为某状态见过一次就丢掉后来更便宜的路径。

图 5-1 的有向边标出行驶分钟数；每经过一条边也可计作一步。所有完整路线可手算：S–B–G 两步、9 分钟；S–B–D–G 三步、4 分钟；S–A–C–G 三步、7 分钟；S–A–D–G 三步、8 分钟。

窄屏提示：图可横向滚动。边上数字均为分钟；颜色之外还用线型和文字标出结果。

改变状态就会改变问题。只记车站无法区分 08:05 与 08:25、当前线路、已换乘次数、电梯停运或临时封站。路径代价也必须先定单位：各边都记 1，答案是最少站间移动；各边记分钟，答案是静态模型中的最短时间；给每次换乘另加 8 分钟，则是在表达某种换乘厌恶。把“分钟”和“换乘次数”相加前必须说明换算权重；没有一条路线天然对所有人“最好”。

5.2 BFS 与 DFS：按层，还是走到底

广度优先搜索（breadth-first search，BFS）总是先取深度最小的未展开节点，通常用先进先出的队列。直观上像从起点一圈圈向外扩展。NIST 的定义也强调逐层访问与队列实现。[2, Definition; Note] 在有限分支且某目标位于有限深度时，BFS 完备；在有限图中配合重复检测，也会访问全部可达状态。它只在每步代价相等时保证最低路径代价。图 5-1 中它返回两步的 S–B–G，却花 9 分钟，不是最少时间。若分支因子（branching factor）——每个状态可产生的后继数量——最大或有效值约为 $b$、最浅目标深度为 $d$，所看节点和所存宽前沿通常随 $b^d$ 量级增长；具体指数会随目标检验时机而差一层。

深度优先搜索（depth-first search，DFS）先沿一条分支尽量深入，再回退，通常用后进先出的栈或递归。[3, Definitions 1–2; Note] 若后继顺序规定 A 在 B 前，图 5-1 中首条答案是 S–A–C–G，7 分钟；换个顺序，结果可能改变。普通树搜索遇到无限分支或环可永远走不回来，所以一般不完备，也不保证最浅或最低代价；但在有限可达图上，若正确记录已达状态并穷尽后继，DFS 会终止并访问所有可达状态。它的路径栈随最大深度增长，通常比 BFS 的宽前沿省内存；若保留完整已达集合，仍要为访问过的状态付内存。

小图逐步复核：frontier 中到底有什么

约定后继顺序为 S:A,B；A:C,D；B:D,G；C:G；D:G；目标仅在从 frontier 取出时检验。“已展开”不含取出即停止的 G。frontier 均按下一次取出顺序列出。

5.3 代价不同时：UCS 与 Dijkstra

一致代价搜索（uniform-cost search，UCS）每次取累计路径代价 $g$ 最小的节点，通常用最小优先队列。若发现到同一状态更便宜的路径，必须更新其最佳 $g$ 与父节点；目标应在以最小 $g$ 被取出时接受，不能刚生成就停止。Dijkstra 1959 年的最短路径方法奠定了这一按暂定最小距离扩展的原则。[4, pp. 269–271] “UCS”常指 AI 搜索中的目标导向表述，“Dijkstra”常指显式图的单源最短路；核心优先原则相同，接口和停止条件可能不同。

图 5-1 的 UCS 过程如下。括号内是 $g$；A 经 A→D 提出的 7 比已有 3 差，忽略；D→G 则把 G 从 9 更新为 4。

在有限图上，正确松弛和重复处理配合非负边权，可求最短路；零代价边允许存在，负边会破坏“已取出的最小值不会再改善”的推理。在可能无限的隐式空间里，“非负”还不足以证明完备：无限条零代价边可让代价 1 的目标永远等不到。常用充分条件是有限分支且每步代价至少为某个 $\varepsilon>0$；更一般地，最优目标代价以下只能有有限多个待处理节点。有限可达图配合重复检测，即使有零边也会终止。

现实交通并不是一张静态加权图

公共交通会随出发时刻、班次、步行接驳、无障碍条件、延误和取消变化。2012 年 RAPTOR 论文用伦敦 2011 年夏季时刻表的一天做实验，同时优化到达时间与换乘次数；数据含 20,843 个站点、2,225 条路线，作者在指定硬件与 10,000 个随机查询上报告基础 RAPTOR 平均 7.3 ms，并与其实现的 Layered Dijkstra 44.5 ms、Multi-Label-Correcting 67.2 ms 比较。[5, §5; Tables 1–4]

这些是论文实验，不是伦敦交通局部署声明，也不是任一乘客都能获得的延迟保证。RAPTOR 按换乘轮次处理线路而非照搬 Dijkstra，说明利用领域结构很重要；论文所说可吸收延误、取消等变化，也不把主要时刻表实验变成实时服务证明。现实“最好路线”还可能是一个到达时间与换乘数无法互相支配的 Pareto 集合，而非单一答案。

5.4 启发式与 A*：估计剩下多远

启发函数（heuristic function）从当前状态估计到目标还需多少代价，用来决定优先检查哪个候选。它可以来自几何距离、放宽限制后的问题或预计算抽象；它是带适用条件的估计，不是“算法有直觉”，计算更强的启发也要时间和内存。

先定义所有符号与单位：$n$ 是一个搜索节点；$g(n)$ 是该节点所代表路径从起点至此的累计实际代价；$h(n)$ 是从其状态到任一目标的最小剩余代价估计；$f(n)$ 是经由该节点的估计总代价。三者必须采用同一可加单位——本例都是分钟，不能把分钟与换乘次数无权重相加。A* 每次取 $f$ 最小的 frontier 节点。其经典形式见 Hart、Nilsson 与 Raphael。[6, pp. 100–107]

令 $h^*(n)$ 表示从 $n$ 的状态到目标的真实最小剩余代价，单位同样为分钟。若对所有节点都有

则称 $h$ 可采纳（admissible）：它不高估。若对每条从 $n$ 到 $n'$、实际边代价为 $c(n,n')\ge0$ 的边都有 $h(\text{goal})=0$ 且

则称 $h$ 一致（consistent）。这像三角不等式：从这里的估计不能大于先走一步的真实代价加下一处估计。一致性在标准条件下蕴含可采纳性，但二者不是同义词。

在小图中取 $h(S,A,B,C,D,G)=(4,5,3,2,1,0)$ 分钟，恰好等于各点真实剩余最短代价，也逐边满足式 5-3。A* 手算为：

这也验证了为何不能在首次生成 G（当时 $g=9$）时停止。保证须按实现分开：A* 树搜索在启发可采纳、有限分支、相关代价轮廓有限等通常条件下返回最优代价；永久关闭状态且不重开的图搜索，标准保证要求一致启发；若启发可采纳但不一致，图搜索必须在发现更小 $g$ 时更新并重开已扩展状态，才可保留相应最优性，代价是可能重复展开。令 $h=0$，A* 就退化为 UCS。可采纳也不自动保证在无限零代价结构中终止。

“A* 总是扩展最少节点”同样过强。Dechter 与 Pearl 说明，仅有可采纳而不一致时，宽泛的最优效率说法并不成立；相关结论还依赖一致性、比较算法类别与问题域。[7, Abstract; §§1–6]

滑块拼图：启发从哪来，爆炸在哪里

8-puzzle 的状态必须记录八个数字块和空格的位置；动作是把与空格正交相邻的一块滑入空格；每次移动代价为 1；目标排列也须明确。图 5-2 的起始局面只需两步，却已经产生回退到旧状态的动作。

窄屏提示：拼图过程可横向滚动；空格用虚线框和“空”标记。

错位块数数不在目标格的数字块；曼哈顿距离把每个数字块到目标格的横向、纵向格数相加，均不计空格。在上述正交移动、单位代价规则下，两者可采纳；曼哈顿距离还一致，因为一次动作只让一块移动一格。它逐状态不小于错位数，通常更有信息，却仍要计算。取多个可采纳启发的最大值仍可采纳；直接相加则未必，除非有不重复计费的成本划分证明。

并非任意排列都能从给定目标到达；奇偶性把排列分成不同可达类，求解前应检查可解性，否则只能穷尽可达分量。路径数又会随深度反复相乘，这就是组合爆炸：重复检测和好启发能减轻，却不消除最坏情形。Ratner 与 Warmuth 证明的是规模可增长的 $n\times n$ 滑块拼图求最短解为 NP-hard，不能误写成固定大小的 8-puzzle 本身“是 NP-hard”。[8, Abstract; pp. 168–172]

5.5 局部搜索：只保留眼前位置

局部搜索（local search）主要在只关心最终配置或目标值的优化问题中，从一个或少数当前状态移动到邻居，通常不保存通往它的完整路径。它不是 BFS、UCS 那样系统维护全体 frontier 的单一算法家族。

爬山法（hill climbing）选择更好的邻居，直到没有改善。内存很低，却可能停在局部最优、平台或狭长山脊，通常既不完备也不保证全局最优；换初始点与邻域定义会换答案。随机重启能提高经验成功率，但有限次重启仍不是证明。模拟退火（simulated annealing）还会按随时间降低的概率接受变差动作，以越出局部最优；经典渐近收敛结论要求有限状态、可遍历移动及极慢等特定降温条件，不等于日常有限预算必得全局最优。束搜索（beam search）只保留排名靠前的固定数量候选，以受控内存换取丢掉唯一好路的风险，一般也不完备、不最优。

5.6 条件比较：不要只看对勾

表中 $b$ 是最大或有效分支因子，$d$ 是最浅目标深度。树搜索的 $b,d$ 估计与显式有限图的顶点数、边数界描述的不是同一表示，不应混写成一个无条件复杂度。实际实现还必须交代：何时标记已达、何时检验目标、是否更新更小 $g$、是否重开、怎样处理平局，以及停止预算。

核心概念

• 状态空间：从初始状态按允许动作可达的状态及连接；取决于建模。
• BFS：按深度逐层扩展；等步代价时求最少步骤。
• DFS：沿分支深入再回退；省前沿内存但首解依顺序。
• UCS / Dijkstra：按累计代价扩展；需非负权、正确更新与停止时机。
• 启发函数：估计剩余代价以指导顺序；有效性依问题和单位。
• A*：按实际已付加估计剩余的 $f=g+h$ 扩展；保证依启发与重开策略。
• 组合爆炸：候选数随深度或变量数反复相乘而急剧增长。

本章小结

• 搜索先把问题写成状态、动作、初始状态、目标与路径代价；改变其中任一项，就可能改变“正确答案”。
• BFS 的最优是等步代价下的最少步数；DFS 节省前沿内存，却不一般保证完备或最优。
• UCS 依累计代价排序。有限图允许零权边；无限隐式空间的完备性还需排除无限低代价节点，负权边则破坏其基本推理。
• A* 把已付代价与剩余估计相加。可采纳与一致不同，树搜索、永久关闭图搜索和可重开图搜索的保证也不同。
• 好启发、重复检测和局部搜索可以节省工作，却不能消除组合爆炸，也不能修补漏掉实时交通、无障碍或乘客偏好的目标。

相关词条与继续阅读

广度优先搜索 · 深度优先搜索 · 一致代价搜索与 Dijkstra · A* · 启发函数 · 组合爆炸

上一章：读懂 AI 所需的计算、数据与数学直觉。下一章：规划、博弈与约束求解。

资料截止说明　本章资料核查至 2026-08-26。小图与拼图均为可手算的原创教学构造；交通现实案例只复述论文所报告的数据、设置与限制。算法性质均限定在正文列出的边权、空间、去重、重开和停止条件内。