5.4 启发式搜索——从最优到"够好"
问题情境：复杂启发反而更差
顶点覆盖问题的反直觉结果
问题：找最小顶点集合，覆盖所有边。
解法 A：简单启发（最大匹配）
算法：找最大匹配，取匹配端点
近似比：2（解最多是最优的 2 倍）
时间：O(m)（边数）解法 B：复杂启发（贪心度数）
算法：每次选度数最大的顶点
近似比：Θ(log n)（可能比最优差 log n 倍）
时间：O(n log n)困惑：为什么"更聪明"的贪心度数算法，近似比反而更差？
第一次尝试：爬山法
小明想了个简单方法：从随机解开始，每次改进一点。
def hill_climbing(initial):
"""爬山法"""
current = initial
while True:
neighbors = get_neighbors(current)
best = min(neighbors, key=cost)
if cost(best) < cost(current):
current = best
else:
break # 无改进，停止
return current小明用在 TSP 上测试，发现一个问题：总是困在局部最优，无法到达全局最优。
困惑：为什么局部最优这么难逃离？
小红画了个图：
代价函数地形
↗ 全局最优（最高峰）
/
/ ↗ 局部最优（小山峰）
/ /
↗ 当前解 → 爬山 → 局部最优（被困）直觉：爬山法只接受"上升"，拒绝"下降"——困在小山峰，无法到达最高峰。
直观思路：允许"错误"转移
模拟退火的直觉
类比：金属退火
- 高温：分子剧烈运动，混乱排列
- 缓慢降温：分子逐渐有序，趋向低能量状态
- 偶尔"错误"：某些分子暂时回到高能量（为了跳出局部陷阱）
应用到搜索：
- 高温：随机游走，广泛探索
- 低温：贪心收敛，精细调整
- 接受"错误"：偶尔接受更差的解，跳出局部最优
Metropolis 函数
接受劣转移的概率：
$$P(\text{accept}) = e^{-\Delta E / T}$$
其中：
- $\Delta E$：代价增加（新解比当前解差多少）
- $T$：当前温度
直觉解释：
- 高温 $T$：$P \approx 1$ → 接受几乎所有转移（混乱）
- 低温 $T$：$P \approx 0$ → 只接受改进（有序）
- $\Delta E$ 大：$P$ 小 → 差很多的解不太可能接受
- $\Delta E$ 小：$P$ 大 → 差一点的解可能接受
规范定义：局部搜索框架
邻域与局部最优
邻域：解的"附近"所有解（通过小扰动可达）。
局部最优：邻域中没有更优解的点。
全局最优：整个解空间中最优的点。
模拟退火算法
def simulated_annealing(initial, neighbor, cost, T0=1000, alpha=0.99):
"""模拟退火"""
current = initial
best = current
T = T0
while T > T_min:
# 生成邻居
new = neighbor(current)
delta = cost(new) - cost(current)
# 判断接受
if delta < 0 or random() < exp(-delta / T):
current = new
if cost(new) < cost(best):
best = new
T *= alpha # 冷却
return best代价函数设计：部分信用
为什么需要部分信用？
问题：中间状态难以评价。
示例：
- TSP 部分路径：未完成回路，如何评价？
- SAT 部分赋值：未赋值所有变量，如何评价？
关键：代价函数必须给中间状态部分信用。
TSP 的代价函数
def cost_with_penalty(path, cities, distances):
"""带惩罚的代价函数"""
# 已选路径
length = total_length(path, distances)
# 未访问城市惩罚
unvisited = [c for c in cities if c not in path]
penalty = len(unvisited) * 10
return length + penalty正确性与复杂度分析
收敛性（概率意义）
定理：模拟退火在无限时间后概率收敛到全局最优。
前提：温度调度合适（足够慢）。
实际：有限时间内可能不收敛 → 只能期望"够好"的解。
复杂度
| 算法 | 时间 | 空间 |
|---|---|---|
| 爬山法 | $O(k \cdot n)$ | $O(n)$ |
| 模拟退火 | $O(k \cdot n)$ | $O(n)$ |
| A* | 取决于 $h$ | 取决于 $h$ |
关键洞察：模拟退火时间可控（迭代次数），空间最优 $O(n)$。
反例：贪心度数为什么更差？
构造反例
二部图：
层 0：1 个顶点（连接层 1 的所有顶点）
层 1：2 个顶点（各连接层 2 的半数顶点）
层 2：4 个顶点
...
层 k：2^k 个顶点
贪心度数选择顺序：
层 0 → 层 1 → 层 2 → ... → 层 k
解大小：1 + 2 + 4 + ... = 2^{k+1} - 1
最优解：
层 k 的所有顶点（覆盖所有边）
解大小：2^k
近似比：约 2（常数）
但实际构造更精细后：Θ(log n)关键洞察：贪心度数"局部最优"，但全局来看，选择了太多顶点。
练习
基本理解
直觉解释：为什么模拟退火叫"退火"？
对比分析：爬山法和模拟退火的区别是什么？
温度作用：高温和低温分别起什么作用？
方法应用
SA 实现：实现 TSP 的模拟退火求解器。
参数实验：测试不同 $T_0$、$\alpha$ 的效果。
代价函数设计：为 SAT 设计一个代价函数。
错误诊断
诊断错误：温度调度太快会发生什么？
代价函数错误：如果代价函数不给部分信用，会发生什么？
方案比较
爬山 vs SA：对比两种方法的效率和解质量。
贪心度数 vs 匹配：解释为什么复杂启发更差。
开放设计
改进思路：如何改进爬山法，避免局部最优陷阱？
自适应温度：设计一个动态调整温度的策略。
过渡：搜索策略的本质是什么？从 DFS 到 A*，从回溯到 SA——我们看到的是同一思想的演进。下一节：LLM 推理与搜索策略的同构性。
参考文献：
- Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by Simulated Annealing[J]. Science, 1983.
- Vazirani V V. Approximation Algorithms[M]. Springer, 2001.