第五章 综合练习
设计原则
本章练习遵循以下原则（参考 Ch1/Ch2）：
- 问题驱动：不只是"计算复杂度"，而是"为什么这样设计"
- 展示推理：不只给答案，还要展示思考过程
- 多样化：包括反例、变式、边界条件
- 开放性：有"能否改进""如果条件变化"这类问题
一、问题情境与直觉建立
1. 为什么需要回溯？
八皇后问题中，如果只用"随意放置"的方法，会遇到什么困难？用具体例子说明。
2. 剪枝的直觉
为什么 Sudoku 剪枝能将百万步优化到几十步？用类比（如修剪果树）解释。
3. A 的启发函数*
为什么好的启发函数让 A* 效率提升百倍？用 TSP 的例子说明"下界"的作用。
4. 模拟退火的温度
高温和低温分别起什么作用？用金属退火的类比解释。
5. LLM 重复输出
为什么贪心解码会导致 LLM 陷入重复输出？这与爬山法的局部最优陷阱有何相似？
二、方法应用与实现
6. 八皇后实现
完整实现八皇后求解器，统计：
- 4 皇后有多少解？
- 搜索过程追踪：前 3 层的搜索树
7. Sudoku 剪枝实验
对比三种剪枝策略：
- 无剪枝：步骤数？
- 前瞻剪枝：步骤数？
- 约束传播：步骤数？
分析差距原因。
8. A 下界计算*
手工计算 4 城市 TSP 的 MST 下界，验证可容许性。
9. SA 参数实验
测试不同参数（$T_0$、$\alpha$）对模拟退火效果的影响，记录：
- 最优解质量
- 收敛迭代数
10. ToT 评估函数设计
为 Game of 24 设计 ToT 的评估函数，测试：
- 评估准确性（是否与实际效果对应）
- 搜索效率（步骤数）
三、错误诊断与反例
11. 剪枝错误
给定一个"凭直觉剪枝"的代码，分析风险：会不会删掉合法解？
12. A 高估后果*
如果启发函数 $h(n) = 2 \times h^(n)$（高估），A 会发生什么错误？
13. SA 温度太快
如果温度调度太快（$\alpha = 0.5$），模拟退火会困在哪里？
14. ToT 评估不准确
如果 ToT 的评估函数是随机评分，会发生什么？
15. 忘记 unmake_move
回溯算法中忘记"恢复决策"（unmake_move），会发生什么错误？
四、方案比较与权衡
16. DFS vs BFS vs 回溯
对比三种策略：
- 空间复杂度
- 适用场景
- 为什么回溯用 DFS？
17. 剪枝策略对比
对比前瞻剪枝、最受约束、约束传播：
- 剪枝效果
- 计算代价
- 适用场景
18. A vs IDA**
对比两种算法：
- 空间峰值
- 时间成本
- 适用场景（大规模 vs 小规模）
19. 爬山法 vs 模拟退火
对比两种方法：
- 解质量
- 时间成本
- 局部最优陷阱
20. CoT vs ToT vs GoT
对比三种 LLM 推理策略：
- 成功率
- 计算成本
- 适用场景
五、变式与边界条件
21. 无约束排列生成
如果排列生成没有任何约束，回溯效率如何？分析为什么剪枝无效。
22. TSP 的松弛程度
对比三种松弛：
- $h=0$（无松弛）
- MST 松弛
- 强松弛（精确估计）
分析下界质量与计算代价的权衡。
23. Sudoku 的对称性
如果 Sudoku 棋盘有对称性（如旋转对称），如何利用对称性剪枝？
24. 15-puzzle 的曼哈顿距离
为什么曼哈顿距离是可容许的？如果棋盘有障碍，曼哈顿距离是否仍可容许？
25. 自适应温度
设计一个自适应温度调度策略：根据搜索进度动态调整温度。
六、开放设计
26. 改进回溯
如果回溯太慢，如何改进？（提示：剪枝、启发函数、分支限界）
27. 剪枝设计
为排列生成问题设计一个剪枝策略，分析效果。
28. 启发函数创新
为 Sudoku 设计一个 A* 启发函数，验证可容许性。
29. 自适应剪枝
设计一个 Agent，动态选择剪枝策略：
- 监控：搜索进度、剩余候选数
- 决策：何时用前瞻、何时用约束传播
30. LLM 推理策略选择
设计一个 Agent，根据问题特征自动选择推理策略（CoT/ToT/GoT）。
七、综合应用
31. 课程安排问题
用回溯+剪枝解决实际问题：安排课程表（避免时间冲突）。
32. 排课 Agent
设计一个排课 Agent，组合至少两种策略（如回溯 + SA），分析效果。
33. LLM 推理优化
设计一个 Agent，检测 LLM 陷入局部最优，自动切换策略（CoT → ToT）。
34. 真实 TSP
用 A* 或 SA 解决真实城市的 TSP（如中国 10 个省会城市），对比效果。
35. NP-hard 综合挑战
选择一个 NP-hard 问题（如顶点覆盖或 SAT），设计求解器，组合至少两种策略。
八、思考题
36. 为什么回溯保证正确但不保证效率？
回溯的系统枚举保证不遗漏解（正确性），但解空间可能巨大（指数级）。效率取决于什么？
37. 剪枝会不会删掉合法解？
不会，只要剪枝条件基于"必然无解"的逻辑。用例子说明。
38. 为什么理解搜索策略能帮助理解 LLM 推理？
因为它们是同构的——同一计算思想的不同实例。分析局限性对应。
39. 如何设计好的评估函数？
从剪枝经验迁移：外部验证、部分信用、先粗略后精细。
40. 搜索策略的演进路径是什么？
从贪心到 GoT：贪心 → DFS → 回溯 → A* → SA → ToT → GoT。分析每一步的改进。
九、LLM 协同实验
41. 策略对比实验
让 LLM 用不同策略求解同一问题（如 Game of 24），记录：
- CoT 成功率
- ToT 成功率
- 计算成本
42. 评估函数测试
让 LLM 自评候选思想，对比人工评分，分析准确性。
43. 温度调参实验
测试不同 Temperature（0.1、1.0、2.0）对 LLM 输出多样性的影响。
44. 故障诊断
给定 LLM 推理失败案例（如重复输出），诊断是哪种策略的局限，推荐改进。
45. 综合挑战
用 LLM 协同解决 Sudoku：
- CoT：线性推理
- ToT：多候选探索 对比效果。
附录：实验数据模板
剪枝效果对比
| 剪枝策略 | 步骤数 | 时间 | 剪枝判断 |
|---|---|---|---|
| 无剪枝 | |||
| 前瞻剪枝 | |||
| 约束传播 |
A* vs 回溯
| n | 回溯节点数 | A* 节点数 | 效率倍数 |
|---|---|---|---|
| 8 | |||
| 10 |
SA 参数实验
| T₀ | α | 最优解质量 | 收敛迭代数 |
|---|---|---|---|
| 100 | 0.9 | ||
| 1000 | 0.99 |
参考文献：
- Skiena S S. The Algorithm Design Manual[M]. 3rd ed. Springer, 2020.
- Yao S, Yu D, Zhao J, et al. Tree of Thoughts[C]//NeurIPS. 2023.
- Besta M, et al. Graph of Thoughts[C]//AAAI. 2024.
- Huang J, et al. LLMs Cannot Self-Correct Reasoning[C]//ICLR. 2024.
- Snell C, et al. Scaling LLM Test-Time Compute[J]. 2024.