用c++完成步骤一.设计八数码格局的隐式存储的节点结构： 将表示棋局的状态用如下向量表示： A＝(X0，X1 ，X2 ，X3 ，X4 ，X5 ， X6 ， X7 ，X8) 约束条件： XiÎ{0，1 ，2，3，4，5，6，7,8} Xi¹Xj，当i¹j时。 初始状态： S0 ＝（0，1，3，2，4，8，7，6，5） 目标状态： Sg ＝（0，1，2，3，4，5，6，7，8） 步骤二. 采用广度优先、深度优先搜索算法实现搜索。 步骤三. 设计启发函数，启发函数可参考如下定义方法： （1）启发函数h(n)定义为：h(n)=w(n) 其中，w(n)代表n的格局域目标节点格局相比，位置不符的将牌数目。 （2）估计函数f(n)定义为：f(n)＝d(n)＋w(n) 其中，d(n)表示节点深度，w(n)意义与前同。 （3）对w(n)进一步改进：令h(n)=P(n) 其中，p(n)是n格局中每个将牌离家（在sg中的位置）的最短距离。 （4）另一种改进：h(n)=p(n)+3s(n) 其中， s(n)是这样计算的：沿着周围哪些非中心方格上依顺时针方向检查n格局上的每一个将牌，如果其后紧跟着的将牌正好是目标格局中该将牌的后续者，则该将牌得0分，否则得2分；在正中方格上有将牌得1分，否则得0分 步骤四.选择并设计搜索算法。 （1）使用全局择优的树式搜索算法，即启发式的宽度优先搜索算法，但要考虑去掉已生成的格局。 （2）使用局部择优的树式搜索算法，即启发式的深度优先搜索算法，但要考虑去掉已生成的格局。 （3）使用A算法或A*算法，即图的启发式搜索算法，比上述两个算法略有难度。 步骤五 设计输出 动态演示格局的变化情况，即数码的移动情况。 步骤六 编写代码，调试程序。

好的，以下是一个可能的实现：

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

// 八数码状态
struct State {
    vector<int> board; // 棋盘状态
    int depth; // 深度
    int f; // 估价函数值
    int prev; // 前驱节点的索引
    int move; // 空格移动方向（上下左右）
    State(vector<int> b, int d = 0, int p = -1, int m = -1)
        : board(b), depth(d), prev(p), move(m) {}
};

// 判断两个状态是否相同
bool operator==(const State& a, const State& b) {
    return a.board == b.board;
}
// 哈希函数
struct StateHasher {
    size_t operator()(const State& s) const {
        size_t h = 0;
        for (int i = 0; i < 9; i++) {
            h = h * 10 + s.board[i];
        }
        return h;
    }
};

// 初始化状态
State initial_state() {
    vector<int> board = {0, 1, 3, 2, 4, 8, 7, 6, 5};
    return State(board);
}
// 目标状态
vector<int> target_board() {
    return {0, 1, 2, 3, 4, 5, 6, 7, 8};
}

// 判断状态是否为目标状态
bool is_target(const State& s) {
    return s.board == target_board();
}

// 宽度优先搜索
void bfs_search() {
    queue<State> q;
    unordered_set<State, StateHasher> visited; // 记录已访问的状态
    State start_state = initial_state();
    q.push(start_state);
    visited.insert(start_state);
    while (!q.empty()) {
        State cur = q.front(); q.pop();
        if (is_target(cur)) {
            // 输出解路径
            stack<State> path;
            while (cur.prev != -1) {
                path.push(cur);
                cur = q[cur.prev];
            }
            path.push(cur);
            int steps = 0;
            while (!path.empty()) {
                State s = path.top(); path.pop();
                cout << "Step " << steps++ << ": move " << s.move << endl;
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        cout << s.board[i * 3 + j] << " ";
                    }
                    cout << endl;
                }
                cout << endl;
            }
            return;
        }
        // 扩展当前状态
        int zero_pos = find(cur.board.begin(), cur.board.end(), 0) - cur.board.begin();
        int x = zero_pos / 3, y = zero_pos % 3;
        vector<vector<int>> moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int i = 0; i < 4; i++) {
            int new_x = x + moves[i][0], new_y = y + moves[i][1];
            if (new_x >= 0 && new_x < 3 && new_y >= 0 && new_y < 3) {
                int new_pos = new_x * 3 + new_y;
                State new_state = cur;
                swap(new_state.board[zero_pos], new_state.board[new_pos]);
                new_state.depth++;
                new_state.prev = visited.size() - 1;
                new_state.move = i;
                if (visited.find(new_state) == visited.end()) {
                    q.push(new_state);
                    visited.insert(new_state);
                }
            }
        }
    }
    cout << "No solution found." << endl;
}

// 深度优先搜索
void dfs_search() {
    stack<State> q;
    unordered_set<State, StateHasher> visited; // 记录已访问的状态
    State start_state = initial_state();
    q.push(start_state);
    visited.insert(start_state);
    while (!q.empty()) {
        State cur = q.top(); q.pop();
        if (is_target(cur)) {
            // 输出解路径
            stack<State> path;
            while (cur.prev != -1) {
                path.push(cur);
                cur = q[cur.prev];
            }
            path.push(cur);
            int steps = 0;
            while (!path.empty()) {
                State s = path.top(); path.pop();
                cout << "Step " << steps++ << ": move " << s.move << endl;
                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {
                        cout << s.board[i * 3 + j] << " ";
                    }
                    cout << endl;
                }
                cout << endl;
            }
            return;
        }
        // 扩展当前状态
        int zero_pos = find(cur.board.begin(), cur.board.end(), 0) - cur.board.begin();
        int x = zero_pos / 3, y = zero_pos % 3;
        vector<vector<int>> moves = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        for (int i = 0; i < 4; i++) {
            int new_x = x + moves[i][0], new_y = y + moves[i][1];
            if (new_x >= 0 && new_x < 3 && new_y >= 0 && new_y < 3) {
                int new_pos = new_x * 3 + new_y;
                State new_state = cur;
                swap(new_state.board[zero_pos], new_state.board[new_pos]);
                new_state.depth++;
                new_state.prev = visited.size() - 1;
                new_state.move = i;
                if (visited.find(new_state) == visited.end()) {
                    q.push(new_state);
                    visited.insert(new_state);
                }
            }
        }
    }
    cout << "No solution found." << endl;
}

// 启发函数1：计算格局不同的数码数量
int heuristic1(const State& s) {
    int count = 0;
    for (int i = 0; i < 9; i++) {
        if (s.board[i] != target_board()[i]) {
            count++;
        }
    }
    return count;
}

// 启发函数2：计算每个数码到目标位置的曼哈顿距离
int heuristic2(const State& s) {
    int sum = 0;
    for (int i = 0; i < 9; i++) {
        int value = s.board[i];
        if (value != 0) {
            int x1 = i / 3, y1 = i % 3;
            int x2 = (value - 1) / 3, y2 = (value - 1) % 3;
            sum += abs(x1 - x2) + abs(y1 - y2);
        }
    }
    return sum;
}

// 启发函数3：计算每个数码到目标位置的曼哈顿距离，加上每个数码离目标位置最近的其他数码的曼哈顿距离
int heuristic3(const State& s) {
    int sum = 0;
    for (int i = 0; i < 9; i++) {
        int value = s.board[i];
        if (value != 0) {
            int x1 = i / 3, y1 = i % 3;
            int x2 = (value - 1) / 3, y2 = (value - 1) % 3;
            sum += abs(x1 - x2) + abs(y1 - y2);
            // 计算最近的其他数码的曼哈顿距离
            int min_dist = INT_MAX;
            for (int j = 0; j < 9; j++) {
                if (s.board[j] == value) {
                    int x3 = j / 3, y3 = j % 3;
                    int dist = abs(x1 - x3) + abs(y1 - y3);
                    if (dist < min_dist) {
                        min_dist = dist;
                    }
                }
            }
            sum += min_dist;
        }
    }
    return sum;
}

// 启发函数4：计算每个数码到目标位置的曼哈顿距离，加上每个数码后面是否紧跟着目标位置的后继数码（0或2分）
int heuristic4(const State& s) {
    int sum = 0;
    for (int i = 0; i < 9; i++) {
        int value = s.board[i];
        if (value != 0) {
            int x1 = i / 3, y1 = i % 3;
            int x2 = (value - 1) / 3, y2 = (value - 1) % 3;
            sum += abs(x1 - x2) + abs(y1 - y2);
            // 判断后继数码是否在目标位置后面
            if (value < 8 && s.board[i + 1] == value + 1) {
                sum += 0;
            } else {
                sum += 2;
            }
        }
    }
    return sum;
}

// A*算法
void astar_search(int (*he