Acwing 算法提高课 剪枝
【算法竞赛进阶指南P103】
剪枝策略:
优化搜索顺序 : 原则是优先搜索分支少的状态
排除等效冗余 : 即不重复搜索等效的状态
可行性剪枝 : 对于已经不可能达到合法答案的分支提前终止,有些题目限制范围是一个区间,则这种剪枝也被称为"上下界剪枝"
最优性剪枝 : 记录全局最优值,若已经花费的代价超过这个最优值就没有继续往下搜的必要了
(记忆化) : 即dp
实例
T1 小猫爬山
本题(Acwing165.小猫爬山)中我们可以使用1和4
具体来说,可以从重猫到轻猫枚举,同时在搜索过程中记录缆车已经搜索到的最优数,若超过这个值就不用再搜了
T2 数独
本题(Acwing166.数独)
我们先考虑如何去搜索:
枚举点 枚举填哪个数 当得到一张完全合法的方案时输出
那么将如何去剪枝呢
我们可以使用优化搜索顺序,先去枚举可能性小的点,注意这里是每次dfs过程中都在枚举
可行性剪枝,即只填合法的数
*位运算优化(本题特有):
使用一个九位二进制数来表示每一行、每一列、每一宫格上的状态(若第i位为1则说明i + 1填过了),
则某一个点的状态可通过对行列宫格取交集即可,同时利用lowbit()来求1的个数, 能使求出某个点能填数字个数的操作时间复杂度降至将近
T3 木棒
我们先来考虑是怎么来进行dfs的
框架为:
从小到大枚举木棒的长度枚举每一根木棒的拼法若合法了则回溯输出
我们考虑如何进行剪枝
优化搜索顺序, 即从小到大枚举
排除等效冗余
- 可以采用组合数的方式来枚举,具体来讲,我们可以在拼接某一根木棒时,以从前往后的顺序,避免重复
- 当一个木棍在此方案中不合法时,把这个木棍换成相等长度的木棍也均不合法
- 当一个木棍在一根木棒的开头且不合法时,无需继续搜索可直接回溯
- 当一个木棍在一根木棒的末尾且不合法时,无需继续搜索可直接回溯
我们在枚举每一根木棍长度时只需要枚举sum(所有木棍的总长度)的因数即可
对于上方的剪枝2-3和2-4虽然形式对称但是证明思路不同
- 对于2-3 : 若这个在开头的木棍在其它位置合法,由于木棍与木棍、木棒与木棒可交换顺序，则必定可以构造出一组该木棒在开头且合法的解 文章末尾有对该点更加形象的解释
- 对于2-4 : 对于这根只剩下如此长度的木棒,若不使用这一根木棒则要么换用更小的木棒,要么使用长度相等的木棒 对于后者,易知是不合法的;对于前者当前的条件的不合法对更小木棒的不合法具有充分性,故也是不合法的、
对于性质2-3的更加详细解释
$$\text{如果对于}
\def\arraystretch{1.5}
\begin{array}{c:c:c}
2 & 3 & 4 \ \hline
2 & ? & ? \
\hline
? & ? & ?
\end{array}
\text{是不合法的}$$
$$\text{若后续搜索存在合法解}
\def\arraystretch{1.5}
\begin{array}{c:c:c}
2 & 3 & 4 \ \hline
? & ? & ? \
\hline
? & 2 & ?
\end{array}\iff
\def\arraystretch{1.5}
\begin{array}{c:c:c}
2 & 3 & 4 \ \hline
? & ? & ? \
\hline
2 & ? & ?
\end{array}\iff
\def\arraystretch{1.5}
\begin{array}{c:c:c}
2 & 3 & 4 \ \hline
2 & ? & ? \
\hline
? & ? & ?
\end{array}$$