C++实现A*算法实现九宫重排

九宫重排问题是一种经典的搜索问题，可以使用A*算法来解决。下面是使用C++实现A*算法解决九宫重排问题的代码示例：

#include <iostream>
#include <queue>
#include <vector>
#include <map>
using namespace std;

const int N = 3; // 九宫格大小
const int MAX_STATE = 1e5; // 最大状态数

struct State {
    int a[N][N]; // 九宫格
    int x, y; // 空格位置
    int f, g, h; // f = g + h
    int id; // 状态编号
    bool operator < (const State& rhs) const {
        return f > rhs.f; // 优先队列按 f 值从小到大排序
    }
};

int dx[4] = {-1, 0, 1, 0}; // 方向数组
int dy[4] = {0, 1, 0, -1};

int start[N][N] = { // 初始状态
    {2, 8, 3},
    {1, 6, 4},
    {7, 0, 5}
};
int goal[N][N] = { // 目标状态
    {1, 2, 3},
    {8, 0, 4},
    {7, 6, 5}
};

int get_h(const int a[][N]) { // 估价函数
    int res = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (a[i][j] == 0) continue;
            int x = (a[i][j] - 1) / N;
            int y = (a[i][j] - 1) % N;
            res += abs(x - i) + abs(y - j);
        }
    }
    return res;
}

int state_id; // 状态编号
map<int, int> vis; // 判重数组
State S[MAX_STATE]; // 状态数组

int get_id(const int a[][N]) { // 获取状态编号
    int res = 0, p = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            res += a[i][j] * p;
            p *= 10;
        }
    }
    return res;
}

void print(const State& s) { // 打印状态
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cout << s.a[i][j] << " ";
        }
        cout << endl;
    }
}

bool is_goal(const State& s) { // 判断是否为目标状态
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (s.a[i][j] != goal[i][j]) return false;
        }
    }
    return true;
}

void A_star() { // A*算法
    priority_queue<State> q;
    state_id = 0;
    vis.clear();
    State start_state;
    start_state.x = 1, start_state.y = 2; // 空格位置
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            start_state.a[i][j] = start[i][j];
        }
    }
    start_state.g = 0;
    start_state.h = get_h(start_state.a);
    start_state.f = start_state.g + start_state.h;
    start_state.id = state_id++;
    S[start_state.id] = start_state;
    q.push(start_state);
    vis[get_id(start_state.a)] = start_state.id;
    while (!q.empty()) {
        State t = q.top();
        q.pop();
        if (is_goal(t)) {
            cout << "找到目标状态" << endl;
            print(t);
            return;
        }
        for (int k = 0; k < 4; k++) {
            int nx = t.x + dx[k], ny = t.y + dy[k];
            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            State s = t;
            s.x = nx, s.y = ny;
            swap(s.a[t.x][t.y], s.a[nx][ny]);
            s.h = get_h(s.a);
            s.g = t.g + 1;
            s.f = s.g + s.h;
            int id = get_id(s.a);
            if (vis.count(id) == 0) {
                s.id = state_id++;
                S[s.id] = s;
                q.push(s);
                vis[id] = s.id;
            } else {
                int pre_id = vis[id];
                if (S[pre_id].f > s.f) {
                    S[pre_id] = s;
                    vis[id] = s.id;
                    q.push(s);
                }
            }
        }
    }
}

int main() {
    A_star();
    return 0;
}

A*算法的核心是估价函数，本例中使用的是曼哈顿距离，即当前状态与目标状态每个数码所在位置的曼哈顿距离之和。在代码实现中，使用了优先队列来维护搜索过程中的状态集合，采用了判重和状态编号的方法来优化算法效率。