八數碼問題（8-Puzzle Problem）

P1379 八數碼難題 - 洛谷

題目概述：在 \(3 \times 3\) 的棋盤上擺放著 \(8\) 個棋子，棋子的編號分別為 \(1\) 到 \(8\)，空格則用 \(0\) 表示，與空格直接相連的棋子可以移至空格中，這樣原來棋子的位置就成為空格，現給出一種初始布局，求到達目標布局的最少步數，為簡單起見，目標布局總是如下：
123
804
765

本題是一道經典的搜索題，下面將介紹幾種常見的搜索演算法，以下所有代碼均需要 C++11 標準，

樸素 BFS

通過對題目的簡單分析，很容易寫出樸素的 BFS 代碼，進行訪問標記時，可以利用哈希的思想，將矩陣轉化為整數，再用 std::unordered_set 存盤，由于本題的資料范圍較小，樸素的 BFS 演算法也能通過本題測驗，但是效率較低，具體代碼如下：

View Code

#include <bits/stdc++.h>

using namespace std;
const int tar_x = 2, tar_y = 2, target = 123804765;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

struct Status {
    int maze[5][5];  // matrix
    int x, y;        // coordinate of blank space
    int t;           // step number

    explicit Status(int num) {
        memset(maze, 0, sizeof(maze));
        t = 0;
        for (int i = 3; i >= 1; --i) {
            for (int j = 3; j >= 1; --j) {
                maze[i][j] = num % 10;
                num /= 10;
                if (maze[i][j] == 0) x = i, y = j;
            }
        }
    }

    int to_int() const {
        int ans = 0;
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j) ans = ans * 10 + maze[i][j];
        return ans;
    }
};

int bfs(int num) {
    queue<Status> q;
    unordered_set<int> vis;
    q.emplace(num);
    vis.insert(num);
    while (!q.empty()) {
        Status now = q.front();
        q.pop();
        if (now.x == tar_x && now.y == tar_y && now.to_int() == target)
            return now.t;
        ++now.t;
        int x = now.x, y = now.y;
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx < 1 || tx > 3 || ty < 1 || ty > 3) continue;
            swap(now.maze[x][y], now.maze[tx][ty]);
            now.x = tx;
            now.y = ty;
            if (!vis.count(now.to_int())) {
                q.push(now);
                vis.insert(now.to_int());
            }
            now.x = x;
            now.y = y;
            swap(now.maze[x][y], now.maze[tx][ty]);
        }
    }
    return -1;  // unused value
}

int main() {
    int num;
    cin >> num;
    cout << bfs(num) << endl;
    return 0;
}

雙向 BFS

對于本題這類已知初始狀態和目標狀態的題目，可以考慮雙向 BFS，在搜索開始前，同時將初始狀態和目標狀態放進 BFS 佇列中，搜索程序中，標記每個狀態被訪問時的搜索方向以及從對應起點出發的步數，當一種狀態被兩個方向同時搜到，也就是兩個方向相遇時，這兩個方向的步數之和就是所求答案，BFS 的性質保證了這一答案一定是最小值，這樣的演算法稱為 Meet in the Middle，通過將實際拓展的層數減半，大大提高了搜索效率，避免了許多不必要的狀態拓展，具體代碼如下：

View Code

#include <bits/stdc++.h>

using namespace std;
const int target = 123804765;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};

struct Status {
    int maze[5][5];  // matrix
    int x, y;        // coordinate of blank space
    bool d;          // bfs direction (true: forward, false: back)
    int t;           // step number

    explicit Status(int num) {
        memset(maze, 0, sizeof(maze));
        t = 0;
        if (num == target)
            d = false;
        else
            d = true;
        for (int i = 3; i >= 1; --i) {
            for (int j = 3; j >= 1; --j) {
                maze[i][j] = num % 10;
                num /= 10;
                if (maze[i][j] == 0) x = i, y = j;
            }
        }
    }

    int to_int() const {
        int ans = 0;
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j) ans = ans * 10 + maze[i][j];
        return ans;
    }
};

int bfs(int num) {
    queue<Status> q;
    unordered_map<int, pair<int, bool>> vis;
    q.emplace(target);
    vis[target] = make_pair(0, false);
    q.emplace(num);
    vis[num] = make_pair(0, true);
    while (!q.empty()) {
        Status now = q.front();
        q.pop();
        if (vis.count(now.to_int()) && vis[now.to_int()].second != now.d)  // meet in the middle
            return now.t + vis[now.to_int()].first;
        ++now.t;
        int x = now.x, y = now.y;
        for (int i = 0; i < 4; ++i) {
            int tx = x + dx[i], ty = y + dy[i];
            if (tx < 1 || tx > 3 || ty < 1 || ty > 3) continue;
            swap(now.maze[x][y], now.maze[tx][ty]);
            now.x = tx;
            now.y = ty;
            swap(now.y, ty);
            if (!vis.count(now.to_int()) || vis[now.to_int()].second != now.d) {
                q.push(now);
                vis[now.to_int()] = make_pair(now.t, now.d);
            }
            now.x = x;
            now.y = y;
            swap(now.maze[now.x][now.y], now.maze[tx][ty]);
        }
    }
    return -1;  // unused value
}

int main() {
    int num;
    cin >> num;
    cout << bfs(num) << endl;
    return 0;
}

A*

A* 演算法是一種啟發式搜索，即利用估值函式進行剪枝，以避免盲目搜索中許多不必要的狀態拓展，A* 演算法以 BFS 為基礎，用優先佇列代替 BFS 佇列，以估值函式為優先級，A* 演算法中，每個狀態的估值函式由兩部分組成，即 \(f(x)=g(x)+h(x)\)，其中 \(g(x)\) 是已經走過的步數，\(h(x)\) 是預估到達終點至少還要走的步數，兩者之和 \(f(x)\) 即這一狀態的估值函式，因此，為確保演算法正確，\(h(x)\) 的值一定不大于實際距離終點的步數，即 \(f(x)\) 的值一定不大于實際總步數，本題中，可以使用每個棋子到目標位置的曼哈頓距離作為其 \(h(x)\)，容易證明，該函式滿足上述條件，具體代碼如下：

View Code

#include <bits/stdc++.h>

using namespace std;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const int pos_x[] = {2, 1, 1, 1, 2, 3, 3, 3, 2};
const int pos_y[] = {2, 1, 2, 3, 3, 3, 2, 1, 1};

struct Status {
    int maze[5][5];  // matrix
    int x, y;        // coordinate of blank space
    int t;           // step number

    explicit Status(int num) {
        memset(maze, 0, sizeof(maze));
        t = 0;
        for (int i = 3; i >= 1; --i) {
            for (int j = 3; j >= 1; --j) {
                maze[i][j] = num % 10;
                num /= 10;
                if (maze[i][j] == 0) x = i, y = j;
            }
        }
    }

    int h() const {
        int ans = 0;
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j)
                if (maze[i][j] != 0 &&
                    (i != pos_x[maze[i][j]] || j != pos_y[maze[i][j]]))
                    ++ans;
        return ans;
    }

    int to_int() const {
        int ans = 0;
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j) ans = ans * 10 + maze[i][j];
        return ans;
    }

    bool operator<(const Status& other) const {
        return h() + t > other.h() + other.t;  // compare by f(x)
    }
};

int a_star(int num) {
    priority_queue<Status, vector<Status>> pq;
    set<int> vis;
    pq.push(Status(num));
    vis.insert(num);
    while (!pq.empty()) {
        if (pq.top().h() == 0) return pq.top().t;
        Status now = pq.top();
        pq.pop();
        ++now.t;
        for (int i = 0; i < 4; ++i) {
            int tx = now.x + dx[i], ty = now.y + dy[i];
            if (tx < 1 || tx > 3 || ty < 1 || ty > 3) continue;
            swap(now.maze[now.x][now.y], now.maze[tx][ty]);
            swap(now.x, tx);
            swap(now.y, ty);
            if (!vis.count(now.to_int())) {
                pq.push(now);
                vis.insert(now.to_int());
            }
            swap(now.x, tx);
            swap(now.y, ty);
            swap(now.maze[now.x][now.y], now.maze[tx][ty]);
        }
    }
    return -1;  // unused value
}

int main() {
    int num;
    cin >> num;
    cout << a_star(num) << endl;
    return 0;
}

IDA*

IDA* 就是基于迭代加深搜索的 A* 演算法，所謂迭代加深，就是在 DFS 的基礎上控制其搜索深度，一旦超過深度限制就停止搜索，若當前深度無法得到答案，則再增加深度限制，迭代加深搜索結合了 DFS 與 BFS 的優點，不需要占用大量空間，支持回溯，同時可以快速找到最優解，避免剪枝不充分而造成的大量無用搜素，并且不需要判重，此外，由于迭代加深演算法基于 DFS，相對于 BFS 而言，其實作難度更低，代碼量更少，IDA* 則是在迭代加深搜素的基礎上加上了估值函式的剪枝，有關估值函式的內容，在 A* 部分已經說明，此處不再贅述，具體代碼如下：

View Code

#include <bits/stdc++.h>

using namespace std;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
const int pos_x[] = {2, 1, 1, 1, 2, 3, 3, 3, 2};
const int pos_y[] = {2, 1, 2, 3, 3, 3, 2, 1, 1};
int lim;  // depth limit
int m[5][5];

int h() {
    int ans = 0;
    for (int i = 1; i <= 3; ++i)
        for (int j = 1; j <= 3; ++j)
            if (m[i][j] != 0)
                ans += abs(i - pos_x[m[i][j]]) + abs(j - pos_y[m[i][j]]);
    return ans;
}

bool dfs(int x, int y, int t, int lx, int ly) {
    int dis = h();
    if (t + dis > lim) return false;  // prune with f(x)
    if (dis == 0) return true;
    for (int i = 0; i < 4; ++i) {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx < 1 || tx > 3 || ty < 1 || ty > 3) continue;
        if (tx == lx && ty == ly) continue;
        swap(m[x][y], m[tx][ty]);
        if (dfs(tx, ty, t + 1, x, y)) return true;
        swap(m[x][y], m[tx][ty]);
    }
    return false;
}

int main() {
    int num;
    cin >> num;
    int sx, sy;
    for (int i = 3; i >= 1; --i) {
        for (int j = 3; j >= 1; --j) {
            m[i][j] = num % 10;
            num /= 10;
            if (m[i][j] == 0) sx = i, sy = j;
        }
    }
    lim = 0;
    while (!dfs(sx, sy, 0, -1, -1)) ++lim;  // IDA*
    cout << lim << endl;
    return 0;
}

轉載請注明出處，原文地址：https://www.cnblogs.com/na-sr/p/8-puzzle.html

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/418106.html

標籤：其他

上一篇：Deno 1.18 環境使用 WebGPU

下一篇：演算法競賽——多源BFS