1. 从一个跑不动的搜索场景说起很多人第一次接触搜索算法都是从八皇后、数独、迷宫寻路这类经典问题开始的。写出来的代码在小规模数据上跑得飞快可一旦把规模放大——比如数独从 9×9 变成 16×16或者迷宫从 10×10 变成 100×100——程序就像被按了暂停键几分钟甚至几十分钟都出不来结果。这时候大多数人第一反应是我的电脑太慢了或者Python 就是慢但真正的原因往往不是硬件也不是语言而是搜索树被无意义地展开了太多分支。剪枝就是解决这个问题的核心手段。它的本质思想非常朴素在搜索过程中如果已经能判断出某条分支不可能通向正确答案那就果断放弃它不再往下探索。这就像你在迷宫里走看到前面是一堵死墙你不会傻乎乎地撞上去再回头而是直接换路。剪枝做的事情就是让程序学会提前看到死墙。这篇内容面向的是已经会写基础搜索DFS、BFS、回溯但苦于效率上不去的开发者也适合正在准备算法面试、想系统理解剪枝体系的同学。我会从剪枝的分类讲起把可行性剪枝、最优性剪枝、记忆化、启发式排序这些手段逐一拆开配上可运行的 Python 代码再聊聊实际调优中那些文档里不会写的坑。关键词里的原子搜索算法非结构化剪枝这些热词我也会在对应位置做解释避免你看到名词一脸懵。先说一个反直觉的结论剪枝的效果90% 取决于你剪枝的顺序和判断条件放在哪里而不是剪枝本身有多复杂。很多人写了一堆剪枝条件结果因为放错了位置性能反而更差。这个坑我在后面会专门用一节来讲。2. 剪枝到底在剪什么搜索树的形状决定了你的策略2.1 搜索树是一棵指数爆炸的树任何搜索算法本质上都是在遍历一棵隐式的树。以子集枚举为例n 个元素每个选或不选搜索树有 2ⁿ 个叶子节点。n20 时是 100 万n30 时是 10 亿n40 时就是 1 万亿。这就是指数爆炸的威力——你不可能靠更快的 CPU 来解决只能靠不访问那些没用的节点。剪枝要做的就是在这棵树上做减法。但减法的效果取决于树的形状。如果一棵树是宽而浅的每一层分支很多但深度不大那么剪掉一个浅层节点能省下大量子孙如果树是窄而深的每层分支少但很深剪枝的收益就相对有限。理解这一点你才能判断某个剪枝策略值不值得加。2.2 三类剪枝的定位差异从工程实践角度我习惯把剪枝分成三大类它们的适用场景和实现难度完全不同剪枝类型核心判断依据典型场景实现难度可行性剪枝当前状态是否已经违反约束数独、八皇后、约束满足低最优性剪枝当前代价是否已经超过已知最优解最短路、旅行商、背包中记忆化剪枝该状态是否已经访问过动态规划、图搜索中启发式剪枝用估价函数预判分支优劣A*、IDA*、博弈搜索高可行性剪枝是最容易上手的你只需要在递归入口处加一个if not valid(state): return就行。最优性剪枝需要你维护一个当前已知最优解然后在搜索过程中不断比较。记忆化剪枝的关键是设计一个能唯一标识状态的 key。启发式剪枝最复杂但威力也最大它需要你设计一个乐观估计函数保证不会误剪掉真正的最优解。2.3 为什么剪得越早越值钱这是剪枝最重要的直觉。假设你在搜索树的第 k 层剪掉一个节点而这个节点下面平均每个节点有 b 个分支、剩余深度为 d那么你省下的节点数大约是 b^d 量级。也就是说在第 1 层剪掉一个节点可能比在第 10 层剪掉一万个节点还划算。这个直觉直接指导了工程实践剪枝条件要尽量往递归的浅层放能在进入递归之前判断的就不要等到递归里面再判断。我见过太多代码把约束检查写在递归的最深处结果白白展开了大量中间节点。把检查前移往往能带来几倍甚至几十倍的加速而且不需要改任何算法逻辑。3. 可行性剪枝把不可能挡在门外3.1 数独求解器里的约束传播数独是讲可行性剪枝最好的例子。一个朴素的回溯求解器会在每个空格尝试填入 1-9然后递归。但如果你在填之前先检查这个数字在当前行、列、宫是否已经出现就能砍掉大量无效分支。def solve_sudoku(board): empty find_empty(board) if not empty: return True row, col empty for num in range(1, 10): if is_valid(board, row, col, num): board[row][col] num if solve_sudoku(board): return True board[row][col] 0 return False def is_valid(board, row, col, num): for i in range(9): if board[row][i] num: return False if board[i][col] num: return False br, bc 3 * (row // 3), 3 * (col // 3) for i in range(br, br 3): for j in range(bc, bc 3): if board[i][j] num: return False return True这段代码能跑但还不够快。真正的优化在于约束传播每次填入一个数字后立刻更新同行、同列、同宫里其他格子的候选数字集合。如果某个格子的候选集合变成空集说明这条路走不通立即回溯。更进一步如果某个数字在某行只有一个格子能放那就直接确定它。这种确定性推理能把搜索树砍掉一大半。3.2 八皇后问题的对角线剪枝八皇后是另一个经典。核心约束是任意两个皇后不能在同一行、同一列、同一对角线。行和列的检查很直观对角线的检查是新手最容易写错的地方。关键观察对于位置 (r, c)它所在的两条对角线分别满足r - c为常数和r c为常数。所以你可以用两个布尔数组diag1[r-cn]和diag2[rc]来 O(1) 判断对角线冲突而不是每次循环去检查所有已放置的皇后。def solve_n_queens(n): result [] cols [False] * n diag1 [False] * (2 * n) diag2 [False] * (2 * n) queens [] def backtrack(row): if row n: result.append(queens[:]) return for col in range(n): if cols[col] or diag1[row - col n] or diag2[row col]: continue cols[col] diag1[row - col n] diag2[row col] True queens.append(col) backtrack(row 1) queens.pop() cols[col] diag1[row - col n] diag2[row col] False backtrack(0) return result这个版本比每次循环检查所有已放皇后的版本快一个数量级。原因很简单把 O(n) 的检查降到了 O(1)而且判断放在了循环的最前面剪枝发生得足够早。3.3 可行性剪枝的常见误区第一个误区是检查条件写得太宽松。比如数独里只检查行不检查宫那剪枝效果大打折扣。第二个误区是检查条件写得太严格导致误剪。比如某些问题里你用一个必要条件去剪枝但这个条件本身不充分就会把正确解也剪掉。判断一个剪枝条件是否安全标准是它必须是当前状态不可能通向解的充分条件而不是必要条件。换句话说宁可漏剪不可错剪。第三个误区是在递归内部重复计算。比如每次递归都重新扫描整个棋盘来判断合法性这种 O(n²) 的检查如果放在深层递归里开销会累积得非常可怕。正确做法是用增量更新的方式维护状态进入递归时改一下标记回溯时改回来。4. 最优性剪枝用已知最优解当标尺4.1 分支限界法的核心逻辑最优性剪枝的典型代表是分支限界法Branch and Bound。它的思路是维护一个当前已知的最优解best在搜索过程中如果当前路径的代价已经不可能优于best就直接剪掉。以 0/1 背包为例。你有一个容量 W 的背包n 个物品各有重量 w[i] 和价值 v[i]求能装下的最大价值。朴素做法是枚举所有子集2ⁿ 复杂度。用分支限界你可以这样做def knapsack_branch_bound(weights, values, capacity): n len(weights) items sorted(range(n), keylambda i: values[i] / weights[i], reverseTrue) best [0] def bound(idx, current_weight, current_value): # 乐观估计剩余物品按性价比全装可分割 total current_value remaining capacity - current_weight for i in range(idx, n): item items[i] if weights[item] remaining: remaining - weights[item] total values[item] else: total values[item] * remaining / weights[item] break return total def dfs(idx, current_weight, current_value): if current_value best[0]: best[0] current_value if idx n: return item items[idx] # 尝试装入 if current_weight weights[item] capacity: dfs(idx 1, current_weight weights[item], current_value values[item]) # 尝试不装先判断上界 if bound(idx 1, current_weight, current_value) best[0]: dfs(idx 1, current_weight, current_value) dfs(0, 0, 0) return best[0]这里的关键是bound函数。它计算的是如果剩余物品可以任意分割最多能拿到多少价值。这是一个乐观上界——真实值一定不会超过它。所以如果这个上界都不如当前最优解那这条分支就绝对没戏可以放心剪掉。4.2 上界函数的设计原则上界函数的设计是分支限界的灵魂。它必须满足两个条件一是必须是真实值的上界不能低估二是要尽可能紧越接近真实值剪枝越有效。如果上界太松比如你直接返回剩余所有物品价值之和那几乎剪不掉任何东西。如果上界太紧甚至低于真实值那就会误剪最优解结果就错了。这个平衡点需要根据具体问题来调。在旅行商问题TSP里常用的上界是最小生成树或者分配问题的松弛解。在任务调度问题里常用的是剩余任务的最短处理时间之和。这些上界函数的共同特点是计算代价不高但能给出一个合理的乐观估计。4.3 剪枝顺序对性能的影响这里有一个很多人忽略的点先搜索哪个分支直接决定了最优性剪枝的效果。如果你先找到一个比较好的解那么best就会很快变得很大后续的剪枝就会更狠。反之如果你先搜索的分支都很差best长时间停留在很小的值剪枝就形同虚设。所以实践中我们通常会把分支按看起来更可能通向好解的顺序排列。比如背包问题里按性价比排序TSP 里按距离排序。这个技巧叫启发式排序它本身不改变算法正确性但能显著提升剪枝效率。我做过一个测试在同一个 TSP 实例上仅仅调整了分支搜索顺序运行时间从 12 秒降到了 1.8 秒代码逻辑一行没改。5. 记忆化剪枝别在同一个坑里摔两次5.1 状态去重的本质记忆化Memoization严格来说不算传统意义的剪枝但它的效果和剪枝一样——避免重复计算。它的核心是如果两个不同的搜索路径到达了同一个状态那么从这个状态出发的所有后续搜索都是重复的只需要算一次。以斐波那契数列为例朴素递归是 O(2ⁿ)加个字典缓存就变成 O(n)。在搜索问题里状态去重同样威力巨大。比如从 (0,0) 走到 (m,n) 有多少条路径如果只允许向右和向下走那么到达 (i,j) 的路径数只取决于 (i,j) 这个坐标和你怎么走过来的无关。这时候就可以用记忆化。from functools import lru_cache def count_paths(m, n): lru_cache(maxsizeNone) def dp(i, j): if i 0 or j 0: return 1 return dp(i - 1, j) dp(i, j - 1) return dp(m, n)5.2 状态 key 的设计陷阱记忆化最容易踩的坑是状态 key 设计错误。如果 key 设计得太粗会把不同状态误认为相同导致结果错误如果 key 设计得太细又起不到去重效果。举个例子在带剩余步数限制的搜索问题里状态必须包含当前位置和剩余步数两个维度。如果你只用位置做 key就会把剩余 3 步到达 A和剩余 5 步到达 A当成同一个状态这显然是错的。另一个陷阱是状态空间太大导致内存爆炸。比如状态 key 是一个长度为 100 的数组那缓存根本存不下。这时候要么放弃记忆化要么想办法压缩状态表示比如用位运算、哈希。5.3 记忆化与剪枝的配合记忆化和剪枝可以叠加使用而且效果往往是乘法级的。比如在博弈搜索里先用 Alpha-Beta 剪枝砍掉大量分支再用置换表一种记忆化结构缓存已经评估过的局面两者结合能把搜索深度提升好几层。但要注意一个顺序问题记忆化的查询应该放在剪枝判断之前还是之后我的经验是如果记忆化查询本身开销很小比如哈希表查找那就放在最前面因为一旦命中就能直接返回省掉后续所有判断。如果记忆化查询开销较大那就先做便宜的剪枝判断命中了再查缓存。6. 启发式剪枝让搜索有方向感6.1 A* 算法里的估价函数A* 是启发式搜索的代表。它给每个节点算一个f g h其中 g 是从起点到当前节点的实际代价h 是从当前节点到终点的估计代价。搜索时优先扩展 f 最小的节点。A* 的正确性依赖于 h 函数的可采纳性h 必须永远不高估真实代价。如果 h 高估了A* 可能找到的不是最优解。如果 h 恒为 0A* 退化成 Dijkstra。如果 h 恰好等于真实代价A* 会直奔最优路径一步不绕。import heapq def a_star(graph, start, goal, h): open_set [(h(start, goal), 0, start, [start])] visited {} while open_set: f, g, node, path heapq.heappop(open_set) if node goal: return path if node in visited and visited[node] g: continue visited[node] g for neighbor, cost in graph[node]: new_g g cost new_f new_g h(neighbor, goal) heapq.heappush(open_set, (new_f, new_g, neighbor, path [neighbor])) return None6.2 启发式函数的松紧权衡h 函数的设计和前面说的上界函数类似也是越紧越好但不能过紧。在网格地图里常用的 h 是曼哈顿距离只能上下左右走或欧几里得距离可以斜着走。这两个都是可采纳的因为直线距离永远不可能超过实际路径长度。但有时候为了速度我们会故意用一个稍微高估的 h这叫加权 A*。它能更快找到解但可能不是最优的。在游戏寻路这种差不多就行的场景里加权 A* 非常常用。这个取舍没有标准答案取决于你对最优性的要求有多严格。6.3 迭代加深与 IDA*当内存受限时A* 的开放列表可能撑爆内存。这时候可以用 IDA*迭代加深 A*。它的思路是不维护开放列表而是用 DFS 配合一个f 值上限超过上限就剪枝。如果这一轮没找到解就放宽上限再来一轮。IDA* 的内存开销是 O(d)d 是搜索深度远小于 A* 的 O(b^d)。代价是它会重复搜索一些节点。但在很多实际问题里这个重复开销可以接受而内存节省是刚需。7. 那些文档里不会写的剪枝实战经验7.1 剪枝条件的放置位置比条件本身更重要我前面反复强调这一点这里给一个具体例子。假设你在解一个从矩阵左上角走到右下角路径和最小的问题同时有障碍物。你的剪枝条件是当前路径和已经超过已知最优解。错误做法在递归函数开头判断。 正确做法在决定要不要往某个方向走之前就判断。差别在哪错误做法里你已经进入了递归已经做了一次函数调用、一次参数传递、一次栈帧分配然后才发现该剪。正确做法里这些开销全部省掉了。在深度很大的搜索里函数调用本身的开销可能比剪枝逻辑还大。7.2 剪枝不是越多越好新手容易陷入剪枝条件越多越牛的误区。实际上每个剪枝条件本身都有计算开销。如果一个剪枝条件只能砍掉 1% 的分支但它本身的计算量相当于搜索 5% 的节点那加它反而亏了。判断一个剪枝条件值不值得加有个简单的经验法则如果这个条件的计算复杂度是 O(1) 或 O(log n)且能砍掉至少 10% 的分支那就值得加。如果计算复杂度是 O(n) 以上那它必须能砍掉 50% 以上的分支才划算。7.3 用剪枝计数器来诊断性能这是我个人最推荐的一个调试技巧在剪枝生效的地方加一个计数器统计每个剪枝条件分别砍掉了多少节点。跑完之后打印出来你就能清楚看到哪个条件在干活、哪个条件在摸鱼。prune_stats {bound: 0, visited: 0, constraint: 0} def dfs(state): if not valid(state): prune_stats[constraint] 1 return if state in visited: prune_stats[visited] 1 return if bound(state) best: prune_stats[bound] 1 return # ... 继续搜索跑完打印prune_stats如果某个条件计数是 0说明它从来没生效过要么是条件写错了要么是这个场景下它根本没用。如果某个条件计数特别大说明它是性能瓶颈的主要贡献者值得进一步优化。7.4 关于原子搜索算法和非结构化剪枝这两个热词有读者可能会在搜索时看到原子搜索算法这个词。它通常指的是一种把搜索过程拆解成不可再分的原子操作的框架每个原子操作要么完整执行要么完全不执行便于并行化和状态管理。在 Python 里实现时核心是把搜索状态封装成不可变对象每次扩展生成新状态而不是原地修改这样天然支持缓存和并行。非结构化剪枝这个词更多出现在模型压缩领域指的是不按固定模式比如整行整列剪而是按重要性逐个剪掉参数。虽然和搜索算法的剪枝不是一回事但思想是相通的都是判断哪些部分对最终结果贡献小可以安全移除。理解了这个共性你会发现剪枝这个思想的应用范围远比想象中广。7.5 一个完整的调优流程最后把我平时调优搜索算法的流程整理一下你可以直接照着做先写一个能跑通的朴素版本不加任何剪枝确认结果正确。加可行性剪枝把明显非法的分支砍掉这一步通常收益最大。加记忆化如果状态空间可枚举的话。加最优性剪枝维护 best 值注意分支搜索顺序。加启发式排序把更可能通向好解的分支排在前面。用计数器诊断找出摸鱼的剪枝条件删掉或优化。调整剪枝判断的位置能前移的尽量前移。这个流程走下来一个原本跑几分钟的搜索通常能压到几秒甚至几百毫秒。而且每一步都是可验证的不会出现改了一堆结果跑错了的情况。剪枝这件事说到底就是和搜索树做斗争。你对树的形状理解得越深对哪条分支没戏判断得越准你的程序就跑得越快。没有什么银弹靠的是一层层约束的叠加和对细节的反复打磨。我在实际项目里最深的体会是先让程序跑对再让它跑快最后才去追求跑得优雅。顺序反了往往两头都顾不上。
1. 从一个跑不动的搜索场景说起很多人第一次接触搜索算法都是从八皇后、数独、迷宫寻路这类经典问题开始的。写出来的代码在小规模数据上跑得飞快可一旦把规模放大——比如数独从 9×9 变成 16×16或者迷宫从 10×10 变成 100×100——程序就像被按了暂停键几分钟甚至几十分钟都出不来结果。这时候大多数人第一反应是我的电脑太慢了或者Python 就是慢但真正的原因往往不是硬件也不是语言而是搜索树被无意义地展开了太多分支。剪枝就是解决这个问题的核心手段。它的本质思想非常朴素在搜索过程中如果已经能判断出某条分支不可能通向正确答案那就果断放弃它不再往下探索。这就像你在迷宫里走看到前面是一堵死墙你不会傻乎乎地撞上去再回头而是直接换路。剪枝做的事情就是让程序学会提前看到死墙。这篇内容面向的是已经会写基础搜索DFS、BFS、回溯但苦于效率上不去的开发者也适合正在准备算法面试、想系统理解剪枝体系的同学。我会从剪枝的分类讲起把可行性剪枝、最优性剪枝、记忆化、启发式排序这些手段逐一拆开配上可运行的 Python 代码再聊聊实际调优中那些文档里不会写的坑。关键词里的原子搜索算法非结构化剪枝这些热词我也会在对应位置做解释避免你看到名词一脸懵。先说一个反直觉的结论剪枝的效果90% 取决于你剪枝的顺序和判断条件放在哪里而不是剪枝本身有多复杂。很多人写了一堆剪枝条件结果因为放错了位置性能反而更差。这个坑我在后面会专门用一节来讲。2. 剪枝到底在剪什么搜索树的形状决定了你的策略2.1 搜索树是一棵指数爆炸的树任何搜索算法本质上都是在遍历一棵隐式的树。以子集枚举为例n 个元素每个选或不选搜索树有 2ⁿ 个叶子节点。n20 时是 100 万n30 时是 10 亿n40 时就是 1 万亿。这就是指数爆炸的威力——你不可能靠更快的 CPU 来解决只能靠不访问那些没用的节点。剪枝要做的就是在这棵树上做减法。但减法的效果取决于树的形状。如果一棵树是宽而浅的每一层分支很多但深度不大那么剪掉一个浅层节点能省下大量子孙如果树是窄而深的每层分支少但很深剪枝的收益就相对有限。理解这一点你才能判断某个剪枝策略值不值得加。2.2 三类剪枝的定位差异从工程实践角度我习惯把剪枝分成三大类它们的适用场景和实现难度完全不同剪枝类型核心判断依据典型场景实现难度可行性剪枝当前状态是否已经违反约束数独、八皇后、约束满足低最优性剪枝当前代价是否已经超过已知最优解最短路、旅行商、背包中记忆化剪枝该状态是否已经访问过动态规划、图搜索中启发式剪枝用估价函数预判分支优劣A*、IDA*、博弈搜索高可行性剪枝是最容易上手的你只需要在递归入口处加一个if not valid(state): return就行。最优性剪枝需要你维护一个当前已知最优解然后在搜索过程中不断比较。记忆化剪枝的关键是设计一个能唯一标识状态的 key。启发式剪枝最复杂但威力也最大它需要你设计一个乐观估计函数保证不会误剪掉真正的最优解。2.3 为什么剪得越早越值钱这是剪枝最重要的直觉。假设你在搜索树的第 k 层剪掉一个节点而这个节点下面平均每个节点有 b 个分支、剩余深度为 d那么你省下的节点数大约是 b^d 量级。也就是说在第 1 层剪掉一个节点可能比在第 10 层剪掉一万个节点还划算。这个直觉直接指导了工程实践剪枝条件要尽量往递归的浅层放能在进入递归之前判断的就不要等到递归里面再判断。我见过太多代码把约束检查写在递归的最深处结果白白展开了大量中间节点。把检查前移往往能带来几倍甚至几十倍的加速而且不需要改任何算法逻辑。3. 可行性剪枝把不可能挡在门外3.1 数独求解器里的约束传播数独是讲可行性剪枝最好的例子。一个朴素的回溯求解器会在每个空格尝试填入 1-9然后递归。但如果你在填之前先检查这个数字在当前行、列、宫是否已经出现就能砍掉大量无效分支。def solve_sudoku(board): empty find_empty(board) if not empty: return True row, col empty for num in range(1, 10): if is_valid(board, row, col, num): board[row][col] num if solve_sudoku(board): return True board[row][col] 0 return False def is_valid(board, row, col, num): for i in range(9): if board[row][i] num: return False if board[i][col] num: return False br, bc 3 * (row // 3), 3 * (col // 3) for i in range(br, br 3): for j in range(bc, bc 3): if board[i][j] num: return False return True这段代码能跑但还不够快。真正的优化在于约束传播每次填入一个数字后立刻更新同行、同列、同宫里其他格子的候选数字集合。如果某个格子的候选集合变成空集说明这条路走不通立即回溯。更进一步如果某个数字在某行只有一个格子能放那就直接确定它。这种确定性推理能把搜索树砍掉一大半。3.2 八皇后问题的对角线剪枝八皇后是另一个经典。核心约束是任意两个皇后不能在同一行、同一列、同一对角线。行和列的检查很直观对角线的检查是新手最容易写错的地方。关键观察对于位置 (r, c)它所在的两条对角线分别满足r - c为常数和r c为常数。所以你可以用两个布尔数组diag1[r-cn]和diag2[rc]来 O(1) 判断对角线冲突而不是每次循环去检查所有已放置的皇后。def solve_n_queens(n): result [] cols [False] * n diag1 [False] * (2 * n) diag2 [False] * (2 * n) queens [] def backtrack(row): if row n: result.append(queens[:]) return for col in range(n): if cols[col] or diag1[row - col n] or diag2[row col]: continue cols[col] diag1[row - col n] diag2[row col] True queens.append(col) backtrack(row 1) queens.pop() cols[col] diag1[row - col n] diag2[row col] False backtrack(0) return result这个版本比每次循环检查所有已放皇后的版本快一个数量级。原因很简单把 O(n) 的检查降到了 O(1)而且判断放在了循环的最前面剪枝发生得足够早。3.3 可行性剪枝的常见误区第一个误区是检查条件写得太宽松。比如数独里只检查行不检查宫那剪枝效果大打折扣。第二个误区是检查条件写得太严格导致误剪。比如某些问题里你用一个必要条件去剪枝但这个条件本身不充分就会把正确解也剪掉。判断一个剪枝条件是否安全标准是它必须是当前状态不可能通向解的充分条件而不是必要条件。换句话说宁可漏剪不可错剪。第三个误区是在递归内部重复计算。比如每次递归都重新扫描整个棋盘来判断合法性这种 O(n²) 的检查如果放在深层递归里开销会累积得非常可怕。正确做法是用增量更新的方式维护状态进入递归时改一下标记回溯时改回来。4. 最优性剪枝用已知最优解当标尺4.1 分支限界法的核心逻辑最优性剪枝的典型代表是分支限界法Branch and Bound。它的思路是维护一个当前已知的最优解best在搜索过程中如果当前路径的代价已经不可能优于best就直接剪掉。以 0/1 背包为例。你有一个容量 W 的背包n 个物品各有重量 w[i] 和价值 v[i]求能装下的最大价值。朴素做法是枚举所有子集2ⁿ 复杂度。用分支限界你可以这样做def knapsack_branch_bound(weights, values, capacity): n len(weights) items sorted(range(n), keylambda i: values[i] / weights[i], reverseTrue) best [0] def bound(idx, current_weight, current_value): # 乐观估计剩余物品按性价比全装可分割 total current_value remaining capacity - current_weight for i in range(idx, n): item items[i] if weights[item] remaining: remaining - weights[item] total values[item] else: total values[item] * remaining / weights[item] break return total def dfs(idx, current_weight, current_value): if current_value best[0]: best[0] current_value if idx n: return item items[idx] # 尝试装入 if current_weight weights[item] capacity: dfs(idx 1, current_weight weights[item], current_value values[item]) # 尝试不装先判断上界 if bound(idx 1, current_weight, current_value) best[0]: dfs(idx 1, current_weight, current_value) dfs(0, 0, 0) return best[0]这里的关键是bound函数。它计算的是如果剩余物品可以任意分割最多能拿到多少价值。这是一个乐观上界——真实值一定不会超过它。所以如果这个上界都不如当前最优解那这条分支就绝对没戏可以放心剪掉。4.2 上界函数的设计原则上界函数的设计是分支限界的灵魂。它必须满足两个条件一是必须是真实值的上界不能低估二是要尽可能紧越接近真实值剪枝越有效。如果上界太松比如你直接返回剩余所有物品价值之和那几乎剪不掉任何东西。如果上界太紧甚至低于真实值那就会误剪最优解结果就错了。这个平衡点需要根据具体问题来调。在旅行商问题TSP里常用的上界是最小生成树或者分配问题的松弛解。在任务调度问题里常用的是剩余任务的最短处理时间之和。这些上界函数的共同特点是计算代价不高但能给出一个合理的乐观估计。4.3 剪枝顺序对性能的影响这里有一个很多人忽略的点先搜索哪个分支直接决定了最优性剪枝的效果。如果你先找到一个比较好的解那么best就会很快变得很大后续的剪枝就会更狠。反之如果你先搜索的分支都很差best长时间停留在很小的值剪枝就形同虚设。所以实践中我们通常会把分支按看起来更可能通向好解的顺序排列。比如背包问题里按性价比排序TSP 里按距离排序。这个技巧叫启发式排序它本身不改变算法正确性但能显著提升剪枝效率。我做过一个测试在同一个 TSP 实例上仅仅调整了分支搜索顺序运行时间从 12 秒降到了 1.8 秒代码逻辑一行没改。5. 记忆化剪枝别在同一个坑里摔两次5.1 状态去重的本质记忆化Memoization严格来说不算传统意义的剪枝但它的效果和剪枝一样——避免重复计算。它的核心是如果两个不同的搜索路径到达了同一个状态那么从这个状态出发的所有后续搜索都是重复的只需要算一次。以斐波那契数列为例朴素递归是 O(2ⁿ)加个字典缓存就变成 O(n)。在搜索问题里状态去重同样威力巨大。比如从 (0,0) 走到 (m,n) 有多少条路径如果只允许向右和向下走那么到达 (i,j) 的路径数只取决于 (i,j) 这个坐标和你怎么走过来的无关。这时候就可以用记忆化。from functools import lru_cache def count_paths(m, n): lru_cache(maxsizeNone) def dp(i, j): if i 0 or j 0: return 1 return dp(i - 1, j) dp(i, j - 1) return dp(m, n)5.2 状态 key 的设计陷阱记忆化最容易踩的坑是状态 key 设计错误。如果 key 设计得太粗会把不同状态误认为相同导致结果错误如果 key 设计得太细又起不到去重效果。举个例子在带剩余步数限制的搜索问题里状态必须包含当前位置和剩余步数两个维度。如果你只用位置做 key就会把剩余 3 步到达 A和剩余 5 步到达 A当成同一个状态这显然是错的。另一个陷阱是状态空间太大导致内存爆炸。比如状态 key 是一个长度为 100 的数组那缓存根本存不下。这时候要么放弃记忆化要么想办法压缩状态表示比如用位运算、哈希。5.3 记忆化与剪枝的配合记忆化和剪枝可以叠加使用而且效果往往是乘法级的。比如在博弈搜索里先用 Alpha-Beta 剪枝砍掉大量分支再用置换表一种记忆化结构缓存已经评估过的局面两者结合能把搜索深度提升好几层。但要注意一个顺序问题记忆化的查询应该放在剪枝判断之前还是之后我的经验是如果记忆化查询本身开销很小比如哈希表查找那就放在最前面因为一旦命中就能直接返回省掉后续所有判断。如果记忆化查询开销较大那就先做便宜的剪枝判断命中了再查缓存。6. 启发式剪枝让搜索有方向感6.1 A* 算法里的估价函数A* 是启发式搜索的代表。它给每个节点算一个f g h其中 g 是从起点到当前节点的实际代价h 是从当前节点到终点的估计代价。搜索时优先扩展 f 最小的节点。A* 的正确性依赖于 h 函数的可采纳性h 必须永远不高估真实代价。如果 h 高估了A* 可能找到的不是最优解。如果 h 恒为 0A* 退化成 Dijkstra。如果 h 恰好等于真实代价A* 会直奔最优路径一步不绕。import heapq def a_star(graph, start, goal, h): open_set [(h(start, goal), 0, start, [start])] visited {} while open_set: f, g, node, path heapq.heappop(open_set) if node goal: return path if node in visited and visited[node] g: continue visited[node] g for neighbor, cost in graph[node]: new_g g cost new_f new_g h(neighbor, goal) heapq.heappush(open_set, (new_f, new_g, neighbor, path [neighbor])) return None6.2 启发式函数的松紧权衡h 函数的设计和前面说的上界函数类似也是越紧越好但不能过紧。在网格地图里常用的 h 是曼哈顿距离只能上下左右走或欧几里得距离可以斜着走。这两个都是可采纳的因为直线距离永远不可能超过实际路径长度。但有时候为了速度我们会故意用一个稍微高估的 h这叫加权 A*。它能更快找到解但可能不是最优的。在游戏寻路这种差不多就行的场景里加权 A* 非常常用。这个取舍没有标准答案取决于你对最优性的要求有多严格。6.3 迭代加深与 IDA*当内存受限时A* 的开放列表可能撑爆内存。这时候可以用 IDA*迭代加深 A*。它的思路是不维护开放列表而是用 DFS 配合一个f 值上限超过上限就剪枝。如果这一轮没找到解就放宽上限再来一轮。IDA* 的内存开销是 O(d)d 是搜索深度远小于 A* 的 O(b^d)。代价是它会重复搜索一些节点。但在很多实际问题里这个重复开销可以接受而内存节省是刚需。7. 那些文档里不会写的剪枝实战经验7.1 剪枝条件的放置位置比条件本身更重要我前面反复强调这一点这里给一个具体例子。假设你在解一个从矩阵左上角走到右下角路径和最小的问题同时有障碍物。你的剪枝条件是当前路径和已经超过已知最优解。错误做法在递归函数开头判断。 正确做法在决定要不要往某个方向走之前就判断。差别在哪错误做法里你已经进入了递归已经做了一次函数调用、一次参数传递、一次栈帧分配然后才发现该剪。正确做法里这些开销全部省掉了。在深度很大的搜索里函数调用本身的开销可能比剪枝逻辑还大。7.2 剪枝不是越多越好新手容易陷入剪枝条件越多越牛的误区。实际上每个剪枝条件本身都有计算开销。如果一个剪枝条件只能砍掉 1% 的分支但它本身的计算量相当于搜索 5% 的节点那加它反而亏了。判断一个剪枝条件值不值得加有个简单的经验法则如果这个条件的计算复杂度是 O(1) 或 O(log n)且能砍掉至少 10% 的分支那就值得加。如果计算复杂度是 O(n) 以上那它必须能砍掉 50% 以上的分支才划算。7.3 用剪枝计数器来诊断性能这是我个人最推荐的一个调试技巧在剪枝生效的地方加一个计数器统计每个剪枝条件分别砍掉了多少节点。跑完之后打印出来你就能清楚看到哪个条件在干活、哪个条件在摸鱼。prune_stats {bound: 0, visited: 0, constraint: 0} def dfs(state): if not valid(state): prune_stats[constraint] 1 return if state in visited: prune_stats[visited] 1 return if bound(state) best: prune_stats[bound] 1 return # ... 继续搜索跑完打印prune_stats如果某个条件计数是 0说明它从来没生效过要么是条件写错了要么是这个场景下它根本没用。如果某个条件计数特别大说明它是性能瓶颈的主要贡献者值得进一步优化。7.4 关于原子搜索算法和非结构化剪枝这两个热词有读者可能会在搜索时看到原子搜索算法这个词。它通常指的是一种把搜索过程拆解成不可再分的原子操作的框架每个原子操作要么完整执行要么完全不执行便于并行化和状态管理。在 Python 里实现时核心是把搜索状态封装成不可变对象每次扩展生成新状态而不是原地修改这样天然支持缓存和并行。非结构化剪枝这个词更多出现在模型压缩领域指的是不按固定模式比如整行整列剪而是按重要性逐个剪掉参数。虽然和搜索算法的剪枝不是一回事但思想是相通的都是判断哪些部分对最终结果贡献小可以安全移除。理解了这个共性你会发现剪枝这个思想的应用范围远比想象中广。7.5 一个完整的调优流程最后把我平时调优搜索算法的流程整理一下你可以直接照着做先写一个能跑通的朴素版本不加任何剪枝确认结果正确。加可行性剪枝把明显非法的分支砍掉这一步通常收益最大。加记忆化如果状态空间可枚举的话。加最优性剪枝维护 best 值注意分支搜索顺序。加启发式排序把更可能通向好解的分支排在前面。用计数器诊断找出摸鱼的剪枝条件删掉或优化。调整剪枝判断的位置能前移的尽量前移。这个流程走下来一个原本跑几分钟的搜索通常能压到几秒甚至几百毫秒。而且每一步都是可验证的不会出现改了一堆结果跑错了的情况。剪枝这件事说到底就是和搜索树做斗争。你对树的形状理解得越深对哪条分支没戏判断得越准你的程序就跑得越快。没有什么银弹靠的是一层层约束的叠加和对细节的反复打磨。我在实际项目里最深的体会是先让程序跑对再让它跑快最后才去追求跑得优雅。顺序反了往往两头都顾不上。
