用c++ 利用A*算法实现八数码难题(九宫重排)的搜索。

好的，下面是C++代码实现：

#include<iostream>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>

using namespace std;

const int n = 3; // 九宫格大小
const int maxn = 9; // 九宫格中数字个数

// 状态节点类
class StateNode {
public:
    int state[maxn]; // 当前状态
    int empty_pos; // 空格位置
    int g; // 到达当前状态的路径长度
    int h; // 启发式函数估计的距离值

    StateNode() {}
    StateNode(int* s, int e, int g, int h) : empty_pos(e), g(g), h(h) {
        for (int i = 0; i < maxn; i++) {
            state[i] = s[i];
        }
    }

    // 获取空格上方状态
    StateNode get_up_state() {
        int* new_state = new int[maxn];
        for (int i = 0; i < maxn; i++) {
            new_state[i] = state[i];
        }
        swap(new_state[empty_pos], new_state[empty_pos - n]);
        return StateNode(new_state, empty_pos - n, g + 1, manhattan(new_state));
    }

    // 获取空格下方状态
    StateNode get_down_state() {
        int* new_state = new int[maxn];
        for (int i = 0; i < maxn; i++) {
            new_state[i] = state[i];
        }
        swap(new_state[empty_pos], new_state[empty_pos + n]);
        return StateNode(new_state, empty_pos + n, g + 1, manhattan(new_state));
    }

    // 获取空格左侧状态
    StateNode get_left_state() {
        int* new_state = new int[maxn];
        for (int i = 0; i < maxn; i++) {
            new_state[i] = state[i];
        }
        swap(new_state[empty_pos], new_state[empty_pos - 1]);
        return StateNode(new_state, empty_pos - 1, g + 1, manhattan(new_state));
    }

    // 获取空格右侧状态
    StateNode get_right_state() {
        int* new_state = new int[maxn];
        for (int i = 0; i < maxn; i++) {
            new_state[i] = state[i];
        }
        swap(new_state[empty_pos], new_state[empty_pos + 1]);
        return StateNode(new_state, empty_pos + 1, g + 1, manhattan(new_state));
    }

    // 获取所有可行的子状态
    vector<StateNode> get_all_next_states() {
        vector<StateNode> next_states;
        if (empty_pos >= n) {
            next_states.push_back(get_up_state());
        }
        if (empty_pos < maxn - n) {
            next_states.push_back(get_down_state());
        }
        if (empty_pos % n != 0) {
            next_states.push_back(get_left_state());
        }
        if (empty_pos % n != n - 1) {
            next_states.push_back(get_right_state());
        }
        return next_states;
    }

    // 获取曼哈顿距离
    int manhattan(int* s) {
        int distance = 0;
        for (int i = 0; i < maxn; i++) {
            if (s[i] == 0) {
                continue;
            }
            int row = s[i] / n;
            int col = s[i] % n;
            distance += abs(row - i / n) + abs(col - i % n);
        }
        return distance;
    }

    // 重载运算符<，用于优先队列排序
    bool operator < (const StateNode& other) const {
        return g + h > other.g + other.h;
    }

    // 判断是否为目标状态
    bool is_target() {
        for (int i = 0; i < maxn; i++) {
            if (state[i] != i) {
                return false;
            }
        }
        return true;
    }

    // 输出状态
    void output_state() {
        for (int i = 0; i < maxn; i++) {
            cout << state[i] << " ";
            if ((i + 1) % n == 0) {
                cout << endl;
            }
        }
        cout << endl;
    }
};

// A*算法搜索
bool a_star_search(StateNode& start_state) {
    priority_queue<StateNode> q;
    map<int, bool> visited;
    q.push(start_state);
    visited[*start_state.state] = true;
    while (!q.empty()) {
        StateNode node = q.top();
        q.pop();
        if (node.is_target()) {
            node.output_state();
            return true;
        }
        vector<StateNode> next_states = node.get_all_next_states();
        for (int i = 0; i < next_states.size(); i++) {
            int* s = next_states[i].state;
            if (!visited[*s]) {
                q.push(next_states[i]);
                visited[*s] = true;
            }
        }
    }
    return false;
}

int main() {
    int start[maxn] = { 2, 8, 3, 1, 6, 4, 7, 0, 5 }; // 初始状态
    int empty_pos = 7; // 空格位置
    StateNode start_state(start, empty_pos, 0, 0);
    if (!a_star_search(start_state)) {
        cout << "无解" << endl;
    }
    return 0;
}

希望我的代码能够帮到你，如果你有其他问题，可以继续问我哦。