搜索是人工智能问题求解的三大方法之一（另两种为推理和约束满足）。搜索算法的本质是在问题的解空间中寻找一条从初始状态到目标状态的最优路径。本章从无信息搜索、启发式搜索、对抗搜索到蒙特卡洛树搜索四个层次展开。
搜索算法基础
搜索问题的五要素
| 要素 | 说明 | 示例（最短路径搜索） |
|---|---|---|
| 状态 | 对智能体和环境当前情形的描述 | 当前所在城市 |
| 动作 | 智能体从一个状态转移到另一个状态的行为 | 乘坐一趟列车到下一城市 |
| 状态转移 | 执行动作后状态的变化（本章假设确定性的） | 从城市A抵达城市D |
| 路径与代价 | 状态序列为一条路径，路径对应一个代价（时间开销） | A→E→G→K，代价为总时间 |
| 目标测试 | 判断状态是否为终止状态 | 若当前状态为K，测试通过 |
搜索算法的评价指标
| 指标 | 含义 |
|---|---|
| 完备性 | 当问题有解时，算法是否能保证找到解 |
| 最优性 | 找到的第一个解是否为最优解 |
| 时间复杂度 | 找到解所需的时间，通常用扩展结点数衡量 |
| 空间复杂度 | 算法运行中需要的内存，通常用同时记录的结点数衡量 |
搜索算法框架
算法 3.1 树搜索框架：
| 步骤 | 操作 |
|---|---|
| 1 | 初始化边缘集合 ，使其只包含根结点。 |
| 2 | 若 ，从 中选出一个结点 。 |
| 3 | 将 从 中删除，若 通过目标测试，返回其路径。 |
| 4 | 将 的后继结点加入 ，重复步骤2。 |
常见结点扩展策略：
| 策略 | 说明 |
|---|---|
| 广度优先搜索 | 每次从 中取出最浅的结点 |
| 深度优先搜索 | 每次从 中取出最深的结点 |
树搜索与图搜索
| 方法 | 核心区别 | 特点 |
|---|---|---|
| 树搜索 | 同一状态可对应多个结点 | 依赖剪枝（去除环路）保证完备性 |
| 图搜索 | 同一状态只能对应一个结点 | 维护闭表 记录已扩展状态，效率更高 |
图搜索流程（算法3.2）：
- 维护边缘集合 和闭表集合 。
- 从 取结点 ，若其状态不在 中，则加入 并扩展其后继加入 。
- 若状态已在 中，则剪枝该结点。
注意：图搜索虽效率更高，但在某些情况下可能破坏原树搜索算法的最优性。
启发式搜索
启发式搜索利用辅助信息（启发信息）指导搜索方向，提高搜索效率。核心是定义启发函数 （估计结点 到目标的代价）和评价函数 （决定扩展优先级）。
两种启发式搜索算法对比
| 算法 | 评价函数 | 特点 |
|---|---|---|
| 贪婪最佳优先搜索 | 只考虑距目标的估计代价，可能非最优 | |
| A*搜索 | 综合已付出代价 和估计剩余代价 ，更全面 |
启发函数的性质
| 性质 | 定义 | 关系 |
|---|---|---|
| 可容性 | ，且对目标 。不高估代价。 | 一致性 可容性 |
| 一致性 | 。满足三角不等式。 | 更强的条件 |
A* 算法的性能
| 条件 | 结论 |
|---|---|
| 状态有限，排除环路 | 图搜索A* 和排除环路的树搜索A* 都是完备的。 |
| 树搜索 + 启发函数可容 | 保证最优性。 |
| 图搜索 + 启发函数可容 | 不一定保证最优性（需额外处理）。 |
| 图搜索 + 启发函数一致 | 保证最优性（且评价函数值沿路径单调非减）。 |
A*的优势：设计的启发函数越好（越接近 ），A* 扩展的结点越少，越接近“最优搜索”。
对抗搜索
对抗搜索（博弈搜索）研究在信息确定、全局可观察、交替行动、零和的两人博弈中如何找到最优策略。
最小最大搜索
核心思想：玩家 MAX 最大化自身得分，玩家 MIN 最小化 MAX 的得分，交替搜索直至终局。
结点得分计算：
算法流程（算法3.3）：
MaxValue(s)：若终局返回得分；否则递归选择子结点中最大值。MinValue(s)：若终局返回得分；否则递归选择子结点中最小值。MinimaxDecision(s)：选择使MinValue最大的动作。
性能：若搜索树有限，算法完备且最优。时间复杂度 ，空间复杂度 。
Alpha-Beta 剪枝
在最小最大搜索基础上，Alpha-Beta 剪枝通过追踪 （MAX 层当前最优下界）和 （MIN 层当前最优上界）来剪除不可能影响最终决策的分支。
剪枝条件：
- Alpha 剪枝：在 MIN 层，若某子结点返回值 ，则剪除其兄弟结点。
- Beta 剪枝：在 MAX 层，若某子结点返回值 ，则剪除其兄弟结点。
算法流程（算法3.4）：
MaxValue(s, α, β)：扩展子结点时，若出现 ，则剪枝返回。MinValue(s, α, β)：扩展子结点时，若出现 ，则剪枝返回。
性能：
- 最优情况下（结点按“最佳先查”排序）时间复杂度降至 。
- 结点顺序对剪枝效率影响极大。
蒙特卡洛树搜索
当搜索空间极大时（如围棋），蒙特卡洛树搜索 (MCTS) 通过采样而非穷举来评估分支优劣，找到近似最优解。
探索与利用的平衡
以多臂赌博机问题为模型：智能体面对 个赌博机，每次选择转动一个臂膀获得随机奖励，目标是最小化悔值。
| 策略 | 说明 | 缺点 |
|---|---|---|
| 贪心算法 | 总是选当前平均奖励最高的臂 | 容易陷入局部最优，探索不足 |
| -贪心算法 | 以 概率随机探索， 概率利用 | 忽略了各臂的探索次数差异 |
上限置信区间 (UCB1)
UCB1 优先选择置信上界最大的动作，平衡利用（均值高）和探索（不确定性大）。
选择公式：
- ：平均奖励， ：被选次数， ：探索权重超参数。
MCTS 的四个步骤
| 步骤 | 操作 | 说明 |
|---|---|---|
| 选择 | 从根结点开始，用 UCB1 递归选择子结点，直至叶子结点或未完全扩展结点 | 平衡探索与利用 |
| 扩展 | 若 非终止结点，随机扩展一个未探索的子结点 | 扩大搜索树 |
| 模拟 | 从 开始，用简单策略（如随机）模拟游戏直至终局 | 快速评估 |
| 反向传播 | 将模拟结果沿路径回溯，更新结点的总奖励和访问次数 | 传播信息 |
MCTS 的优势：基于采样而非穷举，高效且能保证一定准确性，在搜索空间极大的游戏（如围棋）中表现出色。
小结
本章介绍了搜索求解的核心方法与算法：
- 无信息搜索（BFS、DFS）不利用启发信息，状态有限时完备但效率低。
- 启发式搜索（贪婪最佳优先、A*）利用 预估代价指导搜索。A* 在 满足可容性/一致性时保证最优。
- 对抗搜索（最小最大、Alpha-Beta 剪枝）解决二人零和博弈，Alpha-Beta 剪枝大幅减少搜索结点。
- 蒙特卡洛树搜索通过采样和 UCB1 策略，解决复杂博弈的近似最优决策问题。