说起深度优先搜索剪枝我一开始是有点抗拒的。光看这个名字深度优先搜索已经够抽象了再加一个剪枝感觉像是园丁拿着剪刀修剪盆栽跟写代码有什么关系直到有一次我自己写的一个搜索程序在大概二十几个数据量面前就像睡着了一样怎么等都等不出结果我才真正意识到不把剪枝这回事搞明白你写的DFS再多也只是纸上谈兵。这篇内容我会完全用自己的话把深度优先搜索、递归树和剪枝三者串起来讲清楚适合刚学搜索算法不久、被超时卡过、或者想知道剪枝到底剪的是什么的人。我尽量不用竞赛里那套冷冰冰的公式而是用点菜、走迷宫、数独这些生活里的场景来讲同时给出可以直接照着写的代码。目标只有一个让你看完之后再遇到DFS超时能自己找到该剪的那一刀。1. 被一道超时题逼着学剪枝我的初学动机1.1 什么是搜索超时它到底卡在哪先还原一下我当时的场景。在一个练习平台上遇到一道题需求很简单给一批正整数问能不能从中选出若干个数使它们的和恰好等于一个目标值。我心想这还不简单直接深度优先搜索每个数字都有选和不选两种状态挨个试一遍不就行了。于是我写了下面这段非常典型的朴素DFSdef subset_sum(nums, target): def dfs(idx, cur_sum): if cur_sum target: return True if idx len(nums): return False # 选当前数 if dfs(idx 1, cur_sum nums[idx]): return True # 不选当前数 if dfs(idx 1, cur_sum): return True return False return dfs(0, 0)逻辑确实是对的。但问题来了当数据量到20的时候勉强能跑到30的时候程序几乎就卡死了。我一开始以为是代码写得慢后来才反应过来根本不是代码慢而是我让程序把太多根本不需要走的路径也走了一遍。这就是所谓搜索超时的本质不是你的递归函数本身的常数大而是你要遍历的路径数量多到了指数级计算机再快也扛不住。1.2 为什么说DFS是非线性枚举组合爆炸才是原罪用一个例子帮助你感受什么叫组合爆炸。假设你去一家餐厅菜单上有30道菜每一道菜你都可以选择点或者不点。那么你可能的点餐组合有多少种答案是2的30次方也就是大约10.7亿种。如果让一个人站在那里把每种组合都念叨一遍一秒钟念叨一种不吃不喝也得三十多年才能念完。DFS做的事情本质上就是把这个10.7亿种组合全部枚举出来然后挨个判断哪一种恰好等于目标值。除非你运气特别好很早就在某个分支上找到了答案否则它就要老老实实地把所有可能性都走完。这就是为什么我说DFS是一个非线性枚举的过程它的分支数量不是线性增长的而是随着数据规模翻倍而翻倍。每增加一个数字整个搜索空间的规模就翻一倍。这种增长速度就是数学里常说的指数爆炸。明白了这一点之后我的想法就变了与其提升电脑的性能不如降低需要枚举的分支数量。那些明显不可能产生答案的分支直接不进去就好了。这个直接不进去的动作就是剪枝。2. 先把DFS的递归树画明白再谈剪枝2.1 递归、栈和搜索树其实是同一件事的三种看法很多人学DFS的时候背了一堆概念递归函数、调用栈、回溯、搜索树……听起来像是四件事其实它们描述的是同一个过程。你可以把DFS想象成在迷宫里面走路的规则选定一个方向就一直往深处走走到走不动了再退回到最近的分岔口换一个方向继续走。这个一直往深处走就是深度优先四个字的由来。而退回到最近的分岔口这个动作在程序里就是递归函数返回时发生的回溯。所谓搜索树是用树的形式把这个走迷宫的过程画出来。树的根节点就是初始状态比如一个数字都还没选树的每一个分叉就是一个决策比如选下一个数字和不选下一个数字树的每一个叶子节点就是一个完整路径的终点可能是一个答案也可能是一个死胡同。我自己学习的时候比较笨也比较有效的办法是在草稿纸上把数据量缩小到3个、4个然后把整棵递归树完整画一遍。画完之后你会发现所谓的剪枝就是在这棵树上拿一把剪刀把某些子树整个剪掉不让程序进入那些子树里去白白浪费时间。2.2 节点数量级估算剪枝前先知道自己有多慢剪枝之前我建议你先学会一件事大概估算一棵递归树有多少个节点。最简单的情况是每个状态有b种选择深度是d那么整棵树最坏情况下的节点数大约是b^0 b^1 b^2 ... b^d (b^(d1) - 1) / (b - 1)如果b等于2深度是30那结果就是2的31次方减1大概是21亿。你写一个循环让电脑每秒跑一亿次也需要二十多秒才能把节点访问完。这还只是节点数如果每个节点里还做了更多计算那时间就更夸张了。所以剪枝的核心目标就是用各种判断条件让这个b变小或者让有效搜索深度d变小。只要这两个数任何一个降下来整体规模都会成量级地下降。这里顺便说一个我的个人经验不要上来就写代码先在纸上估算一下最大可能的搜索树规模。如果估算出来是十亿量级而你的算法内置剪枝条件又写得太弱那基本可以断定会超时。提前估算能帮你省下大量无意义的调试时间。3. 剪枝到底在剪什么三种最常用的剪枝逻辑3.1 可行性剪枝这个分支根本走不到终点第一种剪枝也是最容易理解的一种叫可行性剪枝。它的核心思想是当前这个状态已经明确违反了题目条件或者从当前状态继续走下去无论如何都不可能得到合法答案那就没必要再继续递归了。拿我刚才那个从数字里凑目标值的例子来说如果给出的数字全是正整数目标值是100而我现在已经选了几个数当前和已经超过了100那后面的数字不管怎么选都只会更大永远不可能再回到100。这时候直接return就行了后面的分支全都不看。这就是可行性剪枝。它要求你认真看题目里的约束条件找到一旦满足某个条件后续路径就全军覆没的判断标准。只要找到这个条件剪枝的杀伤力往往非常可观。再举一个更直观的例子走迷宫的时候如果你发现自己已经走到了墙外面那肯定就直接回头了不会继续往前走。这个判断是否越界的动作本质也是一种可行性剪枝只是因为它太自然了很多时候你没意识到而已。3.2 最优性剪枝就算走到底也换不来更好的结果第二种剪枝叫最优性剪枝它的使用场景是题目要的不是有没有解而是最优解是什么比如最短路径、最少步数、最大价值。这时你可以维护一个全局变量记录当前已经找到的最好答案记为best。在搜索过程中每到一个新状态你先估算一下如果从这个状态继续走下去最好的情况下能得到多少。如果这个最好的情况放到全局来看都已经比best差或者持平了那这个分支就没有继续搜索的价值剪掉。这样说比较抽象我给你一个生活化的类比。你在商场里找最短的出口已经从一条路走到了出口步数是50。之后你看到另一条岔路刚走进去两步就发现就算后面一路畅通也至少还要再走50步才能到出口加起来肯定已经超过50了。这时候你还有必要继续走完这条岔路吗没必要直接回头。这种剪枝的关键在于乐观估计四个字你估计出来的那个最好情况必须真的是所有后续可能情况里的上界或下界。如果你估计得太乐观比如明明后面还有大堵墙你却假设一路畅通那就有可能在错误的方向上多走很多步如果你估计得太悲观则可能把真正的最优解也剪掉导致答案错误。3.3 重复状态剪枝把算过的东西当回事第三种剪枝叫重复状态剪枝在不少资料里也叫记忆化剪枝。它解决的是另一类问题明明同一个状态前面已经算过结果了后面又跑到同一个状态再一模一样地算一遍。最典型的场景是带有方向选择的网格搜索。比如在一个二维网格里你从起点出发可以上下左右走。如果你不记录哪些格子已经走过程序可能会在A和B两个格子之间反复横跳永远停不下来。这时候用一个visited数组记录已经访问过的格子就是最基础的重复状态剪枝。再复杂一点如果DFS的状态由多个参数决定比如当前在第几个物品、当前累计重量是多少那你可以用记忆化数组或哈希表把从这个参数组合出发能不能找到答案记录下来。下次再搜索到相同参数组合时直接返回之前记录的结果而不是重新搜索。不过要提醒一句记忆化不是所有DFS都能用的。只有当某个状态后续的结果只取决于当前状态参数而不取决于之前是怎么走到这个状态的时候记忆化才安全。如果题目要求输出具体路径或者状态携带了很多额外限制那就要谨慎一点。4. 三个经典例子的手把手剪枝实操4.1 N皇后问题冲突检查就是最自然的可行性剪枝N皇后问题大概是初学者接触DFS时最常见的题目了。它的规则是在一个N乘N的棋盘上放N个皇后任意两个皇后不能在同一行、同一列、同一条对角线上。其实你如果一行一行地放就已经天然保证了不同行这个条件。所以真正需要判断的只剩下列冲突和对角线冲突。我见过很多初学者第一次写这题时用的是二维数组模拟棋盘每放一个皇后就去遍历所有已放的皇后检查是否冲突。这样写也不是不行但每次判断的代价太高。更常见的做法是准备三个集合一个记录哪些列已经被占用一个记录主对角线一个记录副对角线用空间换时间。def solve_n_queens(n): cols set() diag1 set() # row - col 相同的在同一主对角线 diag2 set() # row col 相同的在同一副对角线 ans [] def dfs(row, board): if row n: ans.append(board[:]) return for col in range(n): # 可行性剪枝这一列或两条对角线上已经有人 if col in cols or (row - col) in diag1 or (row col) in diag2: continue cols.add(col) diag1.add(row - col) diag2.add(row col) board.append(col) dfs(row 1, board) board.pop() cols.remove(col) diag1.remove(row - col) diag2.remove(row col) dfs(0, []) return ans在这个代码里continue那一段就是剪枝。你可以想想如果没有这个判断程序会怎么做它会傻乎乎地把皇后放在已经被占用的列上然后继续往下一行放直到放完N行之后才在终点发现冲突。这样一个无效分支可能就会衍生出一大堆无效搜索。而加了冲突剪枝之后错误状态在诞生的那一刻就被掐掉了。4.2 子集和问题排序加后缀和几行代码省掉亿次调用回到我开头说的那个凑数字问题。如果数字全是正整数取一个目标值target问能不能找到某个子集让它们的和恰好等于target。第一版无脑DFS已经写过了。现在我们给它加两道剪枝第一当前和已经大于target直接返回第二先把数组排序预处理后缀和如果当前和加上后面所有剩余数字仍然小于target那无论如何也不可能凑出来了直接返回。代码可以这样写def subset_sum(nums, target): nums.sort(reverseTrue) suffix [0] * (len(nums) 1) for i in range(len(nums) - 1, -1, -1): suffix[i] suffix[i 1] nums[i] def dfs(idx, cur): if cur target: return True if idx len(nums) or cur target: return False # 可行性剪枝后面所有数都选上也凑不够 if cur suffix[idx] target: return False # 优先尝试较大的数更容易触发剪枝条件 if dfs(idx 1, cur nums[idx]): return True if dfs(idx 1, cur): return True return False return dfs(0, 0)这里有两个细节值得你品一下。第一个细节是为什么排序后要reverseTrue也就是从大到小搜索。因为剪枝条件cur target只有在当前和已经超出target时才会触发。你先选大数就会更快地让cur增长到超出target从而更早剪掉那些不靠谱的分支。第二个细节是后缀和的剪枝为什么成立。数组已经排序suffix[idx]表示从当前下标到数组末尾所有数字的和。如果当前和加上这批所有数字都还小于target那么后面无论怎么选都不可能再增大到target了。这个剪枝非常强尤其当target比较小、而后面剩余数字又很有限的时候几乎是直接砍掉一整片子树。4.3 迷宫最短路径把已知最优解变成前进路上的标尺最后一个例子是迷宫最短路径。虽然很多情况下求最短路径用BFS更合适但DFS配合最优性剪枝同样能跑而且非常适合用来理解最优性剪枝的工作方式。假设我们有一个二维数组0表示可以走1表示墙起点和终点已知每一步只能上下左右移动一格求最少步数。基础版本是这样的用一个深度优先搜索遍历所有路径维护一个best变量记录当前找到的最短步数。每次到达终点就更新best。如果当前步数已经大于等于best说明继续走下去不可能更优直接剪掉。def shortest_path(maze, start, end): rows, cols len(maze), len(maze[0]) visited [[False] * cols for _ in range(rows)] best [float(inf)] def dfs(x, y, steps): if (x, y) end: best[0] min(best[0], steps) return if steps best[0]: return for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)): nx, ny x dx, y dy if 0 nx rows and 0 ny cols: if maze[nx][ny] 0 and not visited[nx][ny]: visited[nx][ny] True dfs(nx, ny, steps 1) visited[nx][ny] False visited[start[0]][start[1]] True dfs(start[0], start[1], 0) return -1 if best[0] float(inf) else best[0]这段代码里的if steps best[0]就是典型的最优性剪枝。注意要先判断是否到达终点再用当前最优值剪枝否则会出现到达终点时因为步数恰好等于best而被漏掉的情况。如果你还想再加一道更激进的剪枝可以用曼哈顿距离作为乐观估计从当前格子(nx, ny)到终点end就算中间没有任何墙也至少需要走abs(nx - end[0]) abs(ny - end[1])步。所以如果steps 1 曼哈顿距离 best[0]这条分支即使继续走也不可能产出更短路径可以直接不进入。这个乐观估计就是后面A星算法里启发函数的朴素版本。在DFS里使用它本质上是用空间和时间上的估算去换搜索效率。5. 剪枝效果的直观对比剪前和剪后到底差多少5.1 用递归计数器看剪枝的真实杀伤力很多人看完上面的例子知道要剪枝但不知道剪枝到底能把程序提速多少。我建议你在自己的代码里加一个全局计数器每次进入递归函数就加一然后分别跑剪枝前和剪枝后的版本你会有非常直观的感受。比如随机生成25个不超过200的正整数设定一个target跑子集和问题。我在本地做过的实验大概是这样的一组示意数据版本递归调用次数运行效果无剪枝超过百万甚至千万明显卡顿难以接受只加cur大于target剪枝几十万快了一些但还是慢排序加后缀和剪枝几千瞬间出结果这个数量级的差异非常震撼从百万到几千不是快了一倍两倍而是快了上百倍。之所以有这么大的差距是因为剪枝砍掉的不是某一个节点而是一整个子树。每剪掉一个子树就相当于把树上一个节点的所有后代全部免除了搜索。我当时看到这个数字之后对剪枝的态度彻底改变它不是可有可无的优化而是指数级搜索能不能落地运行的关键。5.2 剪枝的先后顺序和预处理同样重要剪枝条件怎么写、先判断谁、后判断谁也会直接影响搜索速度只是这个影响没有前面那个量级差距那么明显但关键时刻能救命。我常用的经验是把代价最低、最容易触发、判断就能砍掉最多分支的条件放在前面。什么意思呢拿上面子集和问题来说cur target这种判断只需要一次比较代价极低而且只要触发就说明当前分支已经没希望所以它应该放最前面。cur suffix[idx] target需要读一次后缀和数组代价稍微高一点但杀伤力也更强放在第二位。还有一类预处理值得专门说排序。很多DFS问题的剪枝效果严重依赖于搜索顺序。搜索前先花很少的代价排序往往能让后续的剪枝条件更早、更频繁地触发。这不是什么高端技巧就是一个朴素的道理你希望程序先去探索那些最有希望、最容易走死的分支让它尽快积累失败经验从而用最短的时间把其他相似分支剪掉。6. 我的经验总结怎么找到该剪的那一刀6.1 新手最容易踩的三个假剪枝坑第一个坑剪枝条件写得太激进把正确答案也剪掉了。最优化问题里如果你用来判断的乐观估计不是真正的上界或下界那就可能把藏着最优解的分支提前砍掉。比如在找最小步数时你估计从当前至少还需要X步但这个X不是你真正能走的最小步数而是一个过于乐观的小数字那程序就会误以为某条路已经足够短而放弃它。反过来如果你把X估得过大又会放过大量可以剪掉的分支。解决办法只有一个每次加一个剪枝条件后先用小规模数据验证答案是否和原来一样。如果答案变了不要怀疑是数据问题几乎都是剪枝条件不严谨。第二个坑修改了全局状态却没有在递归返回时恢复导致剪枝把路径也剪坏了。N皇后代码里的cols.add和cols.remove必须成对出现迷宫里的visited[nx][ny] True和visited[nx][ny] False也必须成对出现。一旦你某个分支提前return时忘了恢复状态后续所有搜索都会在一个被污染的环境里进行表现出来的就是明明剪枝条件没问题结果却神奇地出错。第三个坑为了炫技堆叠一大堆剪枝代码变得完全不可读。剪枝的本质是用正确性换效率但效率的前提是代码正确。如果你自己都看不懂那些剪枝条件那后面维护和调试会非常痛苦。我现在的习惯是先写出最朴素、最容易验证正确的DFS然后一个一个加剪枝每加一个就测试一次。剪枝不是越多越好而是在可读性和效率之间取平衡。6.2 从画递归树到加计数器一套我常用的排查顺序最后分享一套我自己在实战中反复使用的排查方法你可以把它当成一个检查单。第一步画递归树。如果你不清楚怎么画就把数据规模缩小到最小比如3个数字、3乘3的棋盘。把整棵树画出来看看它到底有多宽、多深。剪枝就是在这棵树上找哪些节点可以被剪掉。第二步看约束条件找可行性剪枝。想一想什么样的状态一出现就注定是死路把这些条件写出来加到DFS入口处。第三步看题目问的是什么。如果问的是最优解就维护一个当前最优值然后判断当前状态是否有可能优于它。如果不可能果断return。第四步加一个计数器证实剪枝确实在起作用。如果加了剪枝后递归调用次数和没加一样那说明你这个剪枝条件几乎永远不触发要么写得不对要么判断顺序不对。第五步从弱剪枝到强剪枝逐步加强。每一步都保证算法仍然正确再考虑下一步。这套顺序我用了很久它最适合那种一眼看上去DFS能做、但一跑就超时的题目。大多数情况下到第二步、第三步就能解决百分之八十的问题。说了这么多其实剪枝并不神秘。它就是你在走一条很深的岔路之前先站在路口掂量清楚这条路值得走下去吗如果答案是不值得那就果断回头把时间留给真正有希望的方向。我自己学到这里的时候有个挺明显的感受以前总觉得DFS是暴力硬搜学会剪枝之后才发现它更像是在暴力基础上加了一点点思考的艺术。
