Chapter 4 Informed Search¶

对应于 "Artificial Intelligence - A Modern Approach (3rd Edition)" 中的 Chapter 3

SOLVING PROBLEMS BY INFORMED SEARCHING (3.5~3.6)

最佳优先搜索¶

思想: 使用评估函数𝑓(𝑛)估计每个结点的“可取性”;扩展最期望的未扩展结点

实现: 按照期望降序对边缘中的结点进行排序

启发函数: 表示为h(𝑛)，从结点𝑛到目标结点的最小代价路径的代价估计值，即从结点𝑛到最接近目标的代价

分类：

贪婪最佳优先搜索扩展离目标最近的结点

思想: 避免扩展代价已经很高的路径

评估函数: 𝑓(𝑛) = h(𝑛) + 𝑔(𝑛)

A*搜索结合了一致代价搜索和贪婪最佳优先搜索的优点

保障A*搜索最优性的第一个条件是h(𝑛)是可采纳启发式，指的是它不会过高估计到达目标的代价
- 即：h(𝑛) ≤ \(h^*\)(𝑛)，当\(h^*\)(𝑛)是从结点n到目标结点的真实代价。(同时要求h(𝑛) ≥ 0，因此对任意目标𝐺， h𝐺 =0)

theorem:

如果h(𝑛)是可采纳的，则树搜索的A*算法是最优的

启发式h(𝑛)是一致的：如果对于每个结点 𝑛 和通过任一行动 𝑎 生成的 𝑛 的每个后继结点 \(n^,\) ，从结点𝑛到达目标的估计代价不大于从 𝑛 到 n' 的单步代价与从 n' 到达目标的估计代价之和:
- \(h(n) ≤ cost(n,a,n^,) + h(n^,)\)
如果h(𝑛)是一致的，则：𝑓(𝑛) 在任何路径上都是非递减的
一致性实际上是三角不等式

以“八数码问题”为例：

h* = 放错位置的方格数
h*(𝑠0) = 8
h' = 方格与目标位置的曼哈顿距离(Manhattan distances) 之和。曼哈顿距离指的是水平和竖直的距离之和，h'(𝑠0) =3+1+2+2+2+3+3+2=18

启发式搜索的性能：

定义: 对于两个可采纳启发式函数h*和h'，h'比h*占优势，当且仅当∀𝑛, h'(𝑛) ≥ h*(𝑛)

优势可以转化为效率: 使用h'的A*算法永远不会比使用h* 的A*算法扩展更多的结点

给定任何可采纳启发式ha和hb，h = max(ha, hb)也是可采纳的，并且比ha和hb占优势

好的启发式方法会使 \(b^*\) 值接近于1，即每层扩展一个节点

松弛问题: 减少了行动限制的问题

松弛问题的最优解代价不大于原问题的最优解代价

模式数据库 的思想就是对每个可能的 子问题实例 存储精确解代价

本质是在全局范围内维护一个“并集”

经验意味着求解大量的八数码问题。每个八数码问题的最优解都是供 h(𝑛) 学习的实例，每个实例都包括解路径上的一个状态和从这个状态到达解的代价

机器学习算法用来构造h(𝑛) ，它能预测搜索过程中所出现的其它状态的解代价

从经验中学习启发式不能保证可采纳性或一致性