IDA*算法详解：从DNA Sequence看迭代加深与启发式剪枝

刷搜索题的人大概率都见过1560这道 DNA sequence。题目一句话概括：给你若干条由 A、C、G、T 组成的小片段，让你构造一条 DNA 长链，使每条小片段都是这条长链的连续子串，同时长链要尽可能短。N 非常小，但直接暴搜会炸，经典解法就是 IDA*，也就是迭代加深 A* 搜索。我第一次做这题时很困惑，为什么加一个估价函数就能把指数级搜索砍到几十毫秒；后来把状态设计和启发式函数一条条拆开，才发现这里面的每一步都有讲究。这篇文章就按我的实际调试顺序，把题目建模、IDA* 原理、完整实现、容易踩的坑一次讲清楚。

1. 题目到底在问什么：把一堆 DNA 片段拼成最短序列

1.1 输入的是片段，不是字符串队列

先确认题目形态。输入若干条由 A、C、G、T 组成的小字符串，要求找一条最短的 DNA 长链，让所有小字符串都出现在这条长链里。注意这里是“出现一次即可”，且多个小字符串可以共用一段字符。举一个最直观的例子：

• 片段1：AAA
• 片段2：AAC
• 片段3：ACC

如果只是把三个串首尾拼接，会得到AAAAACACC，长度 9。但显然有更短方案：AAACC，长度 5，它同时包含AAA、AAC和ACC。这里的核心操作是“重叠合并”：把两个片段的公共后缀和另一个片段的公共前缀压到一起。AAA和AAC重叠两个A，得到AAAC；AAAC再和ACC重叠一个C，就能变成AAACC。

这种重叠关系看起来像一道贪心题：每次找重叠长度最大的两个片段拼在一起，重复直到变成一个串。但贪心在这里并不安全。你当前选中的最长重叠，可能把某个关键片段卡死在后续拼接里，导致最后答案反而更长。这种“子串覆盖”问题本质上是最短公共超串问题，属于组合优化里很难处理的一类。题目故意把 N 控制得很小，就是为了让你用搜索硬解。

1.2 为什么贪心和普通 BFS 都不好使

先看贪心反例。片段AB、BC、CA三个片段两两之间重叠长度都是 1。如果第一步贪心合并AB和BC，得到ABC，再和CA合并时只能做到ABCA或CABC，长度 4。但如果你先合并CA和AB，得到CAB，再合并BC会变成CABC，同样是 4。这里看不出问题，换一组更极端的：ABC、BCD、CDE、DEA，最长重叠贪心可能做出ABCDE长度 5，但某些顺序会得到更长的结果。问题在于“最长重叠优先”只能保证局部最优，不是全局最优。

再看普通 BFS。搜索树的每个节点是一段已构造的 DNA 序列，分支是添加 A/C/G/T 四个字符，深度就是要找的答案长度。如果答案长度是 L，状态数量可能高达 4 的 L 次方，哪怕 N 是 8、每条长度只有 5，最坏答案也可能到 40，4^40 这个量级完全跑不动。DFS 空间小，但方向不对时会一头扎进无限长的分支里，根本停不下来。正是因为“深度未知 + 状态巨大”，才需要把“迭代加深”和“启发式剪枝”结合起来，这就是 IDA*。

2. IDA* 的核心思路：一层一层试探，用估价函数提前掉头

2.1 迭代加深：每层重爬，但空间省到极致

迭代加深的思路很像爬楼梯：先假设答案只有 3 层，我从第 0 层开始用 DFS 往下钻，只允许深度到 3，搜不到答案就回来；然后把限制改成 4，再搜一遍；改成 5，再搜一遍。因为每次都在“当前认为合理的深度上限”内做深度优先搜索，所以内存占用只有一条路径的深度，而不是像 BFS 那样把整层节点都存下来。

第一次听这个方案的人都会觉得重复劳动太多了：limit 从 4 变成 5，前面深度 4 的子树不是全部重新算了一遍吗？确实会重复。但迭代加深的核心优势在于，DFS 的深层分支往往占搜索总量的大头，浅层重复的成本相对小。再加上剪枝，很多分支在浅层就被砍掉，实际重复代价没有想象中高。对这个问题来说，状态量巨大而答案深度相对有限，迭代加深是比 BFS 现实得多的选择。

2.2 加持 A* 估价函数：还没到深层就知道这里不可能

光有迭代加深还不够，DFS 可能还是要在 limit 边界上试很多无效分支。IDA* 的“A*”部分就是在每个节点引入一个启发式估价函数 h，用它来估计“从这个状态到目标至少还需要多少步”。搜索时只要满足：

当前已经走的步数 depth + 估价函数 h >= limit

就立刻剪枝。因为 h 永远不大于真实剩余步数，一旦这个不等式成立，说明即使后面每一步都走对了，也无法在 limit 步内到达目标，所以当前分支没有继续的必要。这样就能把大量“看似能到但实际到不了”的分支提前砍掉。

这里的关键是 h 必须“可采纳”，也就是它只能低估或恰好等于真实代价，不能高估。高估的 h 会剪掉可能包含最优解的分支，导致结果错误。可采纳性加上迭代加深按 limit 递增搜索，就可以保证第一次搜索成功时得到的答案一定是最短的。

2.3 这题的估价函数：取每条片段剩余后缀的最大长度

设计一个又准又便宜的启发函数，是 IDA* 的精髓。对这道 DNA sequence 题，我定义状态为一个数组 pos[i]，表示第 i 个片段在当前已构造的 DNA 长链里已经匹配到了哪个位置。pos[i] 等于 len[i] 说明这个片段已经完全被覆盖。

从这个状态出发，第 i 个片段至少还需要 len[i] - pos[i] 个字符，才能把剩余后缀全部出现在最终长链中。所有片段同时都要被覆盖，所以总剩余步数的下界至少是这些剩余长度里的最大值：

h = max( len[i] - pos[i] for i in [0, n-1] )

为什么是最大值而不是求和？因为后续添加的字符可以同时推进多个片段的匹配。例如两个片段分别是AC和CT，当前 pos 都是 0，剩余长度都是 2。如果求总和，会认为至少需要 4 个字符；但实际构造ACT只需要 3 个字符就能覆盖两条片段。所以更紧的下界是“所有片段剩余长度里最大的那个”，它代表了最拖后腿的那条片段。这个函数计算成本是 O(N)，N 最大也就 8，几乎可以忽略不计，而且剪枝效果非常好。

3. 代码实现：IDDFS + 启发剪枝完整拆解

3.1 状态表示与 limit 初值

代码里我用一个 vector 数组 pos 表示当前匹配进度。例如 pos = {0, 2, 1} 表示第 0 条片段一个字符还没匹配，第 1 条片段已经匹配到下标 2，第 2 条片段匹配到下标 1。搜索深度 depth 表示当前长链的长度，也就是已经在末尾添加了多少个字符。

limit 的初值不是 0，而是所有片段长度的最大值。理由很简单：最终答案至少要能把最长那条片段完整放进去，所以答案长度不可能小于最长片段长度。从 maxLen 开始，每次搜索失败就让 limit 加 1，直到成功。这样能跳过大量浅层无效搜索。有些写法喜欢从更紧的下界开始，比如最长片段长度与某些重叠下界取最大值，但对这题的数据规模，从 maxLen 开始就够了。

3.2 DFS 主体：四字符枚举 + 推进剪枝 + 同层去重

进入 dfs(depth, pos) 后，第一步就算 h。如果 depth + h > limit，直接 return false。如果 h == 0，说明所有片段都匹配完了，return true。

接下来枚举四个字符 A、C、G、T，尝试把它们拼到当前长链末尾。这里有一个非常关键的剪枝：只有当前字符能让至少一个片段的匹配位置前进时，才值得递归。如果没有任何一个片段的下一个字符等于这个字符，那么添加它只会白白增加长度，不可能让状态朝目标靠近，整棵分支都没有存在价值。

确定要尝试字符 c 之后，生成新状态 nxt。对每条片段，如果它还没匹配完，并且它的第 pos[i] 个字符正好等于 c，就把 nxt[i] 加 1。已经匹配完的片段保持不动，因为后续字符不会影响“已经被包含”的事实。

还有一个容易被忽视的优化叫“同层状态去重”。不同字符可能产生完全相同的 nxt 状态。比如两条片段AAA和AA，在初始状态添加一个A，两条片段的 pos 都会前进，产生某个 nxt；如果同一个深度之前已经有另一个字符导致这个完全相同的 nxt 被搜过，那当前分支就没有必要再搜了，因为后续所有可走的路径都一样。我维护一个 seen 列表，枚举字符时如果发现新状态已经出现过，就直接跳过。

3.3 完整 C++ 代码

下面是一份可以直接提交的 C++ 实现，关键注释都写在代码里。

#include <bits/stdc++.h> using namespace std; const int MAXN = 10; int n, limit; // 片段数量，当前迭代加深深度上限 string s[MAXN]; // 原始片段 int len[MAXN]; // 每个片段的长度 char gene[4] = {'A', 'C', 'G', 'T'}; // 估价函数：所有片段剩余长度的最大值 int getH(const vector<int>& pos) { int ret = 0; for (int i = 0; i < n; i++) { ret = max(ret, len[i] - pos[i]); } return ret; } bool dfs(int depth, vector<int> pos) { int h = getH(pos); if (depth + h > limit) return false; if (h == 0) return true; vector<vector<int>> seen; // 当前深度的同层去重表 for (int ci = 0; ci < 4; ci++) { char c = gene[ci]; // 推进剪枝：必须至少有一个片段因为这个字符而前进 bool canAdvance = false; for (int i = 0; i < n; i++) { if (pos[i] < len[i] && s[i][pos[i]] == c) { canAdvance = true; break; } } if (!canAdvance) continue; // 生成新状态 vector<int> nxt = pos; for (int i = 0; i < n; i++) { if (nxt[i] < len[i] && s[i][nxt[i]] == c) { nxt[i]++; } } // 同层状态去重 bool duplicate = false; for (const auto& st : seen) { if (st == nxt) { duplicate = true; break; } } if (duplicate) continue; seen.push_back(nxt); if (dfs(depth + 1, nxt)) return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { cin >> n; int maxLen = 0; for (int i = 0; i < n; i++) { cin >> s[i]; len[i] = (int)s[i].size(); maxLen = max(maxLen, len[i]); } vector<int> init(n, 0); // 答案长度至少是 maxLen，逐层放宽 for (limit = maxLen; ; limit++) { if (dfs(0, init)) { cout << limit << '\n'; break; } } } return 0; }

这份代码思路很直白：外层不断增大 limit，内层 DFS 在 limit 约束下搜索。每次递归都会拷贝一份 vector，N 只有 8，所以拷贝成本很低。如果 N 再大一点，可以改成引用传递加回溯还原，不过对这道题完全没必要。

3.4 时间与空间复杂度分析

严格分析 IDA* 的复杂度比较困难，因为搜索树的剪枝规模高度依赖输入数据。但我们可以做个直观估算：搜索深度上限是最终的答案长度 L，每个节点最多 4 个分支，经过“推进剪枝”后有效分支数通常远小于 4。每个有效分支内部要遍历 N 个片段生成新状态，所以单个节点开销是 O(N log N?) 不，具体是 O(N * 4) 左右。估价函数 getH 是 O(N)，整体在每层搜索中大约访问 M 个节点，那么单次 limit 搜索的开销是 O(M * N)。迭代加深会让 limit = maxLen 到 L 之间的每一层都重新跑一遍，相当于乘以一个系数 (L - maxLen + 1)，但因为浅层节点数量远小于深层，这个系数通常不是主导。

空间复杂度非常友好。DFS 递归深度最多 L，每层存储一个 pos 数组，所以空间是 O(L * N)。这里没有用到任何 BFS 式的 Open 表，也没有记录全局访问过的所有状态，这是迭代加深相比普通 A* 的最大优势。内存占用小，自然也就没有哈希碰撞和状态爆炸的烦恼。

4. 写代码时最容易踩的坑：调试实录与排查技巧

4.1 limit 初值、估价函数传参、状态污染

先说最基础的问题。limit 如果从 0 开始递增，也不是不行，但会浪费很多时间在明显不可能的短深度上。因为答案至少是 maxLen，从 maxLen 起步是零成本的优化。还有人把估价函数写成所有片段剩余长度之和，结果剪枝过度，正确解被剪没了，程序输出一个偏大的答案，甚至直接死循环找不到解。这类问题很好排查：把 getH 临时改成 0，也就是退化成纯迭代加深 DFS，如果这时能出正确答案，就说明 h 函数设计有误。

另一个很隐蔽的坑是状态污染。如果 dfs 的参数 pos 传引用，并且在递归前修改了 pos、递归后没有还原，那么同一层的后续字符会读到被污染过的状态，产生完全错误的搜索树。我自己的习惯是直接值传递 vector，简单又安全。只有当 N 很大、拷贝成为瓶颈时，才会手动回溯。

4.2 同层去重为什么能救回来一整个超时分支

同层去重在数据比较随机的时候表现不明显，一旦碰到多个片段高度重复，作用会非常大。比如输入全是AAAAAAAA这种只有一种字符的片段，枚举 A 产生的状态和枚举后续字符产生的状态经常一样。如果不做去重，同一个等价状态可能被反复搜四遍，时间直接翻四倍。更糟的是，这种重复会沿着整棵搜索树一路传染，导致超时。

判断是否需要去重的标准很简单：看“不同动作是否可能收敛到同一个匹配进度数组”。在这道题里，不同字符可以让多条片段前进，前进后可能得到完全相同的 pos 数组，所以去重是有效的。不过要注意，seen 必须是当前 dfs 函数内部的局部变量，不能是全局的，因为不同深度、不同路径下即使 pos 一样，剩余限制也不同，不能混用。

4.3 实测表现：limit 增加时搜索量大概长什么样

我用一组随机生成的数据跑了一下，记录不同 limit 下的 DFS 访问节点数。输入是五条长度 4 到 6 的随机片段，最终答案长度是 8。下面是节点数随 limit 变化的量级，不同机器和输入会有差异，但趋势很典型：

看到 limit=7 到 limit=8 节点数爆发式增长，会让人担心复杂度不可控。但因为有估价函数剪枝，再不济也只是几千到几万节点，完全可以在毫秒级跑完。真正可怕的输入是多个片段互相之间几乎没有重叠，答案长度接近所有片段长度之和，这种数据下搜索量会上涨，但仍然远小于纯 DFS。平时训练时如果发现某组数据卡死，优先检查估价函数是否太弱，再考虑加更紧的下界。

5. 从这道题延伸出去：IDA* 还能用在哪些地方

5.1 判断一道题适不适合 IDA*

做完这道 DNA sequence，我最大的收获是总结出一套“见到搜索题先判断适不适合 IDA*”的方法。如果一个题目满足三个特征，基本可以优先考虑 IDA*：第一，答案是某个“最短步骤数”或“最短长度”，不能直接贪心得到；第二，搜索深度不会大得离谱，一般不超过几十；第三，能设计一个计算简单、可采纳的估价函数。满足这三点，迭代加深 A* 就大概率能打出漂亮的时间。

典型例子包括八数码、十五数码、各种推箱子、魔方还原、带约束的最短路覆盖等。这类问题如果用普通 BFS，状态数会指数爆炸；如果用 A* 加优先队列，又要维护巨大的哈希表。IDA* 用“重复搜索浅层”换“极小的空间开销”，在内存受限或状态无法全部预处理时特别好用。

5.2 启发函数还能怎么往上加

这道题最简单的估价函数是 max(len[i] - pos[i])。如果想进一步收紧，可以观察更细粒度的约束：每个未完成片段剩余部分里的字符顺序。例如多个片段都还没完成，它们剩余部分中第一个字符集合不同，那么未来几步必须覆盖这些不同的起始字符。这种更紧的 h 函数能进一步剪枝，但计算成本也会变高，需要自己做取舍。

对于 N=8 这道题，我建议先跑最简版，不要过早做复杂优化。许多新手一上来就设计“看起来更聪明”的启发函数，结果要么算错、要么计算太慢，反而得不偿失。先保证正确，再在正确基础上测试优化收益，才能知道一个剪枝到底值不值。

5.3 关于做题习惯的一些个人体会

我现在遇到搜索题，会先把迭代加深这个壳子写出来，再往里面塞估价函数。壳子固定后，只需要替换状态定义和 h 函数，就能快速套用到不同题目。这种做法还有个额外好处：题目做多了以后，估价函数的直觉会越来越准，看到状态就能大致猜出 h 怎么设计。对 DNA sequence 这题，哪怕几年后再写，我还是会选择值传递 pos 数组、从 maxLen 开始递增、同层去重这三个关键点。把这些基本功刻进肌肉记忆，比记住某一题的题解更有价值。