先问一个问题给你若干条DNA小片段要求这些片段在一条更长的大序列里按原顺序出现这条大序列最短能有多短我第一次遇见它是在某OJ的搜索练习列表里原题编号HDU 1560社区里一般叫它“DNA sequence”网上不少题解标题却写成HUD1560严重怀疑是当年有人把D和U两个键按反了。题目的数据范围看起来人畜无害最多8条序列每条最长5个字符字母表只有A、C、G、T。我当时心想这不就是全排列合并吗结果朴素DFS交上去样例全过评测机回我一个红色TLE。后来才意识到这题真正想让你练的是IDA*一个迭代加深搜索加启发函数组合起来的经典套路。它不需要BFS那种队列和vis表也不需要精确计算A的open表而是用一个可采纳的下界把指数级搜索树的绝大部分枝桠在长起来之前砍掉。这篇文章把自己从TLE调到AC的整个过程整理出来包括题意细节、启发函数为什么这样设、代码要注意什么适合刚开始学搜索、又想真正理解IDA的同学。1. 题目模型先弄清楚它是子序列不是子串1.1 原题问的是什么某OJ上的原题编号HDU 1560搜索练习列表里通常叫“DNA sequence”。题目描述很简短给n条DNA序列片段字符只有A、C、G、T要求找出一条最短的DNA序列让每条给定片段都能按原顺序出现在这条序列中输出这个最短长度。数据范围是n不超过8每条片段最长不超过5。注意这里的关键词是“按原顺序出现”。如果两条片段是“AC”和“CG”答案是“ACG”长度3“AC”出现在前两个位置“CG”出现在后两个位置。如果两条片段是“A”和“G”答案是“AG”长度2。看起来很简单但它要求的不是“连续出现”而是“子序列式出现”两个字符中间可以插入其他字符。这直接决定了后面搜索状态该怎么维护。我见过不少第一次写这题的人包括我自己都下意识理解成“公共超串”也就是子串要求每个片段完整地、连续地出现在答案串里。于是匹配逻辑写得很重各种前缀匹配、失配跳转最后答案还偏大因为真实数据允许字符之间插入无关字符。1.2 为什么“子序列”这个设定很重要举个DNA字符的具体例子给“AC”和“AG”正确答案是“ACG”长度3。其中“AC”是前两个字符连续“AG”是第1和第3个字符中间隔了一个C作为子序列完全没问题。但如果你按子串理解要求“AC”和“AG”都连续出现最短秒变“ACAG”或者“AGAC”长度4。差别就是这么明显。所以第一道坎不是算法而是模型。只要确认了“子序列”这个设定后面的搜索状态就非常清爽对每个给定串只需要知道它已经匹配到第几个字符记为pos[i]每次在答案串尾部添加一个新字符时若某个串的下一个待匹配字符正好等于它pos[i]就加一否则不动。这里不需要失配清零因为子序列允许中间插入别的东西。顺便说一句这个问题的算法身份两个串的“最短公共超序列”有经典动态规划答案长度等于两串长度之和减最长公共子序列长度但三个及以上串时它就是NP-hard。题目给n8、len5这么小的范围正是为了让搜索在指数级空间里可控。所以这不是一道“考你会不会合并字符串”的题而是一道“考你会不会用搜索下界砍分支”的题。2. 朴素搜索为什么必炸从4^40说起2.1 先算一笔直觉账最直接的想法是枚举答案串。从空串开始每一步在A、C、G、T里选一个字母追加直到所有片段都被覆盖。答案串最长能有多长一个最笨的构造是把8条片段首尾顺序拼起来总长最多8×540。也就是说搜索树最深可能有40层每层4个分支。4^40这个数单纯写出来都能感受到评测机的绝望。即使实际答案通常远小于40朴素DFS也容易在某条“已经匹配了5个字符、但离完成还差很远”的路径上越走越深。有同学会说可以把状态压缩一下答案串不需要真的存下来只需要维护每个串匹配到了第几个字符这就是pos数组。pos数组的组合数是∏(len_i1)用6^8估算约168万个配合哈希表做BFS似乎也可行。这个想法本身不算错但BFS会把整张状态图铺开还要自己写队列判重在题目变成更长序列时立刻顶不住。如果把长度上限从5改成10状态空间立刻变成11^8约2.1亿BFS那套哈希直接内存爆炸。这说明搜索题的边界感很重要范围一变算法选择就变了。HDU 1560把范围卡在n8、len5附近就是为了让IDA*在合理时间内通过。2.2 朴素DFS的问题不只是慢普通DFS的问题不只是慢而是返回时机不可控。你可能会用一个“当前已知可行答案”的全局变量来做最优性剪枝搜索中找到第一个可行解后就记录长度之后只在比它短时继续。但第一次碰到的解往往不是最优解于是你会在若干个局部较优解之间反复横跳深度也降不下来。我自己第一次就是这么写的最后发现搜出来的答案老是偏大而且越改越乱。迭代加深的思路则完全不同我不去猜结果而是把“允许的搜索深度”从下界开始一层层往上试。先假设答案长度是d在这个严格限制下搜索搜不到就放宽到d1再来一次。因为每一步增加一个字符深度就是答案长度所以第一次成功的深度一定是最优解。它牺牲了一些重复搜索的代价换来的是一旦失败就能整棵子树立刻作废的干净利落。这个“先限制、再放宽”的节奏恰好根治了普通DFS里“深陷局部解无法自拔”的问题。2.3 为什么不用A*A需要维护一个带优先级的open表每一步从f值最小的节点扩展空间开销往往是指数级的。而在这种“求最短长度但不需要输出完整路径”的题目里IDA用递归DFS就能跑空间只有O(深度)实现也简单得多。配合一个好的启发函数后IDA的扩展节点数往往非常接近A甚至因为常数小而更快。这是它成为这题标准解法的核心原因。当然如果题目要求输出字典序最小的解你可以在每层按字母顺序尝试并第一次成功就返回如果只是问长度更不用纠结找到就停。3. 启发函数h为什么用最大剩余长度而不是总和3.1 状态与h的精确定义先定义清楚pos[i]记录第i条片段已经匹配了几个字符剩余长度rem[i] len[i] - pos[i]。在当前状态下第i条片段之后还必须依次出现rem[i]个字符这是硬性需求。因此无论后续每一步怎么设计答案串剩下的长度至少要大于等于rem[i]对所有片段取最大得到h max(rem[i])。这就是启发函数。它满足IDA*要求的可采纳性真实还得走的最少步数cost一定不小于h。推理很简单——每个未完成的片段都还有rem[i]个字符等着依次出现这些字符必须分布在后续的某几个不同位置所以总步数至少是rem[i]对所有i成立也就至少是其中的最大值。用符号写就是h(s) ≤ cost(s)。有了这个h每层DFS的剪枝条件就是当前深度dep h limit时说明就算后面每次添加的字符都效果最好也无法在limit步内完成整棵子树直接不搜了。3.2 为什么不能改成sum或平均值这是最容易被新手改错的地方。有人会觉得既然每个串都要完成那下界不应该把所有剩余长度加起来吗答案是否定的。因为一步添加一个字符可以同时推进多个串的进度。比如两条片段都是“A”剩余长度都是1真实只需再走一步加一个A两个串同时完成。如果h取sum会算出2那么在limit2、dep1时剪枝条件122成立把这个明明1步就能完成的解误判成无解从而错过最优答案。所以这里必须用max不能用sum。sum是“每个串各做各的活”时的工位总和而现实中一个字符可以同时服务多个串。用个生活类比几位顾客在同一个窗口办业务厨师炒一道菜如果正好是好几桌都点的那这一道菜就同时满足了好几个等待进度。那最少还要上几道菜取决于剩菜最多的那桌还要几道而不是几桌剩余菜量之和。这个类比能帮助记忆为什么是max。3.3 用数值例子验证一下再回到“AC”和“AG”这个例子。初始时两个串剩余长度都是2h2。真实最优还需要3步也就是构造“ACG”h2确实小于真实值3符合下界要求。假设当前limit2dep0deph2没有超界于是继续搜索尝试两个字母后发现2步确实完成不了说明limit2失败。接着limit加到3再搜一遍找到“ACG”这条路h在终点时为0返回成功。如果错误地把h改成sum初始就是224在limit2时042直接剪掉连尝试的机会都没有就会漏解。这个数值例子也说明启发函数的值不是越大越好而是要保证“不夸大”。一旦夸大最优解就可能被错误剪掉这是搜索算法的致命伤。4. IDA*搜索主循环pos指针数组与代码实现拆解4.1 完整的C核心代码不啰嗦直接给出可提交的框架。下面代码只保留核心搜索部分读入和输出用常规写法即可。#include bits/stdc.h using namespace std; const int MAXN 10; int n, len[MAXN], pos[MAXN]; char s[MAXN][MAXN]; const char gene[4] {A, C, G, T}; int Limit; int get_h() { int mx 0; for (int i 0; i n; i) { mx max(mx, len[i] - pos[i]); } return mx; } bool dfs(int dep) { int h get_h(); if (h 0) return true; // 所有串都已匹配完 if (dep h Limit) return false; // 即使最乐观也超限 for (int k 0; k 4; k) { bool moved false; int tmp[MAXN]; for (int i 0; i n; i) { tmp[i] pos[i]; if (pos[i] len[i] s[i][pos[i]] gene[k]) { pos[i]; moved true; } } if (!moved) continue; // 这个字符没推进任何串忽略 if (dfs(dep 1)) return true; for (int i 0; i n; i) pos[i] tmp[i]; // 回溯 } return false; } int solve() { memset(pos, 0, sizeof(pos)); Limit 0; for (int i 0; i n; i) Limit max(Limit, len[i]); while (!dfs(0)) Limit; return Limit; }4.2 逐行理解dfs在做什么先看dfs开头两行。get_h()算当前剩余最大长度如果h为0说明每个片段的pos都已经等于长度全部完成可以直接返回成功。这里把终态判断放在剪枝之前逻辑上最清晰。然后是核心剪枝dep是已经用掉的字符数h是最少还需要多少字符两者加起来如果超过本轮的limit就说明这条路根本没戏。接着枚举四个字母。内层循环保存tmp[i]并尝试推进pos[i]。注意tmp[i]是在判断之前保存的旧值所以后面回溯时用tmp覆盖pos能完整恢复状态。moved标志记录“这次添加的字符是否至少让一个串前进”。如果这个字符一个串都没推进说明它对当前所有串的子序列匹配没有产生任何实质影响在最短解里可以直接删掉于是continue。这个moved剪枝看似简单其实非常重要。没有它就会产生大量“答案串多了一个无意义的字符状态一点没变深度却加深”的分支。有了它之后每一层都保证至少有一个串的进度前进搜索树被压得小很多。代码里还有一个容易被忽略的点pos数组只会单方向增大不会因为加入无关字符而回退。这正好是子序列模型的天然性质。如果你按子串模型去写加入无关字符时已匹配前缀可能被破坏需要失配回退代码会复杂一个档次。所以前面反复强调“先搞清楚是不是子序列”不只是为了题意更是为了简化实现。4.3 主循环为什么敢从max(len)开始solve里初始Limit取所有片段的长度最大值。为什么不是从0开始因为最长的那个片段本身要作为子序列出现答案串至少得有那么长这是一个天然下界。从0开始当然最终也能搜到但会多做若干轮完整的失败搜索每轮都是一整棵搜索树白费力气。从max(len)开始是最安全的起跑线。每轮dfs(0)先在当前Limit下搜索返回false就Limit重新从0深度开始。因为启发函数是可采纳的不会出现“在Limit小于真实答案时错误返回true”的情况所以第一次返回true的Limit就是答案。这里有一个顺序细节每尝试一个字母如果成功就直接返回true不需要再尝试后面的字母。迭代加深要的是“有没有解、长度多少”不是“字典序最小的解”所以这个提前返回是对的。从复杂度上粗略看每一轮搜索的节点数不会超过所有可能的pos组合数因为pos只增不减再加上moved剪枝实际节点数往往比状态数上限小很多。再加上迭代轮数最多也就是答案长度从max_len到ans之间的差十几轮每轮都是轻量DFS。这也是为什么数据范围开到n8、len5时这个写法跑得非常快。5. 让搜索跑得更快的几个细节与常见误区5.1 moved剪枝的正确性再多说一步有些读者会担心movedfalse的字符真的永远没有用吗考虑一个极端例子当前所有串下一个需要的字符都还不确定提前添加一个无关字符X虽然没推进任何串但万一以后某个串需要X呢注意pos只是“已经匹配到哪”如果某个串之后需要X那么等到它真的进行到需要X的那一步时再添加X也完全来得及现在提前添加X并不会让进度前进分毫。在子序列模型里一个字符的价值只体现在“有没有让某些串的当前指针前进”。提前添加无用的字符既不能节省后续步数反而会占用长度所以它不可能出现在最短解里。这个剪枝在数学上是无损的。我实测过去掉moved剪枝后一组长度5的用例能跑出几百毫秒加上之后降到个位数毫秒。迭代加深最怕的就是“深度增加但状态不变”的无效分支因为每层都会重新分叉指数膨胀得比正常搜索更快。所以这个continue值得写。5.2 记忆化要写在正确的“轮”里如果想把状态判重加上常见写法是用哈希记录状态mask。需要注意两个坑。第一每一轮limit开始时都要清空判重表因为同一个状态在更大的limit下可能从失败变成成功。第二不要简单写“只要访问过就return false”而要记录到达该状态的最小深度minDep。如果当前到达深度minDep说明剩余步数没有上次尝试时多上次都不行这次更不行可以剪如果当前到达深度minDep说明这次剩余步数更多还有翻盘机会要允许继续搜并更新minDep。本题数据量下不加记忆化通常也能过因为IDA*本身已经砍掉大量分支。但把记忆化写成“一个状态只许出现一次”是初学者最容易写出的隐性BUG轻则漏解重则答案偏大。如果只是想稳妥过题先不加也是完全可行的想练通用技巧可以加上并反复测试。5.3 读题和调试中的几个小经验这道题原OJ是一组输入包含多个测试用例先读用例数T再逐组处理。每组是n和n条串。solve()里开头要重置pos和Limit不然上一组的残留数据会污染下一组这是多用例题目最常见的错误来源。我早期写搜索题就栽过好几次数组没清空答案忽大忽小。实际调这道题时还踩过一个坑把Limit初始值设成0然后while循环一层层往上加答案倒是没错但前面几轮会反复把明显不可能的深度搜完白白多了好几次完整失败搜索。后来改成max(len)肉眼可见地快了不少。如果你之后写变体比如n更大、长度更长可以考虑把所有串按长度降序排序再搜索更长的串会更快拉开max值让剪枝条件更早成立。这个优化只影响常数不影响正确性。另外如果题目除了长度还要求输出一个可行答案串可以在dfs里加一个path数组。每次尝试gene[k]时记录path[dep]gene[k]在h0返回true时把path[0..Limit-1]输出即可。回溯时不需要主动清空path因为后面的搜索会覆盖对应位置。最后分享一点个人的训练感受把这道题吃透的价值不在代码本身而在“可采纳启发式”这个思想。我后来遇到好几道搜索题第一反应都是先问自己能不能找到一个不夸大的下界如果能就把普通DFS升级成IDA*如果不能再老老实实想别的办法。对于刚开始学搜索的人来说拿HDU 1560作为理解这个过程的第一道题再合适不过。