刷搜索题的人大概率都见过1560这道 DNA sequence。题目一句话概括给你若干条由 A、C、G、T 组成的小片段让你构造一条 DNA 长链使每条小片段都是这条长链的连续子串同时长链要尽可能短。N 非常小但直接暴搜会炸经典解法就是 IDA*也就是迭代加深 A* 搜索。我第一次做这题时很困惑为什么加一个估价函数就能把指数级搜索砍到几十毫秒后来把状态设计和启发式函数一条条拆开才发现这里面的每一步都有讲究。这篇文章就按我的实际调试顺序把题目建模、IDA* 原理、完整实现、容易踩的坑一次讲清楚。1. 题目到底在问什么把一堆 DNA 片段拼成最短序列1.1 输入的是片段不是字符串队列先确认题目形态。输入若干条由 A、C、G、T 组成的小字符串要求找一条最短的 DNA 长链让所有小字符串都出现在这条长链里。注意这里是“出现一次即可”且多个小字符串可以共用一段字符。举一个最直观的例子片段1AAA片段2AAC片段3ACC如果只是把三个串首尾拼接会得到AAAAACACC长度 9。但显然有更短方案AAACC长度 5它同时包含AAA、AAC和ACC。这里的核心操作是“重叠合并”把两个片段的公共后缀和另一个片段的公共前缀压到一起。AAA和AAC重叠两个A得到AAACAAAC再和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最坏答案也可能到 404^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 vectorint pos) { int ret 0; for (int i 0; i n; i) { ret max(ret, len[i] - pos[i]); } return ret; } bool dfs(int depth, vectorint pos) { int h getH(pos); if (depth h limit) return false; if (h 0) return true; vectorvectorint 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; // 生成新状态 vectorint 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]); } vectorint init(n, 0); // 答案长度至少是 maxLen逐层放宽 for (limit maxLen; ; limit) { if (dfs(0, init)) { cout limit \n; break; } } } return 0; }这份代码思路很直白外层不断增大 limit内层 DFS 在 limit 约束下搜索。每次递归都会拷贝一份 vectorN 只有 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 变化的量级不同机器和输入会有差异但趋势很典型limitDFS 访问节点数是否找到解6大概 20 个否7大概 300 个否8大概 5000 个是看到 limit7 到 limit8 节点数爆发式增长会让人担心复杂度不可控。但因为有估价函数剪枝再不济也只是几千到几万节点完全可以在毫秒级跑完。真正可怕的输入是多个片段互相之间几乎没有重叠答案长度接近所有片段长度之和这种数据下搜索量会上涨但仍然远小于纯 DFS。平时训练时如果发现某组数据卡死优先检查估价函数是否太弱再考虑加更紧的下界。5. 从这道题延伸出去IDA* 还能用在哪些地方5.1 判断一道题适不适合 IDA*做完这道 DNA sequence我最大的收获是总结出一套“见到搜索题先判断适不适合 IDA*”的方法。如果一个题目满足三个特征基本可以优先考虑 IDA*第一答案是某个“最短步骤数”或“最短长度”不能直接贪心得到第二搜索深度不会大得离谱一般不超过几十第三能设计一个计算简单、可采纳的估价函数。满足这三点迭代加深 A* 就大概率能打出漂亮的时间。典型例子包括八数码、十五数码、各种推箱子、魔方还原、带约束的最短路覆盖等。这类问题如果用普通 BFS状态数会指数爆炸如果用 A* 加优先队列又要维护巨大的哈希表。IDA* 用“重复搜索浅层”换“极小的空间开销”在内存受限或状态无法全部预处理时特别好用。5.2 启发函数还能怎么往上加这道题最简单的估价函数是 max(len[i] - pos[i])。如果想进一步收紧可以观察更细粒度的约束每个未完成片段剩余部分里的字符顺序。例如多个片段都还没完成它们剩余部分中第一个字符集合不同那么未来几步必须覆盖这些不同的起始字符。这种更紧的 h 函数能进一步剪枝但计算成本也会变高需要自己做取舍。对于 N8 这道题我建议先跑最简版不要过早做复杂优化。许多新手一上来就设计“看起来更聪明”的启发函数结果要么算错、要么计算太慢反而得不偿失。先保证正确再在正确基础上测试优化收益才能知道一个剪枝到底值不值。5.3 关于做题习惯的一些个人体会我现在遇到搜索题会先把迭代加深这个壳子写出来再往里面塞估价函数。壳子固定后只需要替换状态定义和 h 函数就能快速套用到不同题目。这种做法还有个额外好处题目做多了以后估价函数的直觉会越来越准看到状态就能大致猜出 h 怎么设计。对 DNA sequence 这题哪怕几年后再写我还是会选择值传递 pos 数组、从 maxLen 开始递增、同层去重这三个关键点。把这些基本功刻进肌肉记忆比记住某一题的题解更有价值。