您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

HDU 2918 Tobo or not Tobo - IDA* 搜尋解析

編輯：關於C++

題目背景

Tobo 是一個 3×3 的塑膠棋盤，編號 1~9。棋盤上有四個旋鈕（A、B、C、D），每個旋鈕可順/逆時針旋轉 90°，帶動周圍四個格子一起轉動。給定一個經過 X 步打亂的棋盤狀態，要求在不超過 X 步內還原到標準狀態（123456789），求最少步數；若無法在 X 步內完成則輸出 -1。

核心思路：IDA* (Iterative Deepening A*)

狀態表示：用長度 9 的字串或 3×3 陣列存儲當前棋盤。
移動操作：四個旋鈕各有順/逆時針兩種旋轉，共 8 種移動。預先定義好每個旋鈕影響的四個位置索引，旋轉時做循環交換。
啟發函數 h(n)：採用曼哈頓距離的變體。統計有多少數字不在正確位置，因為一次旋轉最多能修正 4 個數字，所以 h = (錯位數 + 3) / 4。這是可接受的（admissible）估價，不會高估實際步數。
剪枝策略：
1. depth + h > limit 直接返回失敗。
2. 避免「逆操作」：若上一步是旋鈕 A 順時針，本步不嘗試 A 逆時針（反之亦然），減少冗餘搜尋。
迭代加深：從 limit = h(initial) 開始，逐層加深直到找到解或超過 X 步。

關鍵代碼片段 (C++)

// 旋鈕影響的四個位置 (0-based 索引)
const int dial[4][4] = {
    {0, 1, 4, 3}, // A
    {1, 2, 5, 4}, // B
    {3, 4, 7, 6}, // C
    {4, 5, 8, 7}  // D
};

// 順時針旋轉
void rotate_cw(int d, string &s) {
    char t = s[dial[d][0]];
    s[dial[d][0]] = s[dial[d][3]];
    s[dial[d][3]] = s[dial[d][2]];
    s[dial[d][2]] = s[dial[d][1]];
    s[dial[d][1]] = t;
}

// 逆時針旋轉
void rotate_ccw(int d, string &s) {
    char t = s[dial[d][0]];
    s[dial[d][0]] = s[dial[d][1]];
    s[dial[d][1]] = s[dial[d][2]];
    s[dial[d][2]] = s[dial[d][3]];
    s[dial[d][3]] = t;
}

// 啟發函數
int heuristic(const string &s) {
    int mis = 0;
    for (int i = 0; i < 9; ++i)
        if (s[i] != '1' + i) ++mis;
    return (mis + 3) / 4;
}

// IDA* 遞歸
bool dfs(int depth, int limit, string &s, int last_dial, int last_dir) {
    int h = heuristic(s);
    if (h == 0) return true;
    if (depth + h > limit) return false;

    for (int d = 0; d < 4; ++d) {
        for (int dir = 0; dir < 2; ++dir) { // 0: cw, 1: ccw
            if (d == last_dial && dir == 1 - last_dir) continue; // 逆操作剪枝
            if (dir == 0) rotate_cw(d, s);
            else rotate_ccw(d, s);
            if (dfs(depth + 1, limit, s, d, dir)) return true;
            // 回溯：做相反旋轉還原
            if (dir == 0) rotate_ccw(d, s);
            else rotate_cw(d, s);
        }
    }
    return false;
}