UVA 11212：IDA* 求最少區間移動排序次數

UVA 11212 - 移動連續區間使數列遞增：IDA* 搜索

操作：選擇一個連續區間，移動到任意位置。求將排列變為遞增的最少操作數。n ≤ 10（隱含）。

IDA* 框架

• 狀態：當前排列數組
• 啟發函數 h(s)：連續遞增塊數 / 4（經驗常數，保證可接受性）
• 深度限制 lim 從 h(start) 開始遞增，直到搜到解
• DFS 剪枝：depth + h(state) ≥ lim 剪枝

移動操作實現

bool move(int from, int ed, int to, int *s) {
    if (to >= from-1 && to <= ed) return false; // 無效移動
    int tmp[20], nxt[20];
    for (int i=0; i<=n; ++i) tmp[i]=s[i], nxt[i]=i+1;
    nxt[from-1] = ed+1;  // 斷開區間
    nxt[to] = from;      // 插入區間
    nxt[ed] = to+1;
    for (int i=nxt[0], cnt=1; cnt<=n; i=nxt[i], ++cnt) s[cnt] = tmp[i];
    return true;
}

啟發函數

int h(int *s) {
    int cnt = 0;
    for (int i=1; i

關鍵點

狀態空間小（n≤10），IDA* 可行
啟發函數需可接受（h ≤ h*），除以 4 是經驗調參結果
移動操作用鏈表模擬 O(n) 實現
標準 IDA* 遞歸深度優先 + 迭代加深


正確性更強的啟發
理論上 h = ceil(breakpoints / 3) 更準確（每步最多減 3 個斷點），但除以 4 通過測試。實際比賽中可接受性啟發函數常需經驗調整。