写一个使用A*算法实现8数码和15数码问题的程序，要求采用两种估价函数

好的，我了解了你的要求。以下是用A*算法实现8数码和15数码问题的程序代码示例，其中使用了两种常见的估价函数：Manhattan距离和曼哈顿距离。

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

const int N = 3; // 3*3=9, 4*4=16, ...

const string TARGET_8 = "12345678x"; // 目标状态
const string TARGET_15 = "123456789abcdefx";

// 计算曼哈顿距离估价函数
int heuristic(const string& state) {
    int score = 0;
    for (int i = 0; i < N*N; ++i) {
        char c = state[i];
        if (c != 'x') {
            int m = abs(i%N - (c-'1')%N);
            int n = abs(i/N - (c-'1')/N);
            score += m + n;
        }
    }
    return score;
}

// 计算Manhattan距离估价函数
int heuristic2(const string& state) {
    int score = 0;
    for (int i = 0; i < N*N; ++i) {
        char c = state[i];
        if (c != 'x') {
            int m = i % N - (c-'1') % N;
            int n = i / N - (c-'1') / N;
            score += abs(m) + abs(n);
        }
    }
    return score;
}

// 判断状态是否合法
bool valid(const string& s) {
    int cnt = 0; // 记录逆序对的数量
    for (int i = 0; i < N*N; ++i) {
        if (s[i] == 'x') continue;
        for (int j = 0; j < i; ++j) {
            if (s[j] != 'x' && s[j] > s[i]) cnt++;
        }
    }
    return cnt % 2 == 0; // 逆序对数量为偶数时合法
}

// 找到空格的位置
int find_blank(const string& s) {
    for (int i = 0; i < N*N; ++i) {
        if (s[i] == 'x') return i;
    }
    return -1;
}

// 生成下一步的状态
void generate_next_states(const string& s, vector<string>& next_states) {
    next_states.clear();
    int b = find_blank(s);
    int x = b % N, y = b / N;
    // 获取可能的移动方向
    vector<pair<int,int>> dirs = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    for (auto [dx, dy] : dirs) {
        int nx = x + dx, ny = y + dy;
        if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        int nb = ny*N + nx;
        string ss = s;
        swap(ss[b], ss[nb]);
        if (valid(ss)) next_states.push_back(ss);
    }
}

// A*搜索算法
string astar(const string& start, const string& target, int (*heuristic_func)(const string&)) {
    priority_queue<pair<int,string>, vector<pair<int,string>>, greater<pair<int,string>>> pq;
    unordered_map<string, int> visited;
    unordered_map<string, string> parent;
    pq.push({heuristic_func(start), start});
    visited[start] = 0;
    while (!pq.empty()) {
        auto [f, s] = pq.top();
        pq.pop();
        if (s == target) return s; // 找到目标状态
        if (visited[s] < f) continue; // 已经有更优的路径到达该状态
        vector<string> next_states;
        generate_next_states(s, next_states);
        for (auto& ns : next_states) {
            // 计算新状态的f值
            int g = visited[s] + 1;
            int h = heuristic_func(ns);
            int f = g + h;
            if (!visited.count(ns) || g < visited[ns]) {
                visited[ns] = g;
                parent[ns] = s;
                pq.push({f, ns});
            }
        }
    }
    return ""; // 没有找到路径
}

int main() {
    string start, target;
    if (N == 3) {
        start = "8467253x1";
        target = TARGET_8;
    } else if (N == 4) {
        start = "d13c2b5f649a78x";
        target = TARGET_15;
    } else {
        cout << "Unsupported size of puzzle." << endl;
        return 0;
    }
    if (!valid(start)) { // 判断起始状态是否合法
        cout << "Invalid start state." << endl;
        return 0;
    }
    string path = astar(start, target, heuristic);
    if (path.empty()) {
        cout << "No solution found." << endl;
        return 0;
    }
    // 输出路径
    vector<string> states;
    while (path != start) {
        states.push_back(path);
        path = parent[path];
    }
    states.push_back(start);
    for (auto iter = states.rbegin(); iter != states.rend(); ++iter) {
        for (int i = 0; i < N*N; ++i) {
            cout << (*iter)[i] << " ";
            if ((i+1) % N == 0) cout << endl;
        }
        cout << endl;
    }
    return 0;
}

在程序中，我们定义了两种估价函数`heuristic`和`heuristic2`，分别用于计算曼哈顿距离和Manhattan距离。判断状态是否合法的函数是`valid`，它通过计算逆序对的数量来判断状态是否可达。函数`generate_next_states`用于在当前状态下生成下一步的所有合法状态。

最后，我们使用A*搜索算法来寻找从起始状态到目标状态的最短路径，并输出路径中的所有状态。注意，在程序中，估价函数的选择可以通过传递不同的指针参数来实现。