跳到主要内容

通过搜索进行问题求解 — 从穷举到 A*

这一章讲三件事: 「搜索」这个词在 AI 里到底指什么动作; 不靠任何额外线索的搜索算法怎么排座次;以及 A* 凭什么一个「乐观的估计」 就能既找得快又保证最优。 读完你会拿到全书第一个可以逐行复述的算法骨架:边界 + 已达 + 评价函数。

1. 这一章讲什么​

第 1 章说过,agent 要「做正确的事」。但很多时候正确的动作序列不是一眼能看出的: 你在罗马尼亚的 Arad 城,手里有一张明天从 Bucharest 起飞、不能退款的机票, 路牌显示有三条路通向 Sibiu、Timisoara、Zerind——都不是目的地。 这时 agent 该做的,是在模型里把各种动作序列先「演」一遍,找到一条能到 Bucharest 的, 再去真正开车。这个「先演后做」的过程就叫搜索1。

本章限定在最温顺的环境里:回合式、单智能体、完全可观测、确定性、静态、离散、已知。 这是拆解 02 的舞台;后面两章会逐条放宽这些限制。

2. 顶层全景​

  问题形式化(5 元组)
     状态空间 + 初始状态 + 目标测试 + Actions(s) + Result(s,a) + 代价 c(s,a,s′)
                          │
                          ▼
   搜索树:节点=「走到某状态的一条路」,状态可以重复出现在多个节点
     边界 frontier(已生成未扩展) · 已达 reached(生成过) · 扩展=生成子节点
                          │
        ┌─────────────────┼──────────────────┐
        ▼                 ▼                  ▼
   无信息搜索          有信息搜索          内存受限
   f=深度/BFS          f=h 贪心            束搜索 k 个
   f=g  一致代价       f=g+h A*           IDA* / RBFS / SMA*
   f=−深度 DFS        f=g+W·h 加权 A*
        │                 │
        └──── 评价标准:完备性 / 代价最优性 / 时间 / 空间
                          │
                          ▼
   启发式从哪来:松弛问题(删掉一条规则)· 模式数据库 · 地标

图说:整章就是这张图。上三角是「问题长什么样」,中段是「算法怎么排队」, 底部是「h(n) 这个魔法数字从哪来」。

3. 核心原理​

3.1 把「问题」钉成五元组​

书里给搜索问题的定义是一张清单:状态空间(所有可能局面的集合)、初始状态、目标测试(Is-Goal)、 动作集 Actions(s)、转移模型 Result(s,a),外加动作代价 c(s,a,s′)2。 在罗马尼亚的例子里,这些待填的空格里填的具体值是:

  • Actions(Arad) = {ToSibiu, ToTimisoara, ToZerind};
  • Result(Arad, ToZerind) = Zerind;
  • 解(solution)= 从初始状态到目标的路径,最优解 = 路径代价最小的那条。

形式化本身就是一个设计决策:抽象。 书里的警告很形象: 如果把动作细化到「右脚向前移动 1 厘米」,agent 永远走不出停车场3。 好抽象有两条判据:一是合理(抽象解必须能展开成真实世界的解), 二是有用(展开后的每个动作都容易执行——「从 Arad 开车到 Sibiu」 一个普通司机不需要再做规划)。

3.2 状态空间 ≠ 搜索树​

这是新手最容易混的一对概念,书里专门劈了一段: 状态空间描述世界——状态和动作;搜索树描述路径—— 同一个状态可以以多条路径、多个节点出现在树里4。

树里的节点只带四样信息:状态、父节点、动作、路径代价 g(n)。

顺着 Parent 指针(指向父节点的链接)往回爬,就能还原整条路线。

算法统一骨架只有三个数据结构:

  • 边界 frontier:已生成、还没扩展的节点(哪条路「待考察」);
  • 已达 reached:生成过就登记到一个哈希(按键直接定位)表里,防重复;
  • 扩展 expand:取出边界上的一个节点,把它的合法动作全试一遍,生成子节点。

书里还点破了边界的几何意义:边界把状态空间图分成「内部(已扩展)」 和「外部(未到达)」两块,搜索就是边界向外推的过程5。

3.3 冗余路径:不记得历史的算法注定重复历史​

从 Arad 绕 Zerind–Oradea 再回 Sibiu,比直走 Arad–Sibiu 多花 157 英里, 这条更差的路径就是冗余路径;如果允许绕环,状态空间只有 20 个城市的地图 也能长出无限的树6。

代价有多夸张?书里算过:10×10 网格世界,agent 一步之内能到任意相邻格, 9 步之内的路径条数接近 8^9,超过 1 亿条——平均每个格子被一百万条冗余路径命中。 消除冗余路径,搜索能快约一百万倍7。

对应的三个策略:全记住(reached 表,图搜索)、完全不记(树状搜索)、 折中(沿父链查环)。图搜索省时间费内存,树状搜索反之—— 这个开关在后面每一族算法里都会再出现。

3.4 无信息搜索:同一副骨架,四种排队规则​

「无信息」的意思是:算法对「离目标还有多远」一无所知。 唯一的自由度是边界用什么顺序出队。书里的座次表8:

算法出队规则完备?代价最优?时间空间
广度优先 BFS先进先出(深度浅者先)是仅当各步等价O(b^d)O(b^d)
一致代价 UCS / Dijkstrag(n) 小者先是是O(b^(1+⌊C*/ε⌋))同左
深度优先 DFS后进先出(最深者先)否(可能绕环)否O(b^m)O(bm)
IDS(迭代——界限每档加一、反复重做——搜索)深度界限每遍加 1是仅当各步等价O(b^d)O(bd)

b 是分支因子,d 是最浅解的深度,m 是最长路径。表里最反直觉的一行是 IDS。指数(每深一层、组合数翻一番)很快失控。

IDS 的思路是反复重扫浅层节点,看起来浪费,但节点的绝对多数在深层, 所以总节点数只比 BFS 多一点——b=10、d=5 时,IDS 生成 123450 个, BFS 生成 111110 个,差距不到 11%,换来的是空间从指数(每深一层翻一番)降到线性(与规模成正比)9。

UCS 有一个必须走查的细节:晚期目标测试。 从 Sibiu 出发去 Bucharest:先扩展 Rimnicu Vilcea(代价 80),再扩展 Fagaras(99), Fagaras 生成 Bucharest(99+211=310)。如果生成时就检查「到 Bucharest 了!」, 算法会交出 310 的答案;继续按代价出队,先扩展 Pitesti(177), 它生成 Bucharest 的第二条路 80+97+101=278——更便宜10。 结论:代价不相同时,必须在「出队时」而不是「生成时」查目标。

3.5 主走查:A* 在罗马尼亚​

主走查的输入还是那张地图,目标 Bucharest。先给每个城市发一个估计值 h_SLD(n) = n 到 Bucharest 的直线距离(英里):Arad 366、Sibiu 253、 Fagaras 176、Rimnicu Vilcea 193、Pitesti 100、Bucharest 011。

先看贪心最佳优先(f = h)怎么走:Arad 366 → 三条路里 Sibiu(253)最小 → Sibiu 的两个邻居里 Fagaras(176)最小 → Fagaras 生成 Bucharest,收工。 3 步到终点,快得漂亮。但把路径代价加起来:140+99+211 = 450 英里, 而经 Rimnicu Vilcea–Pitesti 的真最短路只有 418——贪心多走了 32 英里12。 它每次都选「看起来离目标最近」的格子,从不回头看已花的钱。

*换 A(f = g + h)**:每一步同时记「已花多少(g)」和「估计还差多少(h)」:

  步骤   出队节点        g      h      f=g+h   备注
  1      Arad            0     366     366    根
  2      Sibiu          140    253     393    f 最小;Timisoara 447、Zerind 449 靠后
  3      RimnicuVilcea  220    193     413    比 Fagaras(415)小,先走
  4      Fagaras        239    176     415    也进边界
  5      Pitesti        317    100     417    ← Bucharest(450)第一次出现,
                                              但 f=450 不是边界最小,继续!
  6      Bucharest      418      0     418    f=417 的 Pitesti 扩展后,
                                              经它到 Bucharest 只要 418

(表中的 g/h 数值取自原书图 3-1 与图 3-16;f 是两者之和。)

最关键的一幕在第 5 步:Bucharest 已经躺在边界里了,f=450, 但算法不理它——因为边界上还有 f=417 的 Pitesti,说明「可能存在一条 总代价 417 的解」,谁也不许急着交卷。等 Pitesti 扩展出 418 的 Bucharest, 417 的希望落空,418 才是铁板钉钉的最优13。

为什么敢保证最优? 靠 h 的一条品德:可容许性(admissibility)——从不高估。 书里的反证法三行就能走完:假设 A* 交出的解代价 C > C*,那么最优路径上必有 某个节点 n 还没被扩展;但用「g*(n) 是事实、h(n) 只会往小说」一推, n 的 f(n) ≤ C*,于是 n 的 f 比已交答案还小,矛盾——所以 C > C* 不可能发生14。

比可容许性更强一点的是一致性:对每条边,h(n) ≤ c(n,a,n′) + h(n′), 就是三角不等式。一致的好处是工程性的:每个状态第一次被到达时就已经在最优路径上, reached 表永远不用改写15。

3.6 想要更快?给最优性让路​

A* 的完备+最优+效率最优不是免费的:该扩展的节点一个都逃不掉。 书里给了三个「松绑」旋钮:

  • 加权 A:* f = g + W·h,W>1。W=2 时,一个网格问题探索的状态数 不到标准 A* 的七分之一,路径只比最优贵 5%16。 W 从 1 滑到 ∞,就连续地从 A* 滑到贪心;W=0 则退化为一致代价搜索。
  • 束搜索: 边界最多留 k 个节点。不完备、不最优,但内存可控。
  • 内存受限族: IDA*(把迭代加深的「深度上限」换成 f 值上限)、 RBFS(记住被丢弃分支的最优叶子值,随时「回心转意」)、 SMA*(内存满了丢 f 最差的叶子,把它的值备份给父节点)17。 书里对 SMA* 的警告很诚实:在极难问题上它会在少数几条候选路径间反复横跳, 像磁盘分页(内存不够时来回倒腾)的抖动——内存限制可以把 A 能解的问题变成不可解*18。

3.7 启发式从哪来:松弛问题​

h(n) 不是天上掉的。书里的答案是全书这一章最漂亮的思想: 把原问题的规则删掉一条,得到一个更松的问题;松弛问题的最优解代价, 天然就是原问题的可容许启发式——因为规则更松只可能让解更便宜,不会更贵19。

8 数码问题走一遍。规则原版:「滑块 X 能移到相邻空格 Y」。删条件:

  • 删「与空格相邻」→ 任何滑块一步直达任意位置 → 最优解恰等于 错位滑块数 h1;
  • 再删「目标格必须是空格」→ 滑块可以互相踩 → 最优解恰等于 曼哈顿距离之和 h2。

原书图 3-25 的实例里,h1=8、h2=18,而真解是 26 步——两个都没高估, 且 h2(n) ≥ h1(n) 对所有 n 成立,这叫 h2 占优 h1:占优直接转化为效率, 用 h2 的 A* 永远不会比用 h1 的 A* 扩展更多节点20。

实测数据(图 3-26,每个深度 100 个随机实例取平均):

解深度 dBFS 节点数A*(h1)A*(h2)
12267227984
209149399051318
24290082530395733

h2 相对 BFS 在 d=24 处省了约 50 倍,h1 省约 5.5 倍21。

再往上一个台阶:能不能自动生成松弛问题? 只要问题用形式语言写出动作模式, 机器就能机械地删条件、自动得到启发式——Absolver 程序就是这么干出魔方的 第一个有效启发式的22。更极端的预计算路线是模式数据库:把 8 数码的 「1-2-3-4 号滑块+空格」的全部 15120 种摆法离线求出精确代价, 在线时直接查表;不相交模式数据库让 15 数码的节点数降到曼哈顿距离的万分之一, 24 数码约百万分之一23。地图导航用的是另一招——地标: 选 10~20 个城市,预存所有点到地标的精确代价,查询时 「经地标中转」的代价就是一个往往相当准的估计24。

4. 作者的判断与证据​

  • (书内定理,给了证明) 可容许 ⟹ A* 代价最优(反证法,3.5 节);一致 ⟹ 首次到达即最优路径。这是本章的数学地基,不依赖任何实验。
  • (书内数据) 图 3-26 的节点数表、加权 A* 的「1/7 状态、+5% 代价」、 有效分支因子 b*(A* h2 在 d=12 时约 1.28,几乎不随深度增长)25。
  • (作者的经验判断) 「迭代加深是解深度未知、内存紧张时的首选无信息方法」26; 「很多实现回避不一致启发式,但最坏情形在实践中很少发生」—— 后一条书里明确标注了出处(Felner et al., 2011),是「经验胜过理论顾虑」的例子27。
  • (作者的立场) 「简单」不是参数个数——深度网络数十亿参数照样能泛化(在没见过的例子上也对), 所以应当追求「合适」而非「简单」的模型类28。这一句是对拆解 12 的预告。

5. 边界与局限​

  • 本章的环境假设(完全可观测、确定、静态、离散、已知)在真实世界很少全部成立; 放宽它们的代价是后面两章的主题。
  • A* 最坏仍是指数:超强吸力真空世界(任意格子一步吸净)有 2^N 个状态, 全部在最优解路径上、全部会被 A* 扩展——最优性买不来多项式29。
  • 松弛启发式并非免费:松弛问题本身可能难解,那时得到 h 的代价会吃掉收益30。
  • 模式数据库和地标要预计算,只对「反复求解同类问题」划算;一次性问题不值。

6. 可带走的​

  1. 搜索问题先写五元组;抽象层级是最重要的建模决策——太细走不出停车场, 太粗展开不出可执行的动作。
  2. 「生成时查目标」还是「出队时查目标」:代价相同时前者更快, 代价不同时后者才正确。这是个一秒学会、一秒忘掉的经典坑。
  3. 记住四个指标(完备/最优/时间/空间),任何新搜索算法都先在这四格打分。
  4. A* 的全部魔法来自一条品德:h 从不高估。想加速而能容忍次优? 乘个 W 让 h「撒点谎」,等值线立刻收拢。
  5. 启发式 = 松弛问题的解代价。写不写得出代码都值得问一句: 「这个问题删掉哪条规则就变简单?」
  6. 反复求解同类问题时,把便宜的计算搬到线下(模式数据库、地标、线下预计算)。
  7. IDS 的「看似浪费」提醒我们:看总量,别看重复率——大多数节点在深层。

7. 原文地图​

主题原书章原文位置
搜索=先演后做通过搜索进行问题求解 开篇text/10-fm.txt:2548(搜「向前搜索」)
罗马尼亚问题3.1text/10-fm.txt:2567(搜「罗马尼亚」) · text/10-fm.txt:2570(搜「Sibiu」)
五元组3.1.1text/10-fm.txt:2610(搜「搜索问题」) · text/10-fm.txt:2623(搜「Actions(Arad)」)
抽象3.1.2text/10-fm.txt:2644(搜「抽象」) · text/10-fm.txt:2645(搜「右脚向前移动 1 厘米」)
状态空间 vs 搜索树3.3text/10-fm.txt:2819(搜「状态空间和搜索树」)
边界与已达3.3text/10-fm.txt:2830(搜「边界」) · text/10-fm.txt:2837(搜「已达」)
冗余路径与百万倍3.3.3text/10-fm.txt:2926(搜「10×10 网格」) · text/10-fm.txt:2930(搜「注定要重复历史」)
四指标3.3.4text/10-fm.txt:2956(搜「完备性」)
BFS 的 10TB3.4.1text/10-fm.txt:3043(搜「10 TB」)
UCS 晚期目标测试3.4.2text/10-fm.txt:3055(搜「Sibiu 的后继」) · text/10-fm.txt:3067(搜「代价更高的路径」)
IDS 节点数对比3.4.4text/10-fm.txt:3175(搜「123 450」)
双向搜索动机3.4.5text/10-fm.txt:3190(搜「五万分之一」)
启发式定义3.5text/10-fm.txt:3263(搜「线索以启发式函数」)
贪心多走 32 英里3.5.1text/10-fm.txt:3284(搜「32 英里」)
hSLD 表3.5.1text/10-fm.txt:3276(搜「366」)
A* 与 f=4173.5.2text/10-fm.txt:3320(搜「Bucharest 首先出现」) · text/10-fm.txt:3323(搜「417」)
可容许性与证明3.5.2text/10-fm.txt:3327(搜「可容许性」) · text/10-fm.txt:3329(搜「反证法」)
一致性3.5.2text/10-fm.txt:3344(搜「性质为一致性」) · text/10-fm.txt:3347(搜「三角不等式」)
剪枝 Timisoara/Zerind3.5.3text/10-fm.txt:3410(搜「pruning」)
A* 的指数反例3.5.3text/10-fm.txt:3416(搜「超强吸力」)
加权 A*3.5.4text/10-fm.txt:3444(搜「七分之一」)
IDA*/RBFS/SMA*3.5.5text/10-fm.txt:3493(搜「IDA*」) · text/10-fm.txt:3552(搜「SMA*」)
内存限制→抖动3.5.5text/10-fm.txt:3573(搜「抖动」)
松弛问题3.6.2text/10-fm.txt:3703(搜「松弛问题」) · text/10-fm.txt:3722(搜「3 种松弛问题」)
h1/h2 与真解对比3.6text/10-fm.txt:3643(搜「错位滑块」) · text/10-fm.txt:3652(搜「= 18」)
占优3.6.1text/10-fm.txt:3695(搜「占优于（dominate）h1」)
图 3-26 数据3.6.1text/10-fm.txt:3678(搜「128」)
模式数据库3.6.3text/10-fm.txt:3756(搜「模式数据库」) · text/10-fm.txt:3775(搜「万分之一」)
地标3.6.4text/10-fm.txt:3780(搜「地标」)
Absolver3.6.2text/10-fm.txt:3732(搜「Absolver」)

Footnotes​

  1. 出处:「通过搜索进行问题求解」第 2548 段(text/10-fm.txt:2548,搜「向前搜索」)。 Arad/Bucharest 设定在 2567–2571 段。 ↩

  2. 出处:「通过搜索进行问题求解」第 2610 段(text/10-fm.txt:2610,搜「搜索问题」)。 ↩

  3. 出处:「通过搜索进行问题求解」第 2645 段(text/10-fm.txt:2645,搜「1 厘米」)。 抽象的合理性与有用性两条判据在 2663–2668 段。 ↩

  4. 出处:「通过搜索进行问题求解」第 2819 段(text/10-fm.txt:2819,搜「状态空间和搜索树」)。 ↩

  5. 出处:「通过搜索进行问题求解」第 2845 段(text/10-fm.txt:2845,搜「分离」)。 边界/已达/扩展定义在 2824–2838 段。 ↩

  6. 出处:「通过搜索进行问题求解」第 2918 段(text/10-fm.txt:2918,搜「重复状态」)。 140 与 297 英里对比在 2922 段。 ↩

  7. 出处:「通过搜索进行问题求解」第 2926 段(text/10-fm.txt:2926,搜「10×10 网格」)。 「快大约 100 万倍」在 2930 段。 ↩

  8. 出处:「通过搜索进行问题求解」图 3-15,第 3256 段(text/10-fm.txt:3256,搜「如果两个方向均使用广度优先搜索或一致代价搜索」)。 BFS 的 10TB/3.5 年数字在 3043–3046 段。 ↩

  9. 出处:「通过搜索进行问题求解」第 3175 段(text/10-fm.txt:3175,搜「123 450」)。 ↩

  10. 出处:「通过搜索进行问题求解」第 3055 段(text/10-fm.txt:3055,搜「Sibiu 的后继」)与 第 3067 段(text/10-fm.txt:3067,搜「代价更高的路径」)。 ↩

  11. 出处:「通过搜索进行问题求解」图 3-16,第 3291 段(text/10-fm.txt:3291,搜「366」)。 hSLD(Arad)=366 在 3276 段。 ↩

  12. 出处:「通过搜索进行问题求解」第 3284 段(text/10-fm.txt:3284,搜「32 英里」)。 贪心的三步走查在 3279–3282 段。 ↩

  13. 出处:「通过搜索进行问题求解」第 3320 段(text/10-fm.txt:3320,搜「Bucharest 首先出现」)。 「可能存在一个经过 Pitesti 的解,代价低至 417」在 3323 段。 ↩

  14. 出处:「通过搜索进行问题求解」第 3329 段(text/10-fm.txt:3329,搜「反证法」)。 五行推导在 3335–3341 段。 ↩

  15. 出处:「通过搜索进行问题求解」第 3358 段(text/10-fm.txt:3358,搜「算法第一次到达某个状态时」)、 第 3347 段(text/10-fm.txt:3347,搜「三角不等式」)与 第 3330 段(text/10-fm.txt:3330,搜「最优路径上」)。 ↩

  16. 出处:「通过搜索进行问题求解」图 3-21 说明,第 3444 段(text/10-fm.txt:3444,搜「七分之一」)。 W=1/0/∞ 对应关系在 3437–3444 段。 ↩

  17. 出处:「通过搜索进行问题求解」第 3493 段(text/10-fm.txt:3493,搜「IDA*」)、 第 3531 段(text/10-fm.txt:3531,搜「改变主意」)与 第 3552 段(text/10-fm.txt:3552,搜「SMA*」)。 ↩

  18. 出处:「通过搜索进行问题求解」第 3573 段(text/10-fm.txt:3573,搜「抖动」)。 「内存限制会使问题变得难以处理」在 3576 段。 ↩

  19. 出处:「通过搜索进行问题求解」第 3703 段(text/10-fm.txt:3703,搜「松弛问题」)与 第 3714 段(text/10-fm.txt:3714,搜「超图」)。 ↩

  20. 出处:「通过搜索进行问题求解」第 3696 段(text/10-fm.txt:3696,搜「使用 h2 的 A* 永远不会比使用 h1 的 A* 扩展更多」)。 ↩

  21. 出处:「通过搜索进行问题求解」图 3-26,第 3678 段(text/10-fm.txt:3678,搜「128」)。 d=24 行:290 082 / 53 039 / 5 733。 ↩

  22. 出处:「通过搜索进行问题求解」第 3732 段(text/10-fm.txt:3732,搜「Absolver」)。 ↩

  23. 出处:「通过搜索进行问题求解」第 3756 段(text/10-fm.txt:3756,搜「模式数据库」)。 15 120 种模式在 3757 段;「千分之一」「万分之一」「一百万倍」在 3765–3776 段。 ↩

  24. 出处:「通过搜索进行问题求解」第 3780 段(text/10-fm.txt:3780,搜「地标」)。 「毫秒内找到代价最优的驾驶路线」在 3781 段。 ↩

  25. 出处:「通过搜索进行问题求解」第 3656 段(text/10-fm.txt:3656,搜「有效分支因子」)。 ↩

  26. 出处:「通过搜索进行问题求解」第 3179 段(text/10-fm.txt:3179,搜「首选」)。 ↩

  27. 出处:「通过搜索进行问题求解」第 3364 段(text/10-fm.txt:3364,搜「费尔纳」)。 ↩

  28. 出处:「通过搜索进行问题求解」第 1282 段(text/10-fm.txt:1282,搜「数十亿」)。 ↩

  29. 出处:「通过搜索进行问题求解」第 3416 段(text/10-fm.txt:3416,搜「超强吸力」)。 ↩

  30. 出处:「通过搜索进行问题求解」第 3731 段(text/10-fm.txt:3731,搜「代价将非常高」)。 ↩