HDU 1560 DNA Sequence - 最短公共超序列 IDA* 求解

題目大意

給定 k (≤8) 條 DNA 序列 (長度 1~5，字符集 {A,C,G,T})，求最短序列長度，使其包含所有給定序列為子序列。等價於求最短公共超序列 (SCS) 長度。

IDA* 設計

• 狀態：每條序列當前已匹配的前綴長度 pos[i] (0~len[i])。
• 操作：向超序列添加一個字符 {A,C,G,T}。對每條序列，若 pos[i] < len[i] 且 seq[i][pos[i]] == ch，則 pos[i]++。
• 目標：所有 pos[i] == len[i]。
• 啟發函數 h：max_i (len[i] - pos[i]) — 剩餘最長序列長度。因為每步最多推進每條序列 1 位，至少還需該值步。
• 剪枝：depth + h > limit 回溯；若某字符無法推進任何序列（所有序列該位均不匹配），跳過該字符。
• 迭代加深：limit = h(initial) 起始遞增。

核心代碼 (C++)

#include 
using namespace std;

int K, limit;
string seq[8];
int len[8], pos[8];
bool found;

int heuristic() {
    int h = 0;
    for (int i = 0; i < K; ++i)
        h = max(h, len[i] - pos[i]);
    return h;
}

void dfs(int depth) {
    int h = heuristic();
    if (h == 0) { found = true; return; }
    if (depth + h > limit) return;

    // 嘗試四種字符
    for (char ch : {'A','C','G','T'}) {
        bool any = false;
        int backup[8];
        memcpy(backup, pos, sizeof(pos));
        for (int i = 0; i < K; ++i)
            if (pos[i] < len[i] && seq[i][pos[i]] == ch) {
                pos[i]++; any = true;
            }
        if (!any) continue; // 該字符無效，剪枝
        dfs(depth + 1);
        if (found) return;
        memcpy(pos, backup, sizeof(pos)); // 回溯
    }
}

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> K;
        for (int i = 0; i < K; ++i) {
            cin >> seq[i];
            len[i] = seq[i].size();
        }
        memset(pos, 0, sizeof(pos));
        for (limit = heuristic(); ; ++limit) {
            found = false;
            dfs(0);
            if (found) { cout << limit << '\n'; break; }
        }
    }
    return 0;
}

關鍵點

1. 狀態空間極小：每條序列長度 ≤5，k≤8，總狀態數 ≤ 6^8 ≈ 167 萬，IDA* 瞬間解出。
2. 啟發函數 max(剩餘長度) 既簡單又緊湊，是 IDA* 高效的關鍵。
3. 字符順序固定 {A,C,G,T} 保證字典序最小（若題目要求），本題僅需長度。

總結

DNA Sequence 是 SCS 問題的小規模實例，完美展示 IDA* 解決「多序列合併」類問題的威力。狀態表示為各序列進度、操作統一為添加字符、啟發函數取最大剩餘長度，模板極其通用。面試中能寫出此框架，可舉一反三解決「多字符串最短公共超序列」、「多機器人協同規劃」等問題。