八数码问题（8-Puzzle Problem）

P1379 八数码难题 - 洛谷

题目概述：在 \(3 \times 3\) 的棋盘上摆放着 \(8\) 个棋子，棋子的编号分别为 \(1\) 到 \(8\)，空格则用 \(0\) 表示。与空格直接相连的棋子可以移至空格中，这样原来棋子的位置就成为空格。现给出一种初始布局，求到达目标布局的最少步数。为简单起见，目标布局总是如下：
123

804

765

本题是一道经典的搜索题，下面将介绍几种常见的搜索算法。以下所有代码均需要 C++11 标准。

朴素 BFS

通过对题目的简单分析，很容易写出朴素的 BFS 代码。进行访问标记时，可以利用哈希的思想，将矩阵转化为整数，再用 std::unordered_set 存储。由于本题的数据范围较小，朴素的 BFS 算法也能通过本题测试，但是效率较低。具体代码如下：

#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];  // hash

        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;  // exit

        ++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);  // expand

                vis.insert(now.to_int());

            }

            now.x = x;

            now.y = y;

            swap(now.maze[x][y], now.maze[tx][ty]);  // backtrack

        }

    }

    return -1;  // unused value

}

int main() {

    int num;

    cin >> num;

    cout << bfs(num) << endl;

    return 0;

}

双向 BFS

对于本题这类已知初始状态和目标状态的题目，可以考虑双向 BFS。在搜索开始前，同时将初始状态和目标状态放进 BFS 队列中。搜索过程中，标记每个状态被访问时的搜索方向以及从对应起点出发的步数。当一种状态被两个方向同时搜到，也就是两个方向相遇时，这两个方向的步数之和就是所求答案。BFS 的性质保证了这一答案一定是最小值。这样的算法称为 Meet in the Middle，通过将实际拓展的层数减半，大大提高了搜索效率，避免了许多不必要的状态拓展。具体代码如下：

#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];  // hash

        return ans;

    }

};

int bfs(int num) {

    queue<Status> q;

    unordered_map<int, pair<int, bool>> vis;

    q.emplace(target);  // target state

    vis[target] = make_pair(0, false);

    q.emplace(num);  // starting state

    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)

            return now.t + vis[now.to_int()].first;  // meet in the middle

        ++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()) || vis[now.to_int()].second != now.d) {

                q.push(now);  // expand

                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]);  // backtrack

        }

    }

    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)\)。容易证明，该函数满足上述条件。具体代码如下：

#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)

                    ans += abs(i - pos_x[maze[i][j]]) + abs(j - pos_y[maze[i][j]]);  // Manhattan distance

        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];  // hash

        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;  // exit

        Status now = pq.top();

        pq.pop();

        ++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[now.x][now.y], now.maze[tx][ty]);

            now.x = tx;

            now.y = ty;

            if (!vis.count(now.to_int())) {

                pq.push(now);  // expand

                vis.insert(now.to_int());

            }

            now.x = x;

            now.y = y;

            swap(now.maze[now.x][now.y], now.maze[tx][ty]);  // backtrack

        }

    }

    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* 部分已经说明，此处不再赘述。具体代码如下：

#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]]);  // Manhattan distance

    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;  // exit

    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;  // very important

        swap(m[x][y], m[tx][ty]);

        if (dfs(tx, ty, t + 1, x, y))

            return true;  // expand

        swap(m[x][y], m[tx][ty]);  // backtrack

    }

    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

巴特西

八数码问题（8-Puzzle Problem）

八数码问题（8-Puzzle Problem）

P1379 八数码难题 - 洛谷

朴素 BFS

双向 BFS

A*

IDA*

最新文章

热门文章