在C++算法竞赛中，深度优先搜索（DFS）是一把锋利的双刃剑。它思想简单、实现直观，但裸的DFS往往会在指数级的状态空间中迷失——题目给的n=30，你的代码跑了3秒还没出结果，而时限只有1秒。这时候，你需要的不是放弃DFS，而是给它装上“剪刀”：剪枝。
一个优秀的剪枝可以将搜索树从庞然大物修剪成清秀的小树，让本来1秒跑不完的数据在0.1秒内轻松通过。本文将系统介绍DFS中常用的剪枝策略，包括可行性剪枝、最优性剪枝、搜索顺序优化、记忆化搜索、对称性剪枝等，全部配有C++代码示例和复杂度分析。
一、DFS为什么慢？认识搜索树
DFS本质上是在遍历一棵决策树。树的根是初始状态，每个分支对应一次选择，叶子节点对应终止状态（解或无解）。最坏情况下，DFS的时间复杂度等于树中节点的个数。
举例：求1~n的所有排列，裸DFS会生成n!个叶子节点，加上内部节点，总复杂度O(n!)。当n=15时，15! ≈ 1.3×10¹²，根本不可能跑完。
剪枝的核心思想：在递归早期就判断出当前分支不可能产生有效解或最优解，从而直接返回（剪掉整棵子树）。
二、可行性剪枝：不可能就回头
可行性剪枝是最直观的剪枝。当你发现当前状态已经违反问题约束，或者无论如何都无法达到合法解时，立即回溯。
经典例子：N皇后问题
在N×N棋盘上放置N个皇后，使其互不攻击。裸DFS每一行放一个皇后，检查是否与之前冲突，复杂度O(N!)。但我们可以提前判断：如果当前列或对角线已被占用，直接跳过。
bool col[20], diag1[40], diag2[40];
void dfs(int row, int n) {
if (row == n) { ans++; return; }
for (int c = 0; c < n; c++) {
if (!col[c] && !diag1[row-c+n] && !diag2[row+c]) {
col[c] = diag1[row-c+n] = diag2[row+c] = true;
dfs(row+1, n);
col[c] = diag1[row-c+n] = diag2[row+c] = false;
}
}
}
这里的可行性剪枝是：如果列或对角线被占，就不尝试这个位置。这比先放置再检查要高效得多，因为提前排除了大量分支。
更强剪枝：剩余位置判断
在数独求解中，如果当前格子可填的数字都不满足行/列/宫唯一性，直接回溯。更进一步的，可以用“最少可选数字”的启发式（见下一节）。
三、最优性剪枝：已经比答案差就放弃
对于求最优解（如最小值、最大值）的DFS，我们往往维护一个全局最优解best。当当前搜索路径的代价已经不可能超过（或小于）best时，直接剪枝。
例子：整数拆分的最小乘积
将一个正整数n拆分成若干个正整数之和，要求这些数的乘积最大（或最小）。在DFS搜索过程中，如果当前乘积已经小于目前找到的最佳值，且之后再怎么乘也不会更大（比如剩余部分全拆成1），就可以剪枝。
更常用的是旅行商问题（TSP）的DFS解法：维护当前已走路径长度，如果当前长度已经大于等于全局最短回路长度，就不必再往下搜。
int best = INF;
void dfs(int u, int cost, int visited_cnt) {
if (cost >= best) return;
if (visited_cnt == n) {
best = min(best, cost + g[u][0]);
return;
}
for (int v = 0; v < n; v++) {
if (!vis[v]) {
vis[v] = true;
dfs(v, cost + g[u][v], visited_cnt+1);
vis[v] = false;
}
}
}
这种剪枝的效果取决于best更新的快慢。所以通常配合搜索顺序优化，先搜索可能产生更优解的分支，让best尽快变小，从而剪掉更多分支。
四、搜索顺序优化：把好的分支放在前面
搜索树的形状直接影响剪枝效果。合理的顺序可以尽早找到解（或优解），或者尽早发现问题。
1. 分支因子小的优先
在数独中，优先选择可选数字最少的空格进行尝试。因为该位置的决策分支较少，失败后能迅速回溯，而且一旦填对，能极大限制其他空格的可能取值。
bool solve_sudoku() {
int best_row = -1, best_col = -1, min_options = 10;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == 0) {
int cnt = count_options(i, j);
if (cnt < min_options) {
min_options = cnt;
best_row = i; best_col = j;
if (min_options == 1) break;
}
}
}
}
if (best_row == -1) return true;
for (int num = 1; num <= 9; num++) {
if (is_valid(best_row, best_col, num)) {
board[best_row][best_col] = num;
if (solve_sudoku()) return true;
board[best_row][best_col] = 0;
}
}
return false;
}
2. 从大到小排序
在整数拆分、物品选取等问题中，优先尝试大的数字。例如整数拆分求乘积最大：先尝试大的加数，可以让乘积快速增长，便于最优性剪枝。又如组合求和（给定数组，找和为target的组合），先将数组从大到小排序，可以更早判断“剩余数字全取最小也达不到target”的情况（可行性剪枝）。
3. 对称性剪枝
当搜索空间存在对称状态时，只搜索其中一个代表。常见于组合问题：比如求{1,2,3}的所有子集，我们规定选择的元素必须递增，避免重复搜索{1,2}和{2,1}。
实现方式：在DFS参数中传入start，每次只从start开始选择下一个元素。
void subsets(vector<int>& nums, int start, vector<int>& cur) {
for (int i = start; i < nums.size(); i++) {
cur.push_back(nums[i]);
subsets(nums, i+1, cur);
cur.pop_back();
}
}
五、记忆化搜索：用空间换时间
记忆化搜索是DFS + 缓存。当某个状态（由若干参数唯一确定）已经被计算过时，直接返回之前的结果，避免重复搜索。
典型应用：动态规划的状态转移方程可以用DFS+记忆化实现。例如斐波那契数列、矩阵中的最长递增路径、博弈问题（如SG函数）等。
int memo[N][M];
int dfs(int i, int j) {
if (memo[i][j] != -1) return memo[i][j];
int res = 0;
return memo[i][j] = res;
}
注意：记忆化要求状态是无后效性的——即当前状态的解只依赖于后面的状态，不受前面路径的影响。
六、综合案例：从1秒到0.1秒——数独求解器的剪枝实战
以标准数独（9×9）为例，裸DFS回溯（按行优先顺序）在普通谜题上可能需要几十毫秒，但在极难题目（如“世界最难数独”）上可能要秒级甚至超时。加入以下剪枝后，可以轻松在0.05秒内解出：
-
维护行、列、宫的数字占用位掩码，每次判断候选数字 O(1)，而非O(9)循环。
-
最少可选数字优先（MRV启发式），每次找到候选最少的格子。
-
正向检查：填一个数字前，检查它是否导致同行/列/宫无解（其实MRV已隐含）。
-
递归前预计算每个格子的候选数字表，动态更新，回溯时恢复。
经过这些优化，搜索树节点从百万级降到数千级，速度提升上百倍。
七、常见错误与调试建议
-
剪枝条件过于乐观：剪掉了可能产生合法解的分支，导致答案错误。必须保证剪枝条件充分必要（或至少安全）。
-
忘记回溯状态：在递归前修改了全局变量，递归后没有恢复，导致后续搜索状态错乱。务必成对出现。
-
记忆化key不完整：漏掉了影响结果的状态参数，导致返回错误缓存。仔细检查递归函数的参数是否包含了决定结果的所有信息。
-
搜索顺序优化过度：在求所有解的问题中，顺序优化可能导致解的排列顺序不同，但不影响正确性；在求第一个解的问题中，顺序影响效率但不影响结果。
调试技巧：
八、总结：剪枝思维导图
一个经典的DFS剪枝流程如下：
开始DFS
│
可行性剪枝 ──否──→ 返回
│是
最优性剪枝 ──是──→ 返回（如果当前已经不可能更优）
│否
对称性剪枝 ──跳过重复状态
│
选择下一个分支（按优化顺序）
│
递归调用
│
回溯恢复状态
这五种剪枝方法并不是互斥的，通常需要结合使用。掌握剪枝的艺术，意味着你能够深入理解问题的结构，找出冗余的搜索空间，并用代码精确地切除它们。
记住：裸DFS是暴力，加了剪枝的DFS是艺术。当你下一次遇到搜索规模看似不可接受的题目时，不要急着否定DFS——先想想，你能剪掉哪些树枝？也许原本需要1秒的程序，经过几处精妙的剪枝，真的就能跑进0.1秒。
现在，打开你的IDE，找一道之前超时的搜索题，尝试应用本文的技巧重新实现。你会惊讶于剪刀的力量。 |
