第 13 讲 · 启发式与局部搜索

第 12 讲的算法只知道“已经走了多远”，不知道“离目标还有多远”。启发式搜索加入估计 $h(n)$ ，把问题领域中的直觉变成搜索顺序。后半讲再换到局部搜索：不保存到达路径，只在候选解空间中不断改进当前方案。

Greedy 和 A* 的差别

Greedy best-first 每次选 $h(n)$ 最小的节点，只看“估计还剩多少”；它可能很快冲向目标，也可能为了眼前接近而绕一条昂贵远路。

A* 同时考虑已付代价与剩余估计：

f(n)=g(n)+h(n)

$h=0$ 时，A* 退化为 UCS；只看 $h$ 时接近 Greedy。

若启发式从不高估真实剩余代价 $h^*(n)$ ：

0\le h(n)\le h^*(n)

就称为可采纳。树搜索版 A* 在正代价等条件下可由此保证最优。图搜索更希望启发式满足一致性：对任意从 $n$ 到 $n'$ 、代价为 $c(n,n')$ 的边，

h(n)\le c(n,n')+h(n')

这相当于三角不等式，使沿路径的 $f$ 值不会下降。此时状态从优先队列弹出后，其最佳代价可以稳定确认。

两者都来自放松问题：忽略一部分移动限制后，放松问题的最优代价不会超过原问题，因此可作为下界。Manhattan 距离通常比错位数更接近真实代价；若两个可采纳启发式满足 $h_2(n)\ge h_1(n)$ ，称 $h_2$ 支配 $h_1$ ，通常展开更少节点。

启发式质量还可用有效分支因子 $b^*$ 概括：若找到深度 $d$ 的解共展开 $N$ 个节点，令

N+1=1+b^*+(b^*)^2+\cdots+(b^*)^d

$b^*$ 越接近 1，启发式越能压缩搜索。

模式数据库预先精确计算一部分对象到目标的距离，查询时作为下界。若组合多个模式，必须确认是否会重复计算同一步代价；可取最大值，或在代价可分时相加。

A* 的主要瓶颈常是内存。IDA* 不保存完整 frontier，而是做一轮轮深度优先搜索，只是阈值不再限制深度，而限制 $f=g+h$ ；下一轮阈值取本轮超过上限的最小 $f$ 。它用重复计算换低内存。

有些问题只关心最终配置，例如安排课程表或最小化函数，不关心“怎样一步步到达”。局部搜索只保留当前状态或少量候选，因此空间小，也能处理连续空间；代价是通常不保证全局最优。

每次移动到更好的邻居，直到没有改进。常见陷阱：

可用随机重启、随机选一个更好邻居、允许有限横向移动等变体提高成功率。

除了总接受更好的移动，还以一定概率接受更差移动。若以能量最小化写，变差量为 $\Delta E>0$ 时，接受概率常为：

P=\exp\left(-\frac{\Delta E}{T}\right)

温度 $T$ 高时敢于探索，温度降低后逐渐稳定。降温过快会卡住，过慢则耗时。

同时保留 $k$ 个状态，每轮生成所有后继，再选最好的 $k$ 个。普通束搜索容易让候选迅速变得相似；随机束搜索按质量给概率，能保持更多多样性。

用一群编码后的个体表示候选解，反复执行：

课件用 schema 解释：某些有益的局部模式可能在选择和交叉中传播。不过编码、适应度、交叉与变异若不符合问题结构，算法同样可能早熟收敛。

搜索假设动作规则和目标已知。下一讲强化学习更进一步：环境模型可以未知，智能体只能从实际交互的奖励中估计哪些动作长期更好。