剪枝
复习
- 回溯与搜索树：把选择展开成树并 DFS
- 大 O 记号：衡量搜索规模的增长
- 算法与正确性：剪枝不能误删可行解
TL;DR
- 剪枝提前放弃不可能产生答案的分支
- 它能大幅缩小搜索树的规模
- 常用约束判断和上下界来剪枝
- 剪枝必须保证不会误删可行解
正文
回溯能把所有解都找出来，可搜索树常常大得吓人。如果能让它在搜索过程中早点放弃那些显然没希望的分支，速度就能大幅提升。这个动作，就是剪枝（pruning）。
把死路提前砍掉
搜索树里，很多分支其实从一开始就注定失败。剪枝的思想是：在深入之前就判断出来，直接跳过整棵子树，不去走。
比如摆皇后的问题：每放一个皇后，都要满足“不同行、不同列、不同斜线”。如果某一列已经冲突了，那这一整条分支再怎么往下放都不可能成立——于是立刻回头，省下后续所有徒劳的尝试。
两类常见的剪枝
剪枝的依据，大致有两类：
- 可行性剪枝：根据问题的约束，判断“当前状态已经违反规则”，那就没必要继续
- 最优性剪枝：如果是求最优解，当“当前部分解已经比已知的最好解更差”时，就没必要往下走了
第二类很像我们平时的思考：如果一条路走到一半，花的力气已经超过手头最好的方案，那再往下也没意义，及时掉头。
别把正确答案剪掉
剪枝威力很大，但有一条铁律：绝不能剪掉任何可能产生正确答案的分支。
如果约束判断写得过严、或者上下界估计得不准，就可能把真正的解也一并砍掉，导致算法给出错误结果。“剪得狠”和“剪得对”是两回事——宁可保守一点，也不能误伤。
你会发现，剪枝背后的思路，和前面许多优化如出一辙：用更多的信息（约束、界限）换更少的搜索。 信息越准，越能精准地砍掉死路，又不伤及无辜。
思考题 1
剪枝为什么会显著加快回溯搜索？
思考题 2
设计剪枝时，最需要避免什么错误？
小结
知识点
- 剪枝提前放弃不可能产生答案的分支
- 分为可行性剪枝与最优性剪枝
- 它可大幅缩小搜索树规模
- 剪枝不能误删任何可行解
参考资料
- Wikipedia(zh)：回溯法：常与剪枝配合使用
- Wikipedia(zh)：分支定界：利用上下界进行剪枝的搜索方法
思考题答案（仅供参考）
思考题 1
因为搜索树中很多分支注定无法产生答案，剪枝能在深入之前就识别并跳过整棵子树，避免了大量无谓的尝试，从而把搜索规模显著缩小，速度大幅提升。
思考题 2
最需要避免的是“误剪”——把可能产生正确答案的分支也剪掉，导致结果错误。约束判断和界估计必须保证不排除任何可行解，必要时宁可保守一些。
协议
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
封面图
设计师 | 南国微雪