OI-wiki 搜索优化指南：DFS 剪枝的三种核心方法与实战应用

OI-wiki 搜索优化指南DFS 剪枝的三种核心方法与实战应用【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读本文是 OI-wiki 搜索专题中关于深度优先搜索DFS优化的核心篇章。在算法竞赛中DFS 往往不是正解而是用于拿到部分分的“骗分”手段本文讲解如何通过记忆化搜索、最优性剪枝、可行性剪枝三种优化手段把朴素爆搜的效率提升到可用级别并通过“工作分配问题”的完整示例与仓库源码展示剪枝思想在真实代码中的落地方式。读完本文你将掌握 DFS 剪枝的模板写法、剪枝思路的推导方法以及如何结合状态设计将指数级搜索压缩到可接受的时间复杂度。前言为什么 DFS 需要剪枝DFS深度优先搜索是算法竞赛中最常见的搜索方式大部分题目都可以用 DFS 求解。但正如 docs/search/index.md 所述“纯粹的搜索往往也是得到部分分的手段但可以通过纯粹的搜索拿到满分的题目非常少”因为朴素 DFS 的时间复杂度通常是指数级别的绝大多数情况下它只是“骗分算法”很少能成为正解。既然 DFS 很难成为正解那就设法多骗一点分——这就引出了本文的主题剪枝Pruning。剪枝的核心思想是在搜索过程中提前判断某些分支不可能产生更优解或合法解从而直接放弃对整棵子树的遍历达到“剪掉”搜索树分支、大幅降低时间复杂度的效果。DFS 基础模板先看一段深搜模板后续所有剪枝模板都将在此基础上修改int ans 最坏情况, now; // now 为当前答案 void dfs(传入数值) { if (到达目的地) ans 从当前解与已有解中选最优; for (遍历所有可能性) if (可行) { 进行操作; dfs(缩小规模); 撤回操作; } }其中的ans可以是解的记录那么“从当前解与已有解中选最优”就变成了输出解。这段模板有三个关键结构终点判定递归到目的地时更新全局最优解ans分支枚举for循环遍历当前状态的所有可能性回溯操作递归返回后必须“撤回操作”恢复现场保证兄弟分支在干净的状态下继续搜索。正是这个“撤回操作”的步骤构成了回溯Backtracking的基础参见 docs/search/backtracking.md。剪枝方法最常用的三种最常用的剪枝有三种记忆化搜索、最优性剪枝、可行性剪枝。它们分别从“重复状态”“劣解分支”“非法分支”三个角度压缩搜索空间。记忆化搜索消除重复状态在搜索中相同的传入值往往带来相同的解于是可以用数组把已经算过的结果记下来避免对同一状态重复搜索。这种“以空间换时间”的做法正是记忆化搜索其完整理论在 docs/dp/memo.md 中有系统阐述。模板int g[MAXN]; // 定义记忆化数组 int ans 最坏情况, now; void dfs f(传入数值) { if (g[规模] ! 无效数值) return; // 或记录解视情况而定 if (到达目的地) ans 从当前解与已有解中选最优; // 输出解视情况而定 for (遍历所有可能性) if (可行) { 进行操作; dfs(缩小规模); 撤回操作; } } int main() { // ... memset(g, 无效数值, sizeof(g)); // 初始化记忆化数组 // ... }记忆化搜索能够生效的前提是问题存在大量重叠子状态。以 docs/dp/memo.md 中的「采药」问题为例朴素 DFS 对同一个(pos, tleft)状态可能被重复访问无数次时间复杂度是指数级而加入记忆化数组后每个状态只被访问一次时间复杂度降为 $O(TM)$。值得注意记忆化搜索与递推动态规划在状态表示和转移上高度类似递推通过规定访问顺序避免重复记忆化搜索则通过给已访问状态打标记达到同样目的但记忆化搜索难以使用滚动数组等优化且递归调用有额外开销因此需要视题目权衡选择。最优性剪枝放弃已经更差的分支搜索变慢的另一个原因是当前解已经比已有解差时仍然继续向下搜索。此时只需要在最开始判断一下当前解是否已经差于已有解如果确实更差直接return因为继续搜下去也不可能更新最优解。模板int ans 最坏情况, now; void dfs(传入数值) { if (now比ans的答案还要差) return; if (到达目的地) ans 从当前解与已有解中选最优; for (遍历所有可能性) if (可行) { 进行操作; dfs(缩小规模); 撤回操作; } }最优性剪枝对“求最值”类搜索最小值、最大值问题效果尤其显著。关键点在于ans的初始值必须是“最坏情况”求最小值时初始化为无穷大并且要尽早用较优的解更新ans这样剪枝条件才能尽快生效。这也提示我们搜索顺序会影响剪枝效果——先尝试更可能产生好解的方案可以让ans快速逼近最优值从而剪掉更多分支。可行性剪枝排除非法分支如果搜索进行到当前状态时该状态已经不可能满足题目约束即当前解已不可用继续搜索只会浪费时间。模板int ans 最坏情况, now; void dfs(传入数值) { if (当前解已不可用) return; if (到达目的地) ans 从当前解与已有解中选最优; for (遍历所有可能性) if (可行) { 进行操作; dfs(缩小规模); 撤回操作; } }可行性剪枝是适用范围最广、也最容易被新手忽略的一种。例如在仓库的八皇后参考实现 docs/search/code/backtracking/backtracking_1.cpp 中放置棋子前先检查check[0][i]列、check[1][line i]主对角线、check[2][line - i n]副对角线三个标记数组任何一个已被占用就跳过该位置——这就是典型的可行性剪枝在当前行已经无法继续合法放置时整棵子树直接被放弃。三种剪枝在实际题目中往往是组合使用的例如启发式搜索参考实现 docs/search/code/heuristic/heuristic_1.cpp 中work函数同时用了两条剪枝if (f(t, p) v ans)是最优性剪枝用估价函数估计剩余物品最大价值若加上现有价值仍不超过已知最优解则放弃“不取”分支if (node[t].a p)是可行性剪枝剩余容量装不下当前物品则放弃“取”的分支。剪枝思路如何为具体问题设计剪枝剪枝思路多种多样大多需要结合具体问题分析。本文简要介绍三种常见的通用思路极端法考虑极端情况。如果最极端最理想的情况都无法满足要求那么实际情况搜出来的结果必然不会更优。例如求最短时间时先假设剩余部分耗时为零若当前已耗时间加上理想下界仍超过已知最优解则整棵子树可剪。这里的“理想下界估计”正是启发式函数的核心参见 docs/search/heuristic.md。调整法通过对子树的比较剪掉重复子树和明显没有“前途”的子树。当不同分支在结构上等价、或某分支经过调整后必然不劣于另一分支时可以只保留代表性分支。数学方法借助数学工具估计下界或排除不可能的情况。比如在图论问题中借助连通分量判断可达性在数论问题中借助模方程同余分析、不等式的放缩来估计搜索空间的下界从而提前终止无效搜索。例题实战工作分配问题下面通过 OI-wiki 的经典例题展示剪枝的完整落地过程。题目描述有 $n$$1 \leq n \leq 15$份工作要分配给 $n$ 个人来完成每个人完成一份。第 $i$ 个人完成第 $k$ 份工作所用的时间为一个正整数 $t_{i,k}$$1 \leq t_{i,k} \leq 10^4$其中 $1 \leq i, k \leq n$。试确定一个分配方案使得完成这 $n$ 份工作的时间总和最小。问题建模与朴素思路由于每个人都必须分配到工作可以建立一个二维数组time[i][j]表示第 $i$ 个人完成第 $j$ 号工作所花费的时间。搜索过程如下从第 1 个人开始循环分配工作直到所有人都分配到为第 $i$ 个人分配工作时循环检查每个工作是否已被分配没有则分配给第 $i$ 个人否则检查下一个工作。用一维数组is_working[j]表示第 $j$ 号工作是否已被分配未分配为is_working[j] 0已分配为is_working[j] 1。利用回溯思想在第 $n$ 个人分配完成后回到上一人取消此次分配的工作再去分配下一个工作直到可以分配为止。这样一直回溯到第 1 个人后就能得到所有的可行解。检查一个解是否合法等价于检查取得该可行解时“人”的第一维下标互不相同且“工作”的第二维下标互不相同。而题目要求的是完成 $n$ 份工作的最小时间总和即所有可行解中时间总和最小的一个因此需要定义一个全局变量cost_time_total_min表示目前找到的解中最小的时间总和初始值取对角线工作时间之和即cost_time_total_min sum(time[i][i])。当所有人分配完时比较当前花费count与cost_time_total_min若count更小说明找到了更优解将count赋给cost_time_total_min。剪枝优化最优性剪枝的应用朴素搜索会遍历全部 $n!$ 种排列$n 15$ 时规模高达 $15! \approx 1.3 \times 10^{12}$完全不可接受。这里的剪枝点在于每次计算局部费用变量count的值时如果判断count已经大于cost_time_total_min就没必要再往下分配了因为这时得到的解必然不是最优解。这正是最优性剪枝由于tm[i][j]全部为正整数count在递归过程中只会单调递增一旦count cost_time_total_min当前分支无论怎么分配剩余工作都不可能优于已知解直接剪掉整棵子树。参考代码与源码剖析仓库中的完整参考实现位于 docs/search/code/opt/opt_1.cpp核心逻辑如下#include iostream constexpr int N 16; int is_working[N] {0}; // 某项工作是否被分配 int tm[N][N]; // 完成某项工作所需的时间 int cost_time_total_min; // 完成 n 份工作的最小时间总和 // i 表示第几个人count 表示工作费用总和 void work(int i, int count, int n) { // 如果 i 超出了所能分配的最大工作件数表示分配完成并且 count 比原来 // cost_time_total_min 花费少则更新 cost_time_total_min 的值 if (i n count cost_time_total_min) { cost_time_total_min count; return; } // 回溯思想 if (count cost_time_total_min) { // j 表示第几件工作 for (int j 1; j n; j) { // 如果工作未被分配 is_working 0 if (is_working[j] 0) { // 分配工作 is_working 1 is_working[j] 1; // 工作交给第 i 1 个人 work(i 1, count tm[i][j], n); // 在一轮迭代完成之后返回到上一个人要对此次的工作进行重新分配 // 将 is_working[j] 重设为 0 is_working[j] 0; } } } } using std::cin; using std::cout; int main() { cin.tie(nullptr)-sync_with_stdio(false); int n; cin n; for (int i 1; i n; i) { for (int j 1; j n; j) { cin tm[i][j]; } cost_time_total_min tm[i][i]; } work(1, 0, n); cout cost_time_total_min \n; return 0; }对照代码可以提炼出几条值得借鉴的实现细节剪枝条件即递归入口条件if (count cost_time_total_min)同时充当最优性剪枝与递归守卫让不满足条件的分支根本不进入for循环减少一次不必要的函数调用开销初始上界来自对角线cost_time_total_min的初值取sum(tm[i][i])对角线之和这是一个合法的平凡解第 $i$ 个人做第 $i$ 份工作保证剪枝判断从一开始就有有效的上界初值越大剪枝越晚生效因此也可以通过贪心等办法构造更紧的上界来加速状态用i 1传递而非显式回溯人下标随递归深度自然递增只对手工管理的is_working[]数组做“分配—撤销”的回溯操作代码更简洁输入输出加速cin.tie(nullptr)-sync_with_stdio(false)关闭了 C 与 C 标准流同步在 $n^2 \leq 225$ 的输入规模下影响不大但在更大数据规模下是常见的 IO 优化手段。实测数据验证仓库为该题提供了对应样例数据。输入文件 docs/search/examples/opt/opt_1.in 内容为5 9 2 9 1 9 1 9 8 9 6 9 9 9 9 1 8 8 1 8 4 9 1 7 8 9即 $n 5$tm[i][j]为后五行数据。期望输出 docs/search/examples/opt/opt_1.ans 为5可以验证将工作 1、2、3、4、5 分别分配给第 4、1、5、2、3 个人时总耗时 $8 2 7 9 1 27$而最小方案为第 1 人做第 4 份工作1、第 2 人做第 1 份工作1、第 3 人做第 5 份工作1、第 4 人做第 3 份工作1、第 5 人做第 2 份工作1总耗时恰好为 5与答案一致。在最优性剪枝的帮助下搜索会在累计耗时超过当前上界时立即剪枝实际访问的状态数远小于 $5! 120$。总结剪枝的工程化建议从 docs/search/index.md 对搜索的定义来看搜索是对状态空间的枚举而剪枝的本质是在不影响结果正确性的前提下缩小被枚举的状态空间。综合本文内容给出如下工程化建议先写朴素 DFS 保证正确性再逐步叠加剪枝每加一条剪枝都要确认它不会误删合法解剪枝的安全性优先于剪枝强度三类剪枝按需组合记忆化搜索解决“重复状态”最优性剪枝解决“劣解分支”可行性剪枝解决“非法分支”三者互不冲突巧设ans初始值与搜索顺序更优的初始上界、更可能先搜到好解的顺序都会让最优性剪枝更早生效善用数学估计下界极端法与数学方法连通分量、模方程、不等式放缩能为最优性剪枝提供更强的剪枝判据结合仓库其他专题继续深入剪枝是启发式搜索docs/search/heuristic.md、IDA*、Alpha-Beta 剪枝docs/search/alpha-beta.md等高级算法的基础掌握了本文的三种剪枝就能自然衔接这些进阶优化手段。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考