复杂环境中的搜索 — 局部搜索、与或树与在线探索
这一章讲四件事: 只要「好状态」不要路径时怎么搜;动作会掷骰子时怎么搜; 看不清世界时怎么搜;地图都没有时怎么搜。 读完你会拿到四张放宽假设后的新地图——以及它们各自付出掉了什么。
1. 这一章讲什么
第 2 章的一切都建立在一张清单上:回合式、单智能体、完全可观测、确定性、静态、 离散、已知。真实世界几乎不发售这种环境。本章按四步放宽1:
- 有些问题只在乎终态:8 皇后要的是一个「谁也不打谁」的摆法, 至于是怎么摆出来的毫不在意——IC 布图、车间调度、投资组合都一样。
- 动作的结果带随机性:吸尘器一吸,可能清了这格也捎带清了那格。
- 看不全:传感器只能告诉你脚下这格。
- 没有地图:在线搜索,一边走一边把地图画出来。
2. 顶层全景
「只要好状态,不要路径」
局部搜索:只记当前状态,不记路径/已达
爬山法 ──卡在局部极大──▶ 模拟退火(先摇后停)
└──▶ 束搜索(k 个并行) / 遗传算法(杂交+变异)
连续状态:梯度 ∇f + 步长 α / 牛顿-拉弗森(黑塞矩阵)
「动作结果随机」
与或树:或节点=我选择,与节点=环境掷骰
解=条件规划(含 if-then-else / while)
「看不全」
信念状态 = 可能状态的集合,在信念空间里照常搜
无传感器规划:用动作序列「强迫」世界进入目标
「没地图」
在线搜索:交替计算-动作;竞争比;死胡同不可避
LRTA*:H(s) 存当前估计,把局部极小「拉平」
图说:四行对应四次放宽;每一行都是「上一行的解法在这里失效了」。
3. 核心原理
3.1 局部搜索:一个健忘的人在大雾中找珠峰
局部搜索只维护当前状态:看邻居、挑最好的、搬过去、再环顾四周。 不记路径也不记已达,于是省内存,还能在无限状态空间里干活2。 代价是书里那句著名的比喻:像一个健忘的人在大雾中试图找到珠穆朗玛峰的顶峰—— 不看全局,只感觉脚下的坡度3。
用 8 皇后走一遍。完整状态形式化:8 个皇后每列一个(可能互相攻击), 移动一个皇后得到后继,每个状态有 8×7=56 个后继;代价函数 h = 可以互相攻击的皇后对的数量,解就是 h=04。
爬山法在这个问题上的成绩单很有意思:从随机初始状态出发,86% 的情况会卡住, 只有 14% 能解出来;但解出来的平均只用 4 步、卡住的只花 3 步—— 失败得飞快,成功得也飞快5。
卡住的三种地形:局部极大值(每个邻居都更矮)、岭(一连串不相连的局 部极大)、 平台区(一片平地)6。补丁是一个数字:允许横向移动—— 在平地上也走,赌它是「山肩」而不是死平台;限制连续横移 100 次防止死循环。 就这一个补丁,成功率从 14% 跳到 94%,代价是每次成功平均要 21 步7。
再往上摞补丁:随机重启。解不出来就换初始状态重跑。 如果单次成功率是 p,期望重启次数是 1/p——8 皇后 p≈0.14, 大约 7 次迭代、总共约 22 步就能解出;加横移后 p≈0.94,平均 1.06 次迭代、约 25 步。 这个组合强到什么程度?书里的原话:即使 300 万个皇后,也能很快找到解8。
3.2 模拟退火:概率性地下坡
爬山法的病根是从不接受更差的状态。纯随机游走反过来,什么都接受, 完备但慢得离谱。模拟退火把两者插值:
选一个随机邻居;如果更好,必接受;如果更差,以概率 e^(−ΔE/T) 接受—— 差得越多越难接受,而且温度——那个随时间下降、控制接受坏移动的参数 T——越低越难接受。T 按 schedule 逐渐降到 09。
书里的物理比喻:把一个乒乓球放进崎岖表面,想让它落进最深的裂缝。 只让它滚,会停在某个局部极小;摇晃平面,它会从浅坑里弹出来—— 诀窍是先用力摇(高温),再慢慢减小幅度(降温),既弹得出浅坑、 又摇不出最深的坑。理论上,降温足够慢时,算法以接近 1 的概率停在全局最优(整片地形里的最深谷底)10。
3.3 遗传算法:杂交何时才有用
局部束搜索已经像「并行(同时跑多份)的爬山」:k 个状态同时前进,好状态会「招呼」计算投入 (书里写:「过来,这里的草更绿!」)11。遗传算法在束搜索上加了一个动作: 重组——两个父串各切一段,拼出子代,再以小概率翻转某些位(变异)12。
杂交不是免费的午餐。书里给了精确的判据:只有当字符串(一长串符号)的某一段本身 就是一个「有用的积木」时,杂交才有优势——比如「前 3 列皇后放在第 2/4/6 行」 互不攻击,这一段可以和其他个体里的好片段拼成完整解。 如果各位完全 无关,或者把基因位置随机打乱,杂交毫无优势13。
配套的还有一条生物学侧记:鲍德温效应——学习可以放宽适应度要求、 加速进化;「难以学习的事最终进入基因组,容易学习的事不必进入基因组」14。
3.4 连续空间:从离散化到牛顿法
状态是连续值时分支因子无限大,上一章的算法几乎全部失效。 解法阶梯:先离散化(在 ±δ 网格上走,δ 逐渐减小);有目标函数表达式时, 用梯度(最陡上升方向的信号)∇f 指方向、步长 α 定大小;α 难调就用线搜索(反复加倍直到 f 变差)15。
最陡的武器是牛顿-拉弗森:用黑塞矩阵(二阶导数表)把地形近似成二次曲面, 一步跳到曲面的极小值。书里的实例:给罗马尼亚新建 3 个机场、 最小化所有城市到最近机场的距离平方和——牛顿法一步的几何意义是 把每个机场直接移到「它的城市集合」的质心16。
3.5 主走查(一):不稳定的吸尘器与与或树
主走查登场。规则改动一处:吸尘器的 Suck 不可靠—— 在脏格子上,它有时只清当前格、有时连邻格一起清;在干净格子上, 它有时反而把灰扬起来17。
于是转移模型从「函数」变「集合」:
Results(1, Suck) = {5, 7}
状态 1(位于 A,两格都脏)执行 Suck,结果可能是 5(A 干净 B 脏)也可能是 7(全干净)。没有任何单一动作序列能保证到达目标,因为第一颗骰子 就掷出了两个世界。解必须换形态——条件规划:
[Suck, if State = 5 then [Right, Suck] else []]
如果 Suck 清了两格(状态 7),什么也不用做;只清了一格(状态 5), 就 Right、再 Suck。解从「一条线」长成了「一棵树」18。
搜索算法随之变形:书里把节点分两类——或节点(轮到我选动作, Left/Right/Suck 任选)和与节点(环境掷完骰子,{5,7} 里每个结果 都必须各自有解)。两种节点交替出现,就是与或树; 解是一棵子树:每个叶子是目标、每个或节点选一条边、每个与节点全要19。
再加一档难度:循环解。另一个变体「光滑真空世界」里,
Right 有时会让 agent 原地不动。从状态 1 出发不存在无环解,
但存在循环解:[Suck, while State = 5 do Right, Suck]——反复尝试直到成功。
什么时候敢这么赌?书里划了界:如果「原地不动」的随机性是独立的
(这次不行下次可能行),循环解可靠;如果失败源于某个未观测的持久原因
(传动带断了),重复一万次也没用20。
3.6 信念状态:看不见,就把「可能在哪」全记住
现在把传感器也拔掉一半。agent 不知道自己在 A 还是 B、不知道灰在哪, 初始信念状态就是全部 8 个物理状态 {1,…,8}。妙处在于:没有感知也能获得信息。 执行 Right,信念状态收缩成 {2,4,6,8}(「我一定在某一列的右边」); 执行 [Right, Suck],收缩成 {4,8};一路执行 [Right, Suck, Left, Suck], 无论初始在哪,必然落在目标状态 7——书里把这个动作叫「强迫」世界21。
无传感器问题的解仍是动作序列(没有感知可分支),但搜索是在信念状态空间里做的: 原问题有 N 个物理状态,信念状态至多 2^N 个。实际搜索时用一条剪枝: 如果一个信念状态是另一个的超集(比如 {1,3,5,7} ⊃ {5,7}), 可以直接剪掉——能解开 {1,3,5,7} 的序列必然能解开它的任何子集22。
有了传感器呢?局部感知真空世界里,初始感知 [L, Dirty] 把信念收到 {1,3}。
此时每次「预测(动作)→可能感知→更新」三段式,信念状态按感知分叉,
解随之变回条件规划:[Suck, Right, if Bstate = {6} then Suck else []]——
注意 if 测的是信念状态而不是真实状态,因为 agent 只知道自己信什么23。
维护信念的更新式 b′ = Update(Predict(b,a), o) 有三个学名:
监视、滤波、状态估计——第 10 章的概率滤波是它的连续版。
同一套机器还能干定位:迷宫机器人拿到声呐位向量(一串 0/1,每位记录一个方向)1011(北/南/西有墙), 全地图更新后只剩 4 个候选位置;挪一步、再读 1010,只剩 1 个。 书里补了一句冷幽默式的重要提醒:如果传感器坏了呢?布尔逻辑处理不了 「传感器大概率错」,概率可以——「只要它出错的时间不超过一半」24。
3.7 在线搜索:把身体押上去
前面所有算法都是离线的:在模型里算完整条路径,再开始执行。 在线搜索反过来:算一步、走一步、看一眼、再算——因为地图根本没有, 「模型」就是世界本身,探索的代价是真实的时间与鞋底25。
在线世界的两个关键词:
- 竞争比:你走的路径代价 ÷ 事先知道地图时的最优代价。越小越好。
- 死胡同:走进去就出不来的状态。书里用对手论证证明:没有算法能在 所有可能的状态空间里躲开死胡同——想象一个对手在你探索时现场搭墙, 你选哪边他就在哪边立一堵长墙26。
两条算法:
在线深度优先:用 result[s,a] 表记录「我试过 a,结果到了 s′」, 把这张表当地图;每到一个新状态先试没试过的动作;全试完就在物理上 沿原路走回去(回溯到上一个还没试完的状态)。最坏情况下每个连接走两遍, 这对探索是最优的27。
LRTA(实时学习 A):给每个到过的状态存一个代价估计 H(s), 每走一步就把刚离开的状态的 H 更新成「邻居的 c(s,a,s′)+H(s′) 的最小值」。 效果是把局部极小拉平**:图 4-23 的一维例子里,agent 卡在 H=2 的坑里, 发现自己左右邻居的估计是 1+9 和 1+2,往右走;走完发现 H=2 太乐观, 改成 3;再走再改——几次往返后坑被填平,agent 逃了出去28。 配套的一条心法:不确定性下的乐观主义——没试过的动作,先假设它直达目标 (按 h(s) 计),这逼着 agent 去探索没走过的门29。
4. 作者的判断与证据
-
(书内数据) 爬山法 14%→94%(加横移)、随机重启 7 次/22 步、 300 万皇后可解578——全是 8 皇后上的实测,原书明确给出。
-
(书内定理) 模拟退火在降温足够慢时,会以接近 1 的概率停在全局最优,依据是玻尔兹曼分布(给「各状态各占多少概率」定规律)的性质9。
-
代价:「足够慢」在实践中几乎等不到9。
-
(书内反证) 在线搜索无算法能避免死胡同(对手论证)26—— 这是少数几处「证明不可能」的地方,比「证明存在」更值得记。
-
(作者的方法论判断) NP 困难问题通常有指数多个局部极大; 地形「像平地上散布着一群秃顶豪猪,每个豪猪的刺上还住着微型豪猪」30—— 这是描述,不是定理,但它是选择随机重启的正当理由。
-
(作者的坦白) 进化算法「目前还不清楚其吸引力来自性能优势,还是来自 进化本身」31——对热点技术的罕见冷处理。
5. 边界与局限
- 局部搜索不知「离解多远」之外的信息,天然不保证最优;模拟退火要收敛(稳定下来不再变化)是有前提的 依赖理论降温曲线,工程里没人等得起。
- 信念状态空间 2^N 的爆炸没有被消灭,只是被剪枝缓解;大 N 时连单个 信念状态都存不下,需要逻辑式这样的紧凑表示(书里预告了第 7 章)32。
- 在线搜索的 LRTA* 只保证在「可安全探索」的空间里有效; 不可逆动作(楼梯、单行道)是真实世界的常态33。
- 循环解的可靠性判据(独立随机 vs 隐藏持久故障)在第 10 章会以 瞬时故障/持续故障模型的形式回来——那时才有了「哪边概率大」的算术。
6. 可带走的
- 只要终态不要路径时,别用图搜索——局部搜索用 1/1000 的内存换 94% 的成功率。
- 「允许偶尔变差」是逃出局部极大的通用药方;温度/概率就是药量。
- 杂交(以及一切「组合两个好东西」的操作)只在存在可复用积木时有意义; 没有结构就别指望拼装。
- 把「结果的集合」而不是「结果」当转移模型,搜索树自动变成与或树, 解自动变成条件规划——接口(调用方式)不变,产物升级。
- 无传感器≠无解:动作序列可以强迫世界进入目标;广谱抗生素就是这个思路。
- 剪枝口诀:能解超集的必能解子集——先解更困惑的情况。
- 在线场景里,「未试过的动作先当它是好的」不是天真,是探索的策略纪律。
7. 原文地图
| 主题 | 原书章 | 原文位置 |
|---|---|---|
| 四次放宽 | 4 开篇 | text/10-fm.txt:4043(搜「放宽这些限制」) |
| 局部搜索优点 | 4.1 | text/10-fm.txt:4057(搜「局部搜索」) |
| 大雾找珠峰 | 4.1.1 | text/10-fm.txt:4076(搜「大雾」) |
| 8 皇后形式化 | 4.1.1 | text/10-fm.txt:4087(搜「8 皇后」) · text/10-fm.txt:4093(搜「h = 17」) |
| 14%→94% | 4.1.1 | text/10-fm.txt:4127(搜「86%」) · text/10-fm.txt:4134(搜「94%」) |
| 随机重启 22 步 | 4.1.1 | text/10-fm.txt:4141(搜「随机重启」) · text/10-fm.txt:4149(搜「300 万个皇后」) |
| 秃顶豪猪 | 4.1.1 | text/10-fm.txt:4153(搜「豪猪」) |
| 乒乓球比喻 | 4.1.2 | text/10-fm.txt:4165(搜「乒乓球」) |
| 玻尔兹曼收敛 | 4.1.2 | text/10-fm.txt:4179(搜「玻尔兹曼分布」) |
| 「草更绿」 | 4.1.3 | text/10-fm.txt:4204(搜「草更绿」) |
| 杂交何时有用 | 4.1.4 | text/10-fm.txt:4283(搜「有用功能的区域」) |
| Baldwin 效应 | 4.1.4 | text/10-fm.txt:4319(搜「鲍德温效应」) |
| 3 机场与质心 | 4.2 | text/10-fm.txt:4342(搜「3 个机场」) · text/10-fm.txt:4393(搜「质心」) |
| 不稳定吸尘器 | 4.3.1 | text/10-fm.txt:4439(搜「不稳定」) · text/10-fm.txt:4447(搜「Results(1, Suck)」) |
| 条件规划 | 4.3.1 | text/10-fm.txt:4450(搜「if State = 5」) |
| 与或树 | 4.3.2 | text/10-fm.txt:4461(搜「或节点」) · text/10-fm.txt:4471(搜「子树」) |
| 循环解与传动带 | 4.3.3 | text/10-fm.txt:4510(搜「循环解」) · text/10-fm.txt:4519(搜「传动带」) |
| 强迫世界 | 4.4.1 | text/10-fm.txt:4539(搜「无传感器」) · text/10-fm.txt:4544(搜「强迫」) |
| 超集剪枝 | 4.4.1 | text/10-fm.txt:4604(搜「超集」) |
| 信念测 if | 4.4.3 | text/10-fm.txt:4678(搜「if Bstate = {6}」) · text/10-fm.txt:4679(搜「信念状态」) |
| 定位 1011→1010 | 4.4.4 | text/10-fm.txt:4713(搜「定位」) · text/10-fm.txt:4718(搜「1011」) |
| 传感器出错不到一半 | 4.4.4 | text/10-fm.txt:566(搜「故障」) |
| 竞争比与死胡同 | 4.5.1 | text/10-fm.txt:4781(搜「竞争比」) · text/10-fm.txt:4788(搜「对手论证」) |
| 在线 DFS | 4.5.2 | text/10-fm.txt:4823(搜「Online-DFS-Agent」) · text/10-fm.txt:4842(搜「两次」) |
| LRTA* 拉平 | 4.5.3 | text/10-fm.txt:4874(搜「拉平」) · text/10-fm.txt:4875(搜「LRTA*」) |
| 乐观主义 | 4.5.3 | text/10-fm.txt:4884(搜「乐观主义」) |