【搜索】【模板】A* 算法

学了 IDA*，
然后学学 A*。

A*

A* 可以简单理解为在 bfs 的时候分个先后，哪个最有可能先到达就先走哪一步。

A* 是在某个最短路问题中（比如求最小的步骤等），如果所有边权都是非负的，那么就可以使用启发函数来优化 bfs 过程。

例题 P1379 八数码难题

思路

我们在 bfs 的过程中加入函数 \(h()\) 表示在某个状态下用最乐观的走法从当前状态到终止状态的步骤。

当然，不难想到 \(h()\) 函数比任何走法都要小。

估价函数 \(f(s)\) 就是在状态 \(s\) 下，已经走的距离 \(g(s)\) 加上最乐观的走法需要的步数 \(h(s)\)，即 \(f(s) = g(s) + h(s)\)。

所以将 bfs 的 queue 改为 priority_queue，关键字为 \(f = g + h\)，采用小根堆。

代码

#include <bits/stdc++.h>

#define node vector<vector<int> >

using namespace std;

const int N = 9;

map<node, int> s;
node g(3, vector<int>(3));
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

node des = 
{
    {1, 2, 3},
    {8, 0, 4},
    {7, 6, 5}
};

int x[N], y[N];

struct cmpnode {
    node g;

    int h() const {
        int cnt = 0;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                cnt += abs((i - x[g[i][j]])) + abs((j - y[g[i][j]]));
            }
        }
        return cnt;
    }

    bool operator>(const cmpnode b) const {
        return s[g] + h() > s[b.g] + b.h();
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string tmp;
    cin >> tmp;
    for (int i = 0, cnt = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            g[i][j] = tmp[cnt++] - '0';
        }
    }

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            x[des[i][j]] = i;
            y[des[i][j]] = j;
        }
    }

    priority_queue<cmpnode, vector<cmpnode>, greater<cmpnode> > q;
    q.push({g});
    s[g] = 0;

    while (q.size()) {
        g = q.top().g;
        auto t = g;
        q.pop();
        if (g == des) {
            cout << s[g] << '\n';
            return 0;
        }

        int sp_x = -1, sp_y = -1;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                if (g[i][j] == 0)
                    sp_x = i, sp_y = j;

        for (int i = 0; i < 4; i++) {
            int nx = sp_x + dx[i], ny = sp_y + dy[i];
            if (nx < 0 || ny < 0 || nx > 2 || ny > 2) continue;
            swap(g[sp_x][sp_y], g[nx][ny]);
            if (!s.count(g)) {
                s[g] = s[t] + 1;
                q.push({g});
            }
            swap(g[sp_x][sp_y], g[nx][ny]);
        }
    }
    return 0;
}