第 II 部分 · 问题求解
第 3 章 通过搜索求解问题
Chapter 3 · Solving Problems by Searching
本章导读
把「如何行动」形式化为在状态空间中寻找从初始状态到目标的路径，系统比较各类搜索策略的完备性、最优性与时间 / 空间复杂度。
学习要点
- 搜索问题五要素：初始状态、动作、转移模型、目标测试、路径耗散。
- 无信息搜索：广度优先（单位代价下最优）、一致代价（最优）、深度优先、迭代加深、双向搜索；分支因子 b 与深度 d 的复杂度分析。
- 有信息搜索：贪婪最佳优先、A*（f = g + h）；A* 树搜索在可采纳启发式下最优，图搜索需要一致性。
- 启发式设计方法：从松弛问题导出可采纳启发式、启发式之间的支配关系与取最大值组合。
- 内存受限搜索预告：IDA*、SMA*，为第 4 章的复杂环境做铺垫。
核心概念
| 术语 | English | 一句话解释 |
|---|---|---|
| 状态空间 | State Space | 所有状态与动作转移构成的隐式图 |
| 前沿（open 表） | Frontier | 已生成、待扩展的节点集合 |
| 广度优先搜索 | BFS | 按层扩展，单位代价下完备且最优 |
| 一致代价搜索 | UCS | 按路径代价 g(n) 扩展，一般代价下最优 |
| A* 搜索 | A* Search | 按 f(n) = g(n) + h(n) 排序的经典最优搜索 |
| 可采纳启发式 | Admissible Heuristic | 从不高估真实代价的启发式 |
| 一致启发式 | Consistent Heuristic | 满足三角不等式 h(n) ≤ c + h(n′) 的启发式 |
| 松弛问题 | Relaxed Problem | 放宽动作限制后的问题，其精确解构成原问题的启发式 |
| 图搜索 | Graph Search | 用 explored 集合做重复状态检测，避免指数膨胀 |
| 迭代加深 | Iterative Deepening | DFS 的空间 + BFS 的最优性，兼顾两者优点 |
配套代码（aima-python）
aima-python 是官方维护的开源算法库（MIT 协议），建议每学完一章就跑一遍对应模块的示例。