做算法题或者写搜索类程序的人，应该都经历过这种崩溃：回溯算法写出来，逻辑全对，样例也能过，一提交就是超时。问题就出在搜索分支太多，把一整棵搜索树硬生生走到底。我最早对剪枝产生深刻体感，是在刷N皇后问题的时候——8皇后如果按最粗暴的方式枚举，是8^8量级的候选组合；而加了约束剪枝之后，整个搜索过程只需要几千次递归调用，这种量级差距用“拯救”来形容毫不夸张。

这篇文章我会把回溯算法的剪枝思路完整拆开讲，从搜索树为什么会爆炸讲起，到四类核心剪枝方法，再亲手带你用N皇后、0-1背包、数独和Alpha-Beta博弈搜索四个经典场景把代码写出来。适合正在刷LeetCode回溯题、写搜索类项目、或者做博弈AI的同学参考，看完你至少能少走三个月弯路。

1. 回溯算法的困境：搜索分支为什么会爆炸

1.1 回溯的本质是带后悔药的DFS

回溯算法本质上就是深度优先搜索（DFS）加上状态恢复。你沿着一条路往下试探，发现走不通就退回来，恢复现场，再选另一条路。这个“退回来”的操作，在代码里表现为递归返回后撤销对状态变量的修改。

举个例子，求一个数组的全排列，最直觉的写法就是这样的：

def permute(nums): result = [] path = [] used = [False] * len(nums) def dfs(): if len(path) == len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] = True path.append(nums[i]) dfs() path.pop() used[i] = False dfs() return result

这个写法是教科书级的，但也是理解剪枝最好的起点。当len(path) == len(nums)时，我们得到一个完整排列；每次循环选一个没用过的数，递归下去。没有做任何“提前判断”的工作，所有分支都会被探索一遍。

这里的核心问题是：如果输入有10个数，全排列是10! = 3,628,800个结果，搜索树的节点数大约是10!再加上中间路径的节点数，整体规模直接奔着千万级去了。一旦输入数量到15，15!已经超过1.3万亿，任何一个普通程序都不可能枚举完。

1.2 搜索树的膨胀速度远超直觉

很多人对搜索树规模没有概念，我习惯用一个简单公式来估算：搜索树的节点数约等于“每一层的分支数的连乘”，也就是分支因子depth次方。分支因子为n、深度为m的搜索树，叶子节点数是n^m。

拿八皇后举例，如果不加任何约束，每一行有8个列位置可选，放8行，那就是8^8 = 16,777,216个叶子节点。看着不算特别大，但如果是12皇后，12^12约等于8.9万亿，瞬间爆炸。现实中的搜索问题，比如数独、排班调度、路径规划，分支因子和深度都比这个夸张，完全枚举在物理上是不可能的。

这就是为什么剪枝不是优化手段，而是回溯算法的必需品。一个没有剪枝的回溯算法，在绝大多数真实场景下，只是把“超时”变成了“MLE”或者“死循环”的另一种写法。

1.3 先分清两种“剪枝”概念

现在网络上搜“剪枝算法”，经常能看到两种完全不同的东西。一个是深度学习里的模型剪枝，分成结构化剪枝和非结构化剪枝，指的是把神经网络里不重要的权重、通道、层去掉，压缩模型体积。另一个就是我们这篇文章聊的搜索剪枝，指在回溯搜索过程中提前终止对不可能产生解的分支的探索。

两者的英文都是pruning，但底层逻辑完全不同。模型剪枝砍的是参数，搜索剪枝砍的是搜索树的子树。这篇文章只讲后者，别再混淆了。

2. 剪枝的本质与四类核心方法

2.1 可行性剪枝：不满足约束的分支直接砍掉

可行性剪枝是最基础也最常用的一类。它的逻辑非常简单：在递归的任意一层，如果当前的局部选择已经违反了题目的约束条件，那这个分支无论怎么往下走都不可能得到一个合法解，直接return。

以N皇后为例，题目约束是“任意两个皇后不能在同一行、同一列、同一条对角线上”。我们按行放置皇后，每行放一个，那么行约束天然满足。剩下的就是列冲突和两条对角线冲突。

def solve_n_queens(n): cols = [False] * n diag1 = [False] * (2 * n - 1) # r + c diag2 = [False] * (2 * n - 1) # r - c + n - 1 board = [-1] * n result = [] def backtrack(r): if r == n: result.append(board[:]) return for c in range(n): if cols[c] or diag1[r + c] or diag2[r - c + n - 1]: continue board[r] = c cols[c] = diag1[r + c] = diag2[r - c + n - 1] = True backtrack(r + 1) cols[c] = diag1[r + c] = diag2[r - c + n - 1] = False board[r] = -1 backtrack(0) return result

每走一步之前，先检查列和两条对角线是否已经被占用。注意对角线冲突的两种表示方式：r + c恒定表示“/”方向的对角线，r - c + n - 1恒定表示“\”方向的对角线。这个偏移量n - 1是为了把负的下标转为非负索引，避免数组越界。

这道题里，“行列冲突”就是约束条件。只要当前格子已经在某一列被占用，后面的行无论再怎么放，这个解都不会合法，完全没必要往下走。这一个剪枝，直接把8皇后的搜索从1677万个叶子节点砍到只有大约2000次递归调用。记住：可行性剪枝是“保底”的，任何回溯题至少要做到这一步。

2.2 最优性剪枝：用上下界干掉注定吃亏的路径

可行性剪枝只管“合法不合法”，但很多问题的目标是求“最优解”，比如最大收益、最小代价。这类问题里，即便一个分支能走到合法解，也不代表它值得走——因为已经有一个更优的解在手了。

最优性剪枝的核心思路是：计算当前路径的“理论上限”（如果是求最大值）或“理论下限”（如果是求最小值），跟当前已知最优解比较。如果上限也不可能超过已知最优解，那这个分支可以直接剪掉。

以0-1背包为例，经典回溯解法是这样：

def knapsack_max_value(values, weights, capacity): n = len(values) items = list(zip(values, weights)) items.sort(key=lambda x: x[0] / x[1], reverse=True) v = [x[0] for x in items] w = [x[1] for x in items] best = 0 def bound(i, cur_w, cur_v): if cur_w >= capacity: return 0 total_v = cur_v remaining = capacity - cur_w j = i while j < n and w[j] <= remaining: remaining -= w[j] total_v += v[j] j += 1 if j < n: total_v += v[j] * remaining / w[j] return total_v def backtrack(i, cur_w, cur_v): nonlocal best if i == n: best = max(best, cur_v) return if cur_w + w[i] <= capacity: backtrack(i + 1, cur_w + w[i], cur_v + v[i]) if bound(i + 1, cur_w, cur_v) > best: backtrack(i + 1, cur_w, cur_v) backtrack(0, 0, 0) return best

这里最关键的代码是bound函数。它的含义是：假设当前已经选了i之前的物品，剩余容量还能装多少价值。为了估算上限，用贪心的方式把剩余物品按单位价值从高到低“全部塞进去”——哪怕某个物品只能分割一部分，也用分数填满。这个分数装填的结果就是当前路径的价值理论上限。

如果这个理论上限都不超过已经找到的best，那这条路径继续往下走，即使走得再深，也不可能刷新最优值，果断剪掉。

留意排序的细节。我把所有物品按单位价值从高到低排序，这样贪心放松的上界会更紧，剪枝效率更高。如果排序不处理，贪心上界可能松弛得厉害，剪枝效果大打折扣。这个排序值得反复体会，它是整个最优性剪枝的隐形功臣。

2.3 重复状态剪枝：别让同一个状态被算三遍

第三类剪枝比较隐蔽，但也非常常见。很多搜索问题会在不同路径上抵达相同的“状态”——比如相同的剩余物品集合、相同的剩余容量、相同的棋盘局面。如果每次都从头搜索，等于反复计算同一个子问题。

最直接的解决办法是哈希去重或记忆化搜索。用一个字典记录“状态 -> 已计算的最优结果”，递归时先查表，命中就直接返回。

from functools import lru_cache def knapsack_with_memo(values, weights, capacity): n = len(values) @lru_cache(None) def dfs(i, cap_left): if i == n: return 0 # 不选当前物品 ans = dfs(i + 1, cap_left) # 选当前物品 if weights[i] <= cap_left: ans = max(ans, values[i] + dfs(i + 1, cap_left - weights[i])) return ans return dfs(0, capacity)

状态是(i, cap_left)，表示已经处理到第i个物品、剩余容量为cap_left时的最大价值。因为在每个状态下，未来的决策完全由这两个参数决定，所以计算结果可以安全缓存。原来需要重复计算大量子问题，现在每个状态只算一遍。

不过要注意，记忆化适合子问题重叠度高的场景。如果每个状态只出现一次，比如前面那种已经做了排序和上界剪枝的回溯版本，记忆化的收获就不大。两类写法有各自的适用场景，不是用得多就好，而是合适就好。

2.4 搜索顺序优化：先搜哪个分支，影响超乎想象

这一条常被忽略，但效果往往比花哨的剪枝函数更猛。搜索顺序决定了“找到好解的速度”和“剪枝条件生效的速度”。

求最大值的问题，先探索大概率产生更优解的分支，就能尽早抬高best，让后续分支更容易被上界剪枝砍掉。求可行解的问题，先探索约束最强的分支，能更快触发冲突，提前剪掉大量分支。

在N皇后问题里，列冲突最少的行先放，明显减少尝试次数；在数独问题里，找候选数最少的空格先填，这就是著名的MRV启发式（Minimum Remaining Values）。一个简单的排序，经常能把搜索树缩小几个数量级。

搜索顺序优化的本质是：剪枝条件只有在信息充分的情况下才有效。你早一点拿到一个较好的可行解，后续的bound > best判断就会更频繁地为真，剪枝也就更狠。我做过一个实验，同一个0-1背包数据集，物品按单位价值降序排列后的回溯耗时只有乱序排列的1/10，就是这么离谱。

3. 实战拆解：三个经典问题的剪枝套路

3.1 N皇后：从暴力到位运算加速的完整演化

N皇后是最适合练习可行性剪枝的题目。上面给的版本用了三个布尔数组，已经把搜索规模压到很小。但如果你想要更极致，可以用位运算替代布尔数组，同时能进一步压缩常系数。

位运算的核心思路是用三个整数分别表示列、主对角线、副对角线的占用状态，每一位代表一列的位置：

def solve_n_queens_bit(n): result = [] board = [-1] * n def backtrack(r, cols, diag1, diag2): if r == n: result.append(board[:]) return available = ((1 << n) - 1) & ~(cols | diag1 | diag2) while available: p = available & -available c = p.bit_length() - 1 board[r] = c backtrack(r + 1, cols | p, (diag1 | p) << 1, (diag2 | p) >> 1) board[r] = -1 available &= available - 1 backtrack(0, 0, 0, 0) return result

说明一下位运算的机理：cols的二进制第i位为1表示第i列已被占用；diag1的二进制第i位为1表示“r+c=i”这条主对角线被占用；diag2的二进制第i位为1表示“r-c+n-1=i”这条副对角线被占用。available的值是当前行所有可放位置组成的位掩码，拿到最低位的1（p = available & -available）就对应一个可放置的列。

进入下一层递归时，主对角线掩码要左移一位，副对角线掩码要右移一位，因为随着行号增加，对角线冲突的编号恰好平移一位。这是位运算回溯的经典代码，网上很多版本都是这个套路，建议自己手写两遍彻底吃透。性能上，位运算版本比布尔数组版本大约再快3到5倍，在大N（比如N=20）时可以显著感受差距。

实际测试中，用布尔数组版本的8皇后，递归调用约2000次；12皇后大约几十万次；到了16皇后，布尔版本已经需要一段时间的等待，而位运算版本仍然能快速返回。所以如果你要挑战大N，位运算不是炫技，而是实实在在的工程需要。

3.2 0-1背包：上界函数和搜索顺序如何协同发力

0-1背包用回溯+上界剪枝，是理解最优性剪枝最好的例子。前面代码里已经出现过核心逻辑，这里再拆解一遍执行流程，顺带讲清楚上界函数是怎么和搜索顺序协同的。

假设数据是这样：容量10，三个物品（价值5重量3，价值7重量4，价值3重量2）。先按单位价值排序，三个物品单位价值分别是1.67、1.75、1.5，排序后顺序是：物品2（7/4=1.75）、物品1（5/3=1.67）、物品3（3/2=1.5）。

搜索从第0个物品开始，两条分支：选与不选。选则有价值7，不选则为0。每条分支继续向下，每一步都调用bound估算剩余容量的价值上限。关键点在于，一旦在某个分支上找到一个较好的可行解，比如“选物品2和物品3”总价值10，best就被抬到10。后续不选物品2的分支，即使把剩余容量全塞满，上界也只有7，低于10，直接不再深入。

为了让这个“较早发现好解”的概率最大化，我们把价值高、重量轻的物品放在前面优先搜索。这是搜索顺序优化和最优性剪枝的组合拳，两者缺一不可。如果顺序乱排，前期找到的best太小，上界剪枝很难生效，搜索就退化成暴力枚举。

实测中，同样100个物品的数据集，排序后剪枝的回溯平均在几毫秒内完成；不排序直接上回溯，可能几秒都跑不完。所以我每次写回溯题，第一件事就是看能不能通过排序让“好分支”先被探索。

这个上界函数还有改进空间。比如可以加一个“当前已选重量+剩余最小重量”判断，剩余物品全部塞进去也装不满就不行；或者用动态规划预处理求剩余物品子集的精确上界。但作为回溯剪枝，贪心放松的上界已经足够日常使用了，太复杂的上界计算会喧宾夺主，反而拖慢整体速度。

3.3 数独求解：MRV启发式让搜索量断崖式下降

数独是另一个极好的剪枝练习场。暴力回溯填数独的写法很简单：从左到右从上到下，找到空格就试着填1到9，填完检查行、列、九宫格是否冲突。但这种写法在比较难的数独谜题上会非常慢，因为搜索顺序完全由棋盘布局决定，而没有任何智能。

真正提升数独求解性能的关键是MRV启发式：每次选择候选数字最少的空格来填。候选数字少，意味着分支因子小，搜索树整体就小；更重要的是，候选数为0时立刻就能判断这条路径失败，不用再往下白白探索。

def solve_sudoku(board): def candidates(r, c): used = set(board[r]) | {board[i][c] for i in range(9)} br, bc = r // 3 * 3, c // 3 * 3 for i in range(br, br + 3): for j in range(bc, bc + 3): used.add(board[i][j]) return [d for d in range(1, 10) if d not in used] def find_next(): best_r = best_c = -1 best_len = 10 for r in range(9): for c in range(9): if board[r][c] == 0: cands = candidates(r, c) if len(cands) < best_len: best_len, best_r, best_c = len(cands), r, c if best_len == 0: return best_r, best_c return best_r, best_c def backtrack(): r, c = find_next() if r == -1: return True for d in candidates(r, c): board[r][c] = d if backtrack(): return True board[r][c] = 0 return False backtrack() return board

这段代码里，find_next每次扫描整个棋盘，找到当前候选数最少的格子。注意候选数是在递归内部动态计算的——因为你每填一个数，会影响同行、同列、同九宫格其他格子的候选数集合。“动态更新+选择最小候选集”，这就是MRV启发式的完整闭环。

可以用一个生活化类比来理解：做抉择时，哪个选项最受限就先决定它，如果最受限的地方都没有可行选项，整个方案必然失败，趁早止损比在宽松的地方纠结一千次都划算。

实测中，MRV版本对绝大多数标准9x9数独都能在毫秒级完成求解，而固定顺序扫描的回溯在“困难”级别谜题上可能要十几秒甚至分钟级。如果你有写数独游戏或者数独解题器的需求，这个优化是必须的。

4. Alpha-Beta剪枝：博弈树上的最优选择搜索

4.1 极大极小值搜索是怎么工作的

下棋类AI是回溯搜索最经典的应用场景。假设你执黑棋，对方执白棋，你希望最终局面对自己最有利，对方希望对他最有利。那在搜索时，就轮流以“己方取最大值、对方取最小值”的视角来评估局面。这就是极大极小值搜索（Minimax）。

搜索树的每一层代表一步棋：偶数层是己方走棋，选择评估值最大的分支；奇数层是对方走棋，选择评估值最小的分支。叶子节点的评估值由局面评估函数给出，正的表示对己方有利，负的表示对对方有利。

举个例子，深度为4的搜索可以这样理解：你走一步，对方走一步，你再走一步，对方再走一步，到达叶子局面，然后从叶子开始往上回溯。对方会选那些让评估值最小的走法，而你会选让评估值最大的走法。这个交替取最大/取最小的过程，保证了最终的评估值对应双方都做出最优选择之后的局面优劣。

4.2 Alpha-Beta剪枝的递归结构

Alpha-Beta剪枝是对Minimax搜索的优化，原理是：维护两个界限，alpha表示“我方已找到的最佳选择的下界”，beta表示“对方已找到的最佳选择的上界”。在搜索过程中，一旦发现某个分支已经不可能改变最终的alpha或beta，就停止搜索剩余子节点。

def alphabeta(node, depth, alpha, beta, maximizing): if depth == 0 or node.is_terminal(): return node.evaluate() if maximizing: value = float('-inf') for child in node.get_ordered_children(): value = max(value, alphabeta(child, depth - 1, alpha, beta, False)) alpha = max(alpha, value) if beta <= alpha: break return value else: value = float('inf') for child in node.get_ordered_children(): value = min(value, alphabeta(child, depth - 1, alpha, beta, True)) beta = min(beta, value) if beta <= alpha: break return value

核心就一句话：if beta <= alpha: break。当对方所说的上界已经不超过我方所说的下界时，这个节点后面的分支再怎么搜也没有意义。对极大层来说，一旦某个子节点的值让alpha超过了beta，说明这个节点的最终值不可能对整体决策产生影响了；对极小层同理。

需要注意，Alpha-Beta剪枝必须在Minimax的递归框架内使用。它不是独立于Minimax的另一种算法，而是Minimax的剪枝加速版。在不改变结果的前提下，它能极大减少搜索量。理想情况下，Alpha-Beta可以把搜索树从O(b^d)降到O(b^(d/2))，这个差别是巨大的——同样是每层35个分支、深度8层的国际象棋搜索，暴力搜是35的8次方，而Alpha-Beta大约只需35的4次方量级。

4.3 走法排序对剪枝效果的显著影响

Alpha-Beta剪枝的效果高度依赖节点的搜索顺序。如果最大值层最先遇到足够大的值，最小编层最先遇到足够小的值，剪枝窗口会快速收窄，剪掉的子树数量会大幅增加。反过来，如果顺序很差，alpha和beta迟迟无法收紧，几乎砍不掉什么分支。

所以工业级的博弈引擎几乎都会做走法排序：先用上一迭代的置换表记录（类似重复状态剪枝）优先搜索，再对剩余走法做静态启发式评估——比如吃子棋局中优先走价值高的吃子，棋类中优先走中心控制较强的位置。我见过一些对战程序，只是改了走法排序，相同的搜索深度下棋力就能明显上升，因为同样的时间预算内它能“看得更远”。

还要提醒一个实战中容易忽略的细节：Alpha-Beta剪枝要求博弈树的评估是“全局一致”的。也就是说，同一个局面不论在搜索树的哪个位置出现，它的评估值应该一样。如果评估函数带了影响搜索方向的随机性，或者开局库、残局表这些外部知识没有被正确处理，剪枝结果就不可靠，甚至可能剪掉最优解。

5. 常见问题与排查技巧实录

5.1 剪枝把正确答案也剪掉了怎么办

剪枝过头是最容易踩的坑。我自己最早写0-1背包时，上界函数里忘了对“选”分支做容量检查，结果某个分支的bound过小，把明明能刷新best的路径给截断了。还有一个典型错误是可行性剪枝的约束条件写错，比如N皇后判断对角线冲突时下标搞混，导致某些合法摆法被直接跳过。

排查思路其实很简单：先用一个明确的小测试用例跑一遍，确认答案正确；再手动模拟搜索树，人工确认每一个剪枝条件是否成立。如果没有现成的小用例，就自己构造，保证答案一眼能算出来。正确性永远是第一位的，剪枝效率只是优化，不能以牺牲正确性为代价。

5.2 为什么剪了还是很慢

如果剪枝条件写对了但还是慢，通常有两个原因。第一，缺少搜索顺序优化。不管什么剪枝，都是在已有信息基础上做判断——你越早拿到一个较好的可行解，剪枝条件越容易快速生效。第二，剪枝条件本身的强度不够。比如上界函数给了个非常放松的估算上限，那么几乎所有分支都无法被剪掉，等于没剪。

我一般会做一件事：在回溯递归入口加一个计数器，统计进入递归的次数，然后把有剪枝和无剪枝版本的计数对比。如果剪枝版本递归次数只少了一点点，说明你的剪枝条件太弱；如果少了几个数量级，说明剪枝是有效的。这个数字是最直观的健康指标，比猜优化效果靠谱得多。

5.3 避坑速查表

提示：剪枝是“用对问题的理解换性能”，不是无脑砍分支。写剪枝前，先把问题的约束和最优化目标用一句话写清楚，再动手。

结尾

根据我实际做搜索类题目的经验，回溯剪枝想写好，核心就三件事：先保证可行性剪枝把非法分支挡掉，再设计一个足够紧的最优性剪枝条件，最后用搜索顺序优化让剪枝条件尽早生效。这三个环节缺一个，性能都会差很远。我踩过最深的坑是只盯着剪枝函数本身，忽略了搜索顺序——后来发现调整顺序的收益常常比优化剪枝函数还大。

最后再分享一个小技巧：做任何回溯题，先把递归函数的参数想成“状态的完整描述”，再想“什么情况下这个状态不可能得到更好解”，剪枝条件自然就写出来了。多练几个经典题之后你会发现，所有剪枝代码背后都是一套统一的思维模式，看透了就能举一反三。