C++实现：综合使用A*算法，广度优先算法和深度优先算法实现九宫重排

好的，下面我将为你提供C++实现。首先，我们需要定义一个节点类，用来保存每个状态的信息和路径：

class Node {
public:
    string state; // 当前状态
    int depth; // 路径长度
    string path; // 路径
    Node(string state, int depth, string path) : state(state), depth(depth), path(path) {}
};

接下来，我们分别实现A*算法，广度优先算法和深度优先算法。

1. A*算法

string astar(string start, string end) {
    unordered_map<string, int> depth; // 用于记录状态的深度
    unordered_map<string, string> path; // 用于记录状态的路径
    priority_queue<pair<int, Node*>, vector<pair<int, Node*>>, greater<pair<int, Node*>>> pq; // 用于存储待扩展节点
    pq.push({manhattan(start, end), new Node(start, 0, "")}); // 将初始状态加入到pq中
    depth[start] = 0; // 初始状态的深度为0
    while (!pq.empty()) {
        auto cur = pq.top().second; // 取出f值最小的节点
        pq.pop();
        if (cur->state == end) return cur->path; // 找到目标状态，返回路径
        if (depth[cur->state] < cur->depth) continue; // 已经扩展过的状态不再扩展
        for (auto next : get_next_states(cur->state)) { // 扩展当前节点
            int d = cur->depth + 1; // 子节点的深度为父节点的深度加1
            if (!depth.count(next) || d < depth[next]) { // 如果子节点未被扩展或者新路径更优
                depth[next] = d; // 记录子节点的深度
                path[next] = cur->path + direction(next, cur->state); // 记录子节点的路径
                pq.push({d + manhattan(next, end), new Node(next, d, path[next])}); // 将子节点加入pq中
            }
        }
    }
    return ""; // 没有找到目标状态，返回空路径
}

在上面的代码中，我们使用了一个优先队列pq来存储待扩展的节点，其中节点的优先级为f值（即深度加上曼哈顿距离）。对于每个被扩展的节点，我们都生成它的所有合法子节点，并计算它们的f值。如果子节点未被扩展或者新路径更优，就将子节点加入到pq中。

2. 广度优先算法

string bfs(string start, string end) {
    unordered_map<string, int> depth; // 用于记录状态的深度
    unordered_map<string, string> path; // 用于记录状态的路径
    queue<Node*> q; // 用于存储待扩展节点
    q.push(new Node(start, 0, "")); // 将初始状态加入到q中
    depth[start] = 0; // 初始状态的深度为0
    while (!q.empty()) {
        auto cur = q.front(); // 取出队列中的第一个节点
        q.pop();
        if (cur->state == end) return cur->path; // 找到目标状态，返回路径
        for (auto next : get_next_states(cur->state)) { // 扩展当前节点
            int d = cur->depth + 1; // 子节点的深度为父节点的深度加1
            if (!depth.count(next)) { // 如果子节点未被扩展
                depth[next] = d; // 记录子节点的深度
                path[next] = cur->path + direction(next, cur->state); // 记录子节点的路径
                q.push(new Node(next, d, path[next])); // 将子节点加入到q中
            }
        }
    }
    return ""; // 没有找到目标状态，返回空路径
}

在上面的代码中，我们使用了一个队列q来存储待扩展的节点。对于每个被扩展的节点，我们都生成它的所有合法子节点，并将未被扩展的子节点加入到q中。

3. 深度优先算法

string dfs(string start, string end, int max_depth) {
    unordered_map<string, int> depth; // 用于记录状态的深度
    unordered_map<string, string> path; // 用于记录状态的路径
    stack<Node*> s; // 用于存储待扩展节点
    s.push(new Node(start, 0, "")); // 将初始状态加入到s中
    depth[start] = 0; // 初始状态的深度为0
    while (!s.empty()) {
        auto cur = s.top(); // 取出栈顶的节点
        s.pop();
        if (cur->state == end) return cur->path; // 找到目标状态，返回路径
        if (cur->depth >= max_depth) continue; // 如果达到最大深度，不再扩展
        for (auto next : get_next_states(cur->state)) { // 扩展当前节点
            int d = cur->depth + 1; // 子节点的深度为父节点的深度加1
            if (!depth.count(next)) { // 如果子节点未被扩展
                depth[next] = d; // 记录子节点的深度
                path[next] = cur->path + direction(next, cur->state); // 记录子节点的路径
                s.push(new Node(next, d, path[next])); // 将子节点加入到s中
            }
        }
    }
    return ""; // 没有找到目标状态，返回空路径
}

在上面的代码中，我们使用了一个栈s来存储待扩展的节点。对于每个被扩展的节点，我们都生成它的所有合法子节点，并将未被扩展且深度未达到最大深度的子节点加入到s中。