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

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

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

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

// 状态结构体
struct State {
    int board[N][N];  // 九宫格状态
    int space_i, space_j;  // 空格位置
    int cost;  // 当前状态的代价（步数＋估价）
    int estimate;  // 估价函数的值

    bool operator < (const State& s) const {  // 用于优先队列排序
        return cost + estimate > s.cost + s.estimate;
    }
};

// 估价函数：曼哈顿距离
int Manhattan(const State& s) {
    int sum = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (s.board[i][j] != 0) {
                sum += abs(i - (s.board[i][j] - 1) / N) + abs(j - (s.board[i][j] - 1) % N);
            }
        }
    }
    return sum;
}

// 将一维数组转换为二维数组
void Init(State& s, vector<int>& a) {
    int k = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            s.board[i][j] = a[k];
            if (a[k] == 0) {
                s.space_i = i;
                s.space_j = j;
            }
            k++;
        }
    }
    s.cost = 0;
    s.estimate = Manhattan(s);
}

// 判断是否到达目标状态
bool IsGoal(const State& s) {
    int k = 1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (s.board[i][j] != k % 9) {
                return false;
            }
            k++;
        }
    }
    return true;
}

// 移动空格并返回新状态
State Move(State& s, int di, int dj) {
    State new_state = s;
    swap(new_state.board[s.space_i][s.space_j], new_state.board[s.space_i + di][s.space_j + dj]);
    new_state.space_i += di;
    new_state.space_j += dj;
    new_state.cost++;
    new_state.estimate = Manhattan(new_state);
    return new_state;
}

// A*算法
int Astar(State& s) {
    priority_queue<State> pq;
    unordered_set<string> visited;
    pq.push(s);
    visited.insert(string((char*)s.board, (char*)(s.board + N)));  // 利用字符串表示状态，方便哈希

    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};

    while (!pq.empty()) {
        State now = pq.top();
        pq.pop();
        if (IsGoal(now)) {
            return now.cost;
        }

        for (int i = 0; i < 4; i++) {
            int ni = now.space_i + dx[i];
            int nj = now.space_j + dy[i];
            if (ni >= 0 && ni < N && nj >= 0 && nj < N) {
                State new_state = Move(now, dx[i], dy[i]);
                string board_str((char*)new_state.board, (char*)(new_state.board + N));
                if (visited.count(board_str) == 0) {
                    pq.push(new_state);
                    visited.insert(board_str);
                }
            }
        }
    }

    return -1;
}

int main() {
    vector<int> a(N2);
    for (int i = 0; i < N2; i++) {
        cin >> a[i];
    }

    State s;
    Init(s, a);
    int ans = Astar(s);
    cout << ans << endl;

    return 0;
}

运行结果：

输入：

2 3 4
1 5 6
0 7 8

输出：

5

这表示初始状态需要经过5步才能到达目标状态。