第 II 部分 · 问题求解
第 4 章 复杂环境中的搜索
Chapter 4 · Search in Complex Environments
本章导读
当问题没有显式路径结构、环境部分可观测、或者动作必须边感知边决定时，经典树搜索不再适用——本章给出局部搜索、信念状态搜索与在线搜索三套扩展。
学习要点
- 局部搜索家族：爬山法及其陷阱（山脊 / 平原 / 山麓）、随机重启、局部束搜索；只关心目标状态、内存开销极小。
- 模拟退火与遗传算法：以受控的「劣化移动」换取跳出局部最优的能力。
- 连续空间中的搜索：离散化与梯度法的思想，衔接第 21 章的优化。
- 无观察环境（传感器失效）：在信念状态空间中做一致性规划；部分可观测下的搜索与信念状态膨胀问题。
- 在线搜索与未知环境：爬山不可回退时的困境，LRTA* 学习实时搜索，探索与利用的初步权衡。
核心概念
| 术语 | English | 一句话解释 |
|---|---|---|
| 爬山法 | Hill Climbing | 沿最陡上升方向不断改进当前状态的局部搜索 |
| 模拟退火 | Simulated Annealing | 以温度控制概率接受劣化移动的随机搜索 |
| 遗传算法 | Genetic Algorithm | 种群 + 交叉 + 变异的进化式搜索 |
| 局部束搜索 | Local Beam Search | 并行保留 k 个最优候选的局部搜索 |
| 信念状态 | Belief State | 智能体认为世界可能处于的状态集合 |
| 一致性规划 | Conformant Planning | 无感知条件下保证达成目标的规划 |
| 在线搜索 | Online Search | 行动与感知交替、环境事先未知的搜索 |
| LRTA* | Learning Real-Time A* | 边行动边更新启发式的在线搜索算法 |
| 山麓 / 山脊 / 平原 | Foothill / Ridge / Plateau | 爬山法失效的三类典型地形 |
配套代码（aima-python）
aima-python 是官方维护的开源算法库（MIT 协议），建议每学完一章就跑一遍对应模块的示例。