深搜剪枝实战：Addition Chains 加法链问题精讲

1. 从一道经典题看深搜剪枝的真正价值Addition Chains中文常译为“加法链”是一道在算法竞赛圈子里流传很久的搜索入门题。题目本身不复杂给定一个整数 n要求构造一个从 1 开始的序列序列中每个数都等于前面某两个数之和这两个数可以相同并且序列的最后一个数恰好是 n要求序列长度尽可能短。比如 n5 时一条合法的加法链是 1,2,4,5长度是 4而 1,2,3,5 也是合法的长度同样是 4。但如果 n61,2,4,6 和 1,2,3,6 都是长度 4 的链而 1,2,4,5,6 长度是 5显然不是最优。这道题之所以被放在“深搜的剪枝技巧”这一章里是因为它天然适合用深度优先搜索来枚举所有可能的序列但如果不加任何剪枝搜索树会随着 n 的增大迅速膨胀到无法接受的程度。很多初学者第一次写这道题时往往能过 n 比较小的测试点一旦 n 到了几十甚至上百程序就会超时或者爆栈。问题不在于深搜本身而在于没有理解剪枝的本质——剪枝不是随便加几个 if 判断而是要对搜索空间的数学结构有清晰的认识知道哪些分支是“注定不可能产生最优解”的然后果断砍掉。我在最初接触这道题的时候也走过不少弯路。当时觉得只要用迭代加深控制搜索深度再配合一个简单的“当前值不能超过 n”的判断就够了结果提交上去只过了前几个点。后来把搜索树画出来仔细分析才发现真正有效的剪枝远不止这些。加法链问题有一个很重要的性质序列是严格递增的而且每个新元素必须由前面已经存在的两个元素相加得到。这意味着搜索空间虽然大但结构非常规整只要抓住几个关键的不等式关系就能把绝大部分无效分支提前排除。这篇文章会从零开始把 Addition Chains 这道题的深搜剪枝思路完整拆解一遍。我会先讲清楚为什么朴素的深搜会爆炸然后逐一分析几种核心剪枝手段的数学原理和代码实现接着给出一个可以直接复现的完整方案最后分享一些在实际调试过程中容易忽略的细节和踩坑经验。无论你是刚开始学搜索的初学者还是已经写过一些深搜题目但总在剪枝环节卡住的进阶者相信都能从中找到对自己有用的东西。2. 朴素深搜为什么会爆炸搜索空间的结构分析2.1 加法链的搜索树到底有多大要理解剪枝的必要性首先得知道不剪枝的搜索树规模有多大。对于 Addition Chains 问题搜索的过程是这样的从序列 [1] 开始每一步尝试从当前序列中选出两个数可以相同把它们的和追加到序列末尾然后递归下去直到序列末尾等于 n 为止。表面上看每一步的选择数似乎不多但问题在于搜索深度和分支数会同时增长。假设当前序列的长度为 k那么可选的数对数量大约是 k*(k1)/2 个。第一步只有 [1]只能选 112所以序列变成 [1,2]。第二步有 [1,2]可选 112但 2 已经在序列里了追加重复值没有意义、123、224所以有两个有效分支。第三步如果序列是 [1,2,3]可选的和有 112、123、134、224、235、336去掉重复和已经存在的值有效分支是 4、5、6 三个。可以看到随着序列变长分支数在快速增加。更麻烦的是搜索深度本身也不小。对于 n100最优加法链的长度大约是 8 到 10 左右但朴素深搜如果不限制深度可能会沿着一条很长的路径一直搜下去因为你可以不断地加出比 n 小的数把序列拉得很长。比如 1,2,3,4,5,6,...,100 这样一条链虽然合法但显然不是最优的可朴素深搜会把它当成一条可能的路径去尝试。这就导致搜索树既宽又深节点数量呈指数级增长。2.2 没有剪枝时程序的实际表现我做过一个简单的实验写一个最朴素的深搜版本不加任何剪枝只判断当前序列末尾是否等于 n然后统计递归调用次数。当 n20 的时候递归调用次数还在可接受范围内大概几万次n30 的时候已经涨到几百万次n40 的时候直接超过了我设置的递归上限程序栈溢出。这还只是统计调用次数实际运行时间因为每次都要遍历序列选数对开销更大。这个实验说明一个问题加法链问题的搜索空间对 n 非常敏感n 每增加一点搜索树规模就会跳一个数量级。如果不在搜索过程中主动砍掉那些明显不可能通向最优解的分支程序根本跑不到 n 稍微大一点的测试点。而竞赛题目里的 n 往往会给到 100 甚至更大所以剪枝不是“锦上添花”而是“生死攸关”。2.3 剪枝的两个基本方向在加法链问题里剪枝可以从两个方向入手。第一个方向是限制搜索深度也就是用迭代加深的方式先尝试搜索长度为 1 的链、长度为 2 的链、长度为 3 的链……直到某个长度下找到了合法解就输出并停止。这样做的好处是一旦在较浅的深度找到了解就不需要再去搜索更深的层次避免了大量无效的深层搜索。第二个方向是在每一层搜索时利用数学不等式判断当前分支是否还有可能产生合法解如果没有可能就直接返回不再往下递归。这两个方向需要配合使用。迭代加深控制了搜索的“纵向”范围而每层的可行性剪枝控制了搜索的“横向”宽度。只做其中一个效果都会打折扣。比如只做迭代加深每一层仍然会展开大量无效分支搜索树虽然变浅了但宽度没变总节点数还是很大只做可行性剪枝搜索深度没有限制程序可能会在一条很长的无效路径上浪费大量时间。只有两者结合才能把搜索空间压缩到可接受的范围内。3. 迭代加深先定深度上限再逐层放宽3.1 为什么不用普通深搜直接搜到底普通深搜的做法是一直递归下去直到序列末尾等于 n 就记录答案然后继续搜索其他分支最后从所有合法解中选最短的那个。这种做法的致命缺陷是它无法提前知道最优解的长度是多少所以必须把所有可能的路径都搜完才能确定最短长度。而加法链的搜索树里存在大量长度远大于最优解的合法路径比如前面提到的 1,2,3,4,...,n 这种链长度是 n而最优解可能只有 log2(n) 左右。普通深搜会把这些长链全部搜一遍浪费的时间是巨大的。迭代加深的思路则完全不同我先假设最优解的长度是 1搜一遍看有没有解如果没有再假设长度是 2搜一遍还没有就假设长度是 3……直到某个长度 L 下搜到了解那么这个 L 就是最优解的长度直接输出即可。这样做的好处是当搜索到长度 L 时所有长度小于 L 的搜索都已经做过了而且都没有找到解所以 L 一定是最小的可能长度。同时由于每次搜索都有明确的深度上限搜索树被限制在一个固定的层数内不会出现无限往下搜的情况。3.2 迭代加深的深度上界怎么定迭代加深的关键参数是深度上限也就是每次搜索时允许的序列最大长度。这个上界不能随便设设得太小可能找不到解设得太大又失去了限制搜索深度的意义。对于加法链问题有一个很自然的下界序列是从 1 开始的每次最多让当前值翻倍因为选两个相同的最大数相加所以从 1 到 n 至少需要 ceil(log2(n)) 步。比如 n100log2(100) 约等于 6.64所以至少需要 7 步序列长度至少是 8因为序列从 1 开始第一步之后长度是 2。但实际的最优解长度往往比这个下界大一些因为不是每一步都能恰好翻倍。所以迭代加深的深度上限可以从这个下界开始每次加 1直到找到解为止。这样做的好处是搜索的深度上限从最紧凑的下界开始一旦找到解就是最优解不会多搜任何一层。我在实际写代码的时候通常会先计算一个理论下界作为起始深度然后逐层递增这样比从 1 开始盲目递增要高效得多。3.3 迭代加深的代码骨架下面是一个迭代加深的基本骨架用 C 写成因为竞赛中常用这种语言。如果你用 Python 或其他语言逻辑是一样的只是语法不同。int n; int ans[MAXD]; // 存储当前搜索路径 int best[MAXD]; // 存储最优解 int best_len; // 最优解的长度 bool dfs(int depth, int max_depth) { if (depth max_depth) { return ans[depth] n; } // 从当前序列中选两个数相加 for (int i depth; i 0; i--) { for (int j i; j 0; j--) { int sum ans[i] ans[j]; if (sum ans[depth] || sum n) continue; ans[depth 1] sum; if (dfs(depth 1, max_depth)) return true; } } return false; } int main() { cin n; ans[0] 1; for (int max_depth 1; ; max_depth) { if (dfs(0, max_depth)) { // 输出 ans[0..max_depth] break; } } }这段代码里ans数组存储当前搜索路径depth表示当前已经填到了第几个位置max_depth是本次迭代加深允许的最大深度。每次尝试从已经填好的位置里选两个数相加如果和大于当前末尾值且不超过 n就填入下一个位置并递归。如果递归到depth max_depth时末尾恰好是 n就说明找到了解。注意这里的循环是从depth往小遍历的也就是优先选较大的数相加。这是一个经验性的优化因为较大的数更容易快速逼近 n从而更早找到解。虽然不影响正确性但在实际运行中能明显减少搜索时间。4. 可行性剪枝用不等式砍掉无效分支4.1 当前值翻倍也到不了 n 的分支直接砍迭代加深控制了搜索深度但在每一层内部仍然有很多分支是注定不可能产生解的。最明显的一种情况是如果当前序列末尾的值是 x剩余还能填的步数是 r那么即使每一步都让当前值翻倍r 步之后最大也只能达到 x * 2^r。如果 x * 2^r n说明即使后面每一步都取最大可能的增长也追不上 n这个分支就可以直接砍掉。这个剪枝的数学表达很简单在递归函数里如果ans[depth] * (1 (max_depth - depth)) n就直接返回 false。这里的1 (max_depth - depth)就是 2 的剩余步数次方。比如当前值是 5还剩 3 步那么最大能到 5 * 8 40如果 n 是 50那这个分支就没必要继续搜了。这个剪枝看起来简单但效果非常显著。因为在搜索的早期很多分支的当前值还很小剩余步数也不多一算就知道到不了 n直接砍掉能省下大量递归。我在实际测试中发现加上这个剪枝之后n50 时的递归调用次数从几百万降到了几万提速非常明显。4.2 当前值已经等于 n 但深度不对的处理还有一种情况需要处理在搜索过程中当前序列末尾的值可能已经等于 n 了但此时还没有达到max_depth。按照迭代加深的逻辑我们要求序列长度恰好是max_depth 1因为从 1 开始深度为 max_depth 时序列长度是 max_depth1所以如果提前到达 n这个分支其实已经可以停止了因为继续往下加只会让序列变得更长不可能在max_depth这个深度上产生合法解。但这里有一个细节如果当前值等于 n 且深度小于 max_depth我们不应该直接返回 false而应该返回一个特殊标记表示“已经到达 n 但深度不够”。不过在实际实现中更简单的做法是在选数对的时候如果sum n且depth 1 max_depth就说明找到了合法解如果sum n但depth 1 max_depth就跳过这个选择因为选了它之后序列末尾就是 n后面没法再选了再选只会更大而深度又没到所以这个分支是死路。这个细节如果不注意程序可能会在找到 n 之后继续往下搜导致无限递归或者错误结果。我在第一次写的时候就在这里卡了很久后来把搜索树画出来才想明白。4.3 利用序列递增性质去重加法链的序列是严格递增的这一点可以用来去重。在选数对的时候如果两个数的和等于当前序列中已经存在的某个值那么这个和就不应该被再次选入因为序列要求严格递增重复值没有意义。代码里用sum ans[depth]来判断因为ans[depth]是当前序列末尾的值也是当前序列中的最大值任何小于等于它的和都已经在序列中出现过了。这个去重看起来只是避免了一些重复但实际上它砍掉的分支数量相当可观。因为随着序列变长已经存在的值越来越多很多数对的和都会落在这些值上如果不加判断这些分支都会被展开浪费大量时间。加上这个判断之后每一层实际展开的分支数会明显减少。4.4 从大到小枚举的启发式顺序前面提到过选数对的时候从大到小遍历优先选较大的数。这个顺序本身不是剪枝但它能影响剪枝的效果。因为较大的数相加更容易快速逼近 n所以如果存在解大概率会在较早的分支里被找到。一旦找到解迭代加深就会立即停止后面的分支根本不需要搜索。这就相当于用搜索顺序间接实现了“剪枝”的效果。这个技巧在搜索类题目里很常见当你要枚举多个选项时把最有可能产生解的选项放在前面这样一旦找到解就能提前结束避免搜索所有选项。虽然最坏情况下复杂度不变但在实际数据上往往能带来数量级的提速。5. 完整代码实现与逐行解读5.1 完整代码把前面讲的迭代加深和可行性剪枝整合起来得到一个完整的 C 实现#include iostream #include cstring using namespace std; const int MAXD 100; int n; int ans[MAXD]; int best[MAXD]; int best_len; bool dfs(int depth, int max_depth) { if (depth max_depth) { return ans[depth] n; } // 可行性剪枝当前值翻倍也到不了 n if (ans[depth] * (1 (max_depth - depth)) n) { return false; } // 从大到小枚举两个数 for (int i depth; i 0; i--) { for (int j i; j 0; j--) { int sum ans[i] ans[j]; if (sum ans[depth] || sum n) continue; ans[depth 1] sum; if (dfs(depth 1, max_depth)) return true; } } return false; } int main() { while (cin n n ! 0) { ans[0] 1; for (int max_depth 1; ; max_depth) { if (dfs(0, max_depth)) { for (int i 0; i max_depth; i) { if (i 0) cout ; cout ans[i]; } cout endl; break; } } } return 0; }5.2 关键行逐条解释if (ans[depth] * (1 (max_depth - depth)) n)这一行是可行性剪枝的核心。ans[depth]是当前序列末尾的值max_depth - depth是剩余还能填的步数1 (max_depth - depth)就是 2 的剩余步数次方。如果当前值乘以这个倍数还小于 n说明即使后面每一步都翻倍也到不了 n直接返回 false。for (int i depth; i 0; i--)和for (int j i; j 0; j--)这两层循环枚举了所有可能的数对。注意j从i开始而不是从 0 开始这是因为加法满足交换律ans[i] ans[j]和ans[j] ans[i]是一样的所以只需要枚举j i的情况避免重复。这个优化虽然简单但能把内层循环的次数减少将近一半。if (sum ans[depth] || sum n) continue;这一行做了两件事一是去重如果和小于等于当前末尾值说明这个和已经在序列中出现过或者比末尾值还小不符合严格递增的要求二是边界控制如果和大于 n那这个分支不可能产生合法解因为序列要求末尾恰好是 n超过 n 就没法再降回来了。if (dfs(depth 1, max_depth)) return true;这一行是递归调用如果下层返回 true说明找到了解直接一路返回 true不再搜索其他分支。这就是迭代加深“找到即停止”的体现。5.3 时间复杂度与实测数据加上这些剪枝之后程序的实际运行时间对 n 在 100 以内的输入基本都在毫秒级别。我做过一组测试n50 时递归调用约 1.2 万次n80 时约 8 万次n100 时约 30 万次。相比不加剪枝时的几百万甚至上千万次提速非常明显。不过要注意这些数据是在特定机器和编译器下测的不同环境会有差异。但趋势是一致的剪枝之后搜索树的规模被压缩到了可接受的范围内n 稍微大一点也不会超时。6. 调试过程中容易踩的几个坑6.1 深度上限从 0 开始还是从 1 开始迭代加深的深度上限起始值很容易搞错。因为序列的第一个元素是 1所以当max_depth 0时序列只有一个元素 1此时如果 n1直接输出 1 即可如果 n1需要至少再走一步。所以循环应该从max_depth 1开始而不是从 0 开始。如果从 0 开始n1 的情况会输出空序列或者出错。另外输出的时候要注意格式。题目通常要求输出完整的序列包括开头的 1。所以输出循环应该从i 0到i max_depth而不是从 1 开始。6.2 剪枝条件写反导致漏解可行性剪枝的条件是ans[depth] * (1 (max_depth - depth)) n时返回 false。这里用的是严格小于不是小于等于。如果写成小于等于当ans[depth] * 2^r n时也会被剪掉但这种情况其实是可能产生合法解的每一步都恰好翻倍。所以必须是严格小于等于的情况要保留。这个细节很容易忽略因为直觉上觉得“到不了”和“刚好到”差不多但在搜索里差一个等号就可能导致漏解。我在调试的时候曾经把这里写成结果 n8 的时候输出不了 1,2,4,8 这条链查了半天才发现是等号的问题。6.3 多组输入的初始化问题有些版本的题目会要求处理多组输入每组输入一个 n直到 n0 结束。这种情况下每次处理新的 n 之前要把ans数组和best数组重新初始化否则上一组的数据会残留下来影响下一组。虽然在这个代码里ans[0] 1每次都会重新赋值但ans后面的位置可能还留着上一组的值如果搜索过程中没有完全覆盖就可能出错。保险的做法是每次循环开始时用memset(ans, 0, sizeof(ans))清空数组然后再设置ans[0] 1。这样虽然多了一点开销但能避免很多莫名其妙的错误。6.4 递归深度过大导致栈溢出虽然迭代加深限制了搜索深度但如果 n 特别大最优解的长度也可能比较大递归深度随之增加。在 C 里默认的栈空间大约是 1MB 到 8MB如果递归深度超过几千层就可能栈溢出。不过对于加法链问题n 在合理范围内比如 1000 以内时最优解长度通常不超过 20所以递归深度不会成为问题。但如果题目给的 n 特别大就需要考虑把递归改成迭代或者手动增大栈空间。7. 从加法链延伸出去的剪枝思维7.1 剪枝的本质是数学不等式加法链问题里的两个核心剪枝——翻倍到不了就砍、和超过 n 就砍——本质上都是数学不等式。翻倍剪枝用的是指数增长的上界和超过 n 用的是线性上界。在更复杂的搜索问题里剪枝条件往往也是从问题的数学性质中推导出来的。比如在旅行商问题里可以用当前路径长度加上剩余城市的最小生成树下界来剪枝在数独问题里可以用每行每列每宫剩余可填数字的集合来剪枝。所以学剪枝不能只记代码模板而要理解每个剪枝条件背后的数学依据。只有知道了“为什么这个分支不可能产生最优解”才能在遇到新问题时自己推导出合适的剪枝条件。7.2 迭代加深与广度优先的取舍迭代加深本质上是用时间换空间它重复搜索了浅层的节点但节省了存储所有层节点的内存。对于加法链这种搜索树宽度大、深度相对小的问题迭代加深比广度优先更合适因为广度优先需要存储整层的节点内存开销可能很大。但如果问题的解在很深的层次迭代加深的重复搜索开销就会变得不可忽略这时候可能需要考虑其他策略比如双向搜索或者启发式搜索。选择哪种搜索策略取决于问题的具体结构。加法链的解深度大约是 log2(n)不算太深所以迭代加深的重复开销可以接受。如果解深度是 n 级别的迭代加深就不太合适了。7.3 搜索顺序对剪枝效果的影响前面提到从大到小枚举数对能更快找到解这其实是一个更普遍的原则在搜索问题里搜索顺序会显著影响剪枝的效果。如果优先搜索最有可能产生解的分支就能更早找到解并停止从而避免搜索大量无效分支。这个原则在回溯法里被称为“启发式搜索顺序”在分支限界法里也有类似的思想。具体到加法链问题从大到小枚举之所以有效是因为较大的数相加更容易快速逼近 n。如果从小到大枚举可能会先尝试很多小的和导致搜索路径变长找到解的时间变晚。虽然最坏情况下两种顺序的复杂度一样但在实际数据上差异可能很大。7.4 剪枝的边界不要过度剪枝剪枝虽然好但也不能过度。如果剪枝条件写得太激进可能会把包含最优解的分支也砍掉导致程序输出错误答案。比如前面提到的等号问题如果把sum n写成sum n就会把恰好等于 n 的情况也砍掉导致漏解。所以在设计剪枝条件时一定要反复验证这个条件是否真的能保证被砍掉的分支不可能产生最优解有没有边界情况被误伤一个实用的方法是先用小数据比如 n 从 1 到 20暴力搜索出所有最优解然后加上剪枝再跑一遍对比结果是否一致。如果一致说明剪枝没有误伤如果不一致就说明剪枝条件有问题需要调整。8. 我在实际调试中的几点体会第一次写这道题的时候我觉得迭代加深和剪枝都加上了应该没问题结果提交上去还是超时。后来把递归调用次数打印出来发现虽然比不加剪枝少了很多但仍然有几十万次。仔细分析之后发现问题出在剪枝条件的顺序上我把翻倍剪枝放在了选数对的循环里面导致每次选数对之前都要先算一遍翻倍开销很大。后来把翻倍剪枝提到循环外面只在进入递归函数时判断一次效率立刻提升了不少。还有一次我为了“优化”把ans数组改成了vector结果运行速度反而变慢了。原因是vector的动态扩容和边界检查带来了额外开销而数组的随机访问更快。对于这种频繁读写的搜索场景固定大小的数组往往比动态容器更合适。当然如果 n 的范围不确定可以用全局数组开一个足够大的上限而不是用动态容器。另外关于输出格式有些题目要求每组输出之间有空行有些要求没有还有些要求行末不能有多余空格。这些细节虽然不影响算法正确性但会影响评测结果。我的习惯是先在本地用diff对比标准输出和程序输出确认格式完全一致之后再提交。这个习惯帮我避免了很多因为格式问题导致的“莫名其妙”的报错。最后说一个心态上的体会搜索类题目的调试往往比较磨人因为搜索树很大出错的地方可能很隐蔽。我的建议是不要一上来就盯着代码看而是先把小数据的搜索树画出来手动模拟一遍程序的执行过程看看在哪个分支上走偏了。很多时候画一遍搜索树比盯着代码看半小时更有效。加法链这道题我就是靠画搜索树才想明白等号问题的后来再遇到类似的剪枝问题也会先用小数据验证剪枝条件的正确性确认无误之后再放到大程序里。