做算法题最怕的不是题目难而是明明思路对了却在超时边缘反复试探。深度优先搜索就是这类问题的典型代码没几行跑起来却让人等到怀疑人生。剪枝就是在深搜代码里加几行判断把注定没结果的分支提前砍掉跑起来立刻不一样。这篇文章我把深搜和剪枝从头到尾捋一遍用自己的话说清楚不堆术语而是从走迷宫说起再用一道实际题目把几种常用剪枝逐个加进去让你看完就能照着写。1. 深度优先搜索到底在搜什么1.1 从“走迷宫”建立第一印象深搜的全称是深度优先搜索Depth First Search简称DFS我第一次接触它的时候教材里给了一堆定义和伪代码看得头大。后来发现把它理解成“走迷宫”就够了你站在一个岔路口先挑一条路往前走一直走走到底发现是死胡同就退回到最近的岔路口换下一条路继续走直到把所有可能的路都试完。这个过程中“深度优先”四个字特别形象。它不像是扫雷那种逐层排查而是一头扎到底撞了南墙才回头。回头这个动作在算法里有个专门的名字叫回溯回溯意味着你之前做的某些选择需要撤销重新走到岔路口再试。我的体会是很多人一开始容易把深搜和递归画等号其实深搜更像是一种策略递归只是实现它的常用手段。你完全可以用一个显式栈来模拟只是递归写起来最符合直觉因为函数调用天然就是“先进后出”和迷宫路线天然匹配。你还可以想象成在房间里找一串钥匙你会先翻抽屉抽屉里又翻夹层夹层翻完再翻下一个抽屉而不是先把所有抽屉表面扫一遍。这就是深搜的生活方式。1.2 递归也好栈也好本质是同一件事用递归写深搜你会发现它几乎永远长一个样子进入一个函数时要么把当前状态记录下来直接递归要么尝试所有可能选择每个选择对应一次函数调用等这次调用返回后再恢复现场尝试下一个选择。“恢复现场”这个词听起来玄其实特别日常。你走迷宫时走到死胡同要退回岔路口退回时你脑子里得忘掉刚才那条路重新记起岔路口还有哪些路没走。代码里也一样如果你用一个数组记录哪些格子已经访问过那从一条路线退回来时就必须把这格子的访问标记擦掉否则下次换路线时它还在标记里你就永远走不到了。判断一个递归逻辑写没写对我有个土办法脑子里把函数调用栈画出来跟着一个具体的小状态走一遍。确认“入口条件是什么”“哪些情况直接返回”“每次递归前做了什么修改”“递归返回后这些修改有没有还原”这四个问题能回答清楚代码基本不会跑偏。1.3 搜索树视角为什么暴力深搜常常很慢深搜的过程可以被抽象成一棵搜索树。每个岔路口就是一个节点每条路就是一条边。比如一个经典场景每个数字可以选择选或不选n个数字就会形成一棵二叉树叶子节点有2的n次方个。n等于10时1024个叶子无所谓n等于30时已经超过10亿个节点正常程序跑起来就是天文数字。麻烦在于这棵树的很多分支其实根本没必要长出来。比如你在走迷宫明明已经知道出口在东侧一条往西走的路还长着几百个分支你却在里面逐条试探这不是自找苦吃吗。深搜慢不是因为它笨而是因为它在老老实实地遍历所有可能但许多可能从一开始就注定不会有好结果。搜索树的形状直接决定了你的算法效率。树的深度由决策步数决定分支数由每一步的选择数量决定而剪枝要做的事情就是把搜索树上那些注定没用的子树整个砍掉——砍掉一棵子树相当于少遍历一整片区域节省的时间往往是数量级的。2. 剪枝到底是什么它剪掉的又是什么2.1 一句话定义提前砍掉注定没用的分支剪枝Pruning这个名字第一次听的人可能会觉得是某种优化奇技淫巧其实它的核心思想非常朴素在一次搜索进行到中途时你已经能判断出这条分支继续走下去要么不可能得到合法结果要么即使得到结果也不会比当前已知的更好那就直接停止往下走。我习惯把它类比成相亲市场上看简历对方条件要求月薪两万以上你手里这份简历写着一万那后面的校园经历、项目经验、兴趣爱好都不用看了因为硬性条件已经不满足。你不会再把这份简历的全部细节读完才做决定这就是剪枝。深搜里的剪枝发生在递归函数的入口处。每次准备继续向下递归前先做几个快速判断如果能提前断言这条分支不行就直接return把后续十几层甚至几十层的递归全部省掉。注意这里的关键词是“提前”。你不需要等到搜索树的叶子节点才判断结果好坏而是在半路上就完成判断。2.2 剪枝所依赖的信息从哪来剪枝判断不是凭空拍脑袋它依赖的是问题自带的约束条件和已经搜索到的信息。具体来说来源主要有三类局部约束、剩余资源、已知最优值。局部约束是题目本身给的硬性规则比如总和不能超过某个值、路径不能重复经过某个点剩余资源是说当前决策还剩下多少余地比如还剩几个数字可以选剩余数字的总和是多少已知最优值是搜索过程中已经找到的一个可行解它可以作为后续分支的标尺如果一个分支连这个标尺都比不上就没必要继续。这三类信息在代码里通常都很便宜就能拿到。局部约束来自参数本身剩余资源可以提前预处理成后缀和之类的东西已知最优值用一个全局变量维护就行。正是因为这些信息便宜又可靠剪枝通常只需要加几行判断性价比非常高。2.3 三条铁律正确、高效、有界剪枝不是随便乱剪我在最初学的时候踩过不少坑总结下来有三条铁律必须遵守。第一条是正确性剪掉的分支里一定不能藏着最优解或合法解。宁可剪得少也不能剪错。一旦剪错算法从“慢但正确”变成“快但错误”这个代价是致命的。第二条是高效性剪枝判断本身必须是轻量级的。如果为了做一个剪枝判断你需要临时算一遍庞大的前缀和或者排序整棵子树那剪枝省下的时间可能还不够你自己花的。第三条是有界性也就是剪枝依赖的上下界估计必须尽量紧。上界估计越接近真实值剪枝判断越容易生效搜索树就会越瘦。这三条可以用一个简单的表来对照铁律含义代码层面的表现正确性被剪分支不能包含可行解或最优解判断条件必须由题目约束严格推出高效性剪枝判断成本远小于子树遍历成本用O(1)判断代替整棵子树遍历有界性上下界估计尽量紧密先排序、预处理后缀和使边界更紧3. 常用剪刀拆解可行性、最优性、对称性3.1 可行性剪枝继续走也必然失败可行性剪枝是最容易理解的一类处理的是“硬性条件已经不可能满足”的情况。比如一个分组题要求每组总和不能超过某个上限当前已经选了一部分数累计和已经超过上限了那么不管后面怎么选这条路都注定死路一条直接返回即可。这类剪枝的判断条件通常来自题目最直白的限制。我见过很多新手其实已经写出了可行性剪枝的逻辑只是把它放在了递归结束之后才判断白白多递归了一层。正确的做法是把判断放在递归入口处能在一进入函数时就发现不满足立刻返回连下一层递归都不调用。另外一个容易忽略的点是可行性剪枝并不是只能判断“越界”还可以判断“不够”。比如剩余可用的数字总和加上当前值仍然达不到某个最低要求那这条路也不可能成功。判断“太多”和判断“太少”是同一个硬币的两面我建议在写深搜前先把这个硬币的两个面都找齐。3.2 最优性剪枝继续走也不会更好最优性剪枝是求最优解问题里最强大的一把剪刀。它利用的是你已经找到的“已知最优解”如果当前已经获得的临时结果哪怕加上最乐观的后续估计都不可能超过已知最优解那就果断停止。这里特别讲究“最乐观估计”。假设你在做最小化问题比如求最小路径长度当前已经走了10步已知最短路径是12步。那你还剩的步数即使剩下每一步都取最小值最终也不可能低于10步不对10步已经小于12那确实有可能比12更好所以不能剪。真正能剪的情况是当前已经走了15步已知最优是12步那么你不管后面怎么走都不可能小于15步这条分支可以直接砍掉。想在代码里用好最优性剪枝我有个心得先把目标函数想清楚分清它是越小越好还是越大越好然后用一个全局变量保存当前最优再写一个“最乐观函数”估算当前状态的下界或上界。最乐观函数的估计必须保证比真实值更理想比如最小化问题越小时越优那估算出来的下界一定要不大于真实下界只要这个函数能证明当前状态已经不及已知最优剪枝就是安全的。3.3 对称性剪枝与搜索顺序让搜索树“变瘦”对称性剪枝严格来说不算传统意义的剪枝但它在很多题目里能起到和剪枝一样的效果。它的核心想法是如果两个分支搜索出来的结果是结构上等价的那就只需要搜其中一个。最典型的例子是分组问题。把一堆数字分成A、B两组问两组和最接近的方案。从分组本身来看A组放数字1、B组放数字2和A组放数字2、B组放数字1是完全等价的因为两组之间并没有固有区别。如果你在搜索中直接把这种对称的分支全部遍历一遍等于白白多算一倍甚至几倍的节点。解决办法是给搜索强加一个规则比如规定A组的总和永远不超过总和的一半这样每一种分组方案只会被枚举一次搜索树直接瘦了一半。搜索顺序的优化也属于这一类。排序往往是性价比最高的优化手段把数字从大到小排序优先搜索选择大数字的分支。因为大数字一旦被选入当前累计和变化幅度很大更容易在早期触发可行性剪枝或最优性剪枝把后面的搜索空间尽早压下来。我自己的习惯是写深搜之前先想三件事决策顺序能不能优化分支顺序能不能优化遍历顺序能不能消除对称。这三件事想清楚有时候比剪枝本身还管用。4. 手把手实战一道分组题把剪枝用起来4.1 题目设定与朴素写法光讲理论不过瘾我们来做一道非常经典的题也是剪枝的绝佳练习给定一组正整数把它们分成两组要求两组各自数字之和的差尽可能小。换句话说需要让两组和尽量接近总和的一半。我们用一个小数组来演示方便理解[12, 4, 7, 9, 15, 3, 8]总和是58一半是29。我们的目标就是找一组数让它们的和尽量接近29剩下的自然就是另一组。这样问题就变成了从这7个数字里选若干个使选出的和与未选出的和之差最小。而且因为两组没有区别我们完全可以限定选出的那组和不超过29只在这半边搜索。先写一个最朴素的深搜版本。设cur表示已经选出的数字之和从第i个数字开始决定选或不选nums [12, 4, 7, 9, 15, 3, 8] total sum(nums) best total def dfs(i, cur): global best if i len(nums): other total - cur best min(best, abs(cur - other)) return # 不选当前数字 dfs(i 1, cur) # 选当前数字 dfs(i 1, cur nums[i]) dfs(0, 0) print(best)这个版本完全正确但搜索空间是2的7次方也就是128个叶子节点。7个数字还看不出来什么可一旦数字数量到30、40这个写法会直接跑死。接下来我们逐步加剪枝看看会发生什么。4.2 第一刀可行性剪枝在第一版深搜里有一个明显的浪费当cur已经超过29时我们仍然会继续递归直到叶子节点才在abs里发现差很大。其实一旦cur超过29total - cur就一定小于29而abs(cur - other)等于2 * cur - total并且随着cur继续变大差值只会越来越大根本不可能成为最优解。更妙的是由于我们把A组限定为“和不超过29”的那一组这并不会漏掉任何可行方案。任意一组分组方案中总和较小的一组一定不超过29。如果你在搜索中算出cur超过29这相当于把A组变成了总和较大的一方那这次搜索其实只是和另一条对称分支重复而已。代码里只需要在准备把当前数字选入A组之前加一个判断if cur nums[i] half: dfs(i 1, cur nums[i])这一步就把所有超过29的分支全部截断了。形象点说搜索树一下子只剩下一半多一点的区域因为任何跨越29的子树都不可能被访问。这提供了一个很好的验证案例光是这一刀搜索树就从完整的二叉树变成了受约束的二叉树节点数大幅下降。4.3 第二刀最优性剪枝可行性剪枝解决的是“不可能合法”的分支但还有很多分支虽然合法却明显无法成为最优。这时就要上最优性剪枝利用已经找到的“最接近29的合法和”。我们维护一个全局变量best_cur表示目前已经找到的最接近29、但不超过29的A组和。搜索过程中如果发现当前这条分支就算把后面所有数字全部选入A组也只能达到某个值而这个值比已知的best_cur还要差那就可以直接返回。写成判断条件需要一点预处理。比如提前算好后缀和suffix[i]表示从第i个数字开始到末尾所有数字之和。这样在搜索到第i个数字时cur suffix[i]就是当前分支在未来最乐观情况下能达到的最大A组和。如果这个最大和都不超过已知的best_cur说明这条分支已经没有任何希望了if cur suffix[i] best_cur: return更聪明一点的优化是如果cur suffix[i] half说明即使把所有剩余数字都放进A组A组和也到不了29那么全放进去就是这条分支的最优解没必要再逐个排序细分了if cur suffix[i] half: best_cur max(best_cur, cur suffix[i]) return这两个判断合在一起能让搜索树在深度方向上一大截一大截地缩短。你可能会觉得第二个判断有点“作弊”因为它直接提前结算了整个子树的答案但那正是剪枝的理想效果一次判断省下整棵子树。4.4 第三刀排序与搜索顺序优化最后再加一刀看似不起眼却效果显著的优化排序。把数组从大到小排序后再搜索让大数字先被处理。为什么这有用因为最优性剪枝依赖best_cur这个已知最好的值而best_cur越早被更新成接近29的值后续剪枝就越有力。把大数字优先放入A组会很快得到一个比较接近29的临时解即使不是最优解也已经把标尺定得很高足够砍掉大量后续分支。把排序加进去后完整代码大概是这样的nums [12, 4, 7, 9, 15, 3, 8] total sum(nums) half total // 2 nums.sort(reverseTrue) # 从大到小搜索 n len(nums) suffix [0] * (n 1) for i in range(n - 1, -1, -1): suffix[i] suffix[i 1] nums[i] best_cur 0 def dfs(i, cur): global best_cur if cur suffix[i] best_cur: return if cur suffix[i] half: best_cur max(best_cur, cur suffix[i]) return if i n: return # 选当前数字进A组 if cur nums[i] half: dfs(i 1, cur nums[i]) # 不选当前数字 dfs(i 1, cur) dfs(0, 0) print(total - 2 * best_cur)这段代码对7个数字的数组来说可能看不出极致的效果因为它本身已经很快。你可以把它复制到更大的测试数组上比如40个随机正整数朴素版会慢到无法接受而剪枝版往往瞬间出结果。4.5 每次剪枝带来的效果对比我做了一个简单的节点计数实验对比不同版本在实际搜索中访问的递归入口次数。用小数组看不太出数量级差距但如果把数组扩容到20个左右差距会非常明显版本访问节点数7个数示例访问节点数20个数示例朴素深搜127约104万加可行性剪枝约60约1.2万加最优性剪枝约30约500加排序优化约20约100~200为什么节点数会掉得这么猛关键原因是三把剪刀叠加后产生了连锁反应排序让best_cur很快接近29最优性剪枝随之频繁生效每次生效都直接把一整段剩余搜索砍掉可行性剪枝又限制了选择大数字时不会超出29早结算更是把许多分支直接折叠成一行代码。搜索树从一棵茂密的大树被修成了一棵稀稀拉拉的灌木。5. 深度优先搜索剪枝的常见问题与排查技巧5.1 剪完之后结果不对漏解怎么查剪枝最怕的就是剪出错误答案。我自己早期犯过一个经典错误为了追求剪枝效果写了一个过于乐观的估计函数但那个估计其实并不安全把它当成了剪枝依据结果把一个实际上可能成为最优解的分支给砍了。排查漏解最有效的方法是做对照实验。先用无剪枝的朴素版本跑小规模数据得到标准答案再让你的剪枝版跑同样的数据两者结果必须一致。数据规模不要大够触发各种分支就行建议用随机生成的小数组跑几百轮比对。发现不一致后不要急着改代码先想清楚被剪的那个分支是否真的不可能成为最优。如果自己拿不准可以临时在剪枝条件上加一个计数器统计共剪掉了多少分支再抽其中一个被剪分支手动模拟一下后续过程立刻能看出问题出在哪。5.2 剪得不彻底瓶颈到底在哪另一种常见情况是剪了但没什么用程序照样超时。这时候要警惕你的剪枝可能只是看起来正确实际上很少触发。检查思路是统计每次剪枝条件触发的次数看看哪条剪枝语句贡献最大。我一般会在每条return语句前面挂一个计数器跑一遍后打印出来数字最低的那条往往就是整个搜索的瓶颈所在。如果所有剪枝触发次数都很低那问题多半出在搜索顺序上。搜索顺序决定了best_cur的更新速度也决定了可行性判断的触发时机。试着把数字按从大到小排序把选择更多的分支放在前面优先尝试通常能显著改善。还有一种可能是上界估得太松比如你的cur suffix[i] best_cur判断如果suffix[i]这个后缀和远大于实际可达到的最优值那剪枝条件就很难成立。可以把后缀和改成一个更严谨的“剩余数字中能达到的最大可行值”边界会紧很多。5.3 回溯状态的“现场保护”写深搜时最经典的低级错误是递归返回后没有恢复修改过的变量。比如用visited数组标记已访问节点递归结束时把对应位置置回未访问这个动作丢失就会导致后续分支看到一套被污染的状态结果各种怪象都出来了。我自己的习惯是所有状态修改尽量集中放在递归调用前的紧邻区域恢复动作和修改动作保持结构对称。也就是说如果调用前做了visited[x] True调用返回后紧接着就写visited[x] False不要隔好几行再恢复否则很容易漏。如果你用Java或Python这种引用语言还要特别注意不要用默认参数传递可变对象比如把list作为函数默认参数那会在多次递归调用之间共享同一份对象修改几乎无法收敛。有一个小技巧尽量把不变量直接作为递归函数的参数传递比如cur这个累计和每次递归传cur nums[i]而不是先修改一个外部变量。参数传递天然自带“快照”效果返回后不需要重设能省掉很多手工恢复的麻烦。5.4 递归太深导致栈溢出怎么办深搜的递归深度等于搜索树的深度如果数据规模上千Python这类语言很容易触发递归深度限制直接报出栈溢出错误。解决方法有几个层次。最省事的是调高递归限制比如sys.setrecursionlimit(20000)但这个方法治标不治本深度太大依然会撑爆系统栈。真正的根本解法是把递归改写成显式栈用自己维护的栈来模拟深搜过程。改写后每次循环弹出一种状态处理完把子状态压回栈里。这样栈的空间由你控制可以放在堆上基本不受系统递归栈限制。如果只是竞赛或笔试场景我的优先级是先尝试用迭代深搜不对迭代加深是另一种思路。优先评估数据规模和递归深度如果递归深度不超过几千调高递归限制就够了如果数据规模可能达到十万级那从一开始就应该考虑显式栈方案别等爆栈了再来救。6. 一点个人体会剪枝学到最后我最大的感受是它不只是一个算法技巧更是一种思维方式。解决问题的第一步永远是找到“哪些信息是白给的”第二步才是设计搜索树。搜索写的不是代码而是你对问题约束的理解。我通常会在动手写DFS之前先花几分钟把下面几个问题写下来优化目标是什么有哪些硬约束有没有对称性可以利用剩余资源怎么快速求和。把这四个问题想清楚剪枝条件几乎是自动浮出来的。我在实际使用中还发现一个小习惯非常有用给每个剪枝条件起一个明白的名字比如“下半区截断”“全选无效剪枝”“对称性规约”并且在代码旁边用注释写清楚它为什么安全。这样等你隔几周回来看这段代码或者别人接手你的代码时不用重新推导一遍也能看懂每把剪刀的用途避免因为看不懂而把剪枝条件越调越乱。最后再分享一个扩展思路如果你今天学的是深搜剪枝那明天遇到alpha-beta搜索、排课问题、数独求解本质上都是同一套东西只是那把剪刀的形状不同。把这套理解框架掌握住以后再看到搜索类的题目你第一反应就不再是“我要枚举所有状态”而是“这棵树能不能从一开始就变瘦”。
