A-star 算法——启发式搜索算法

种子相声大师 JustPureH₂O 在他的新作里如此写道：

（上台）

今个咱们不说dijkstra，咱来聊一聊 A星算法。

诶，这个我知道。A星就是矩阵 A 的伴随矩阵，它有可多性质啦！考研娃们万别错过，咱们说这个伴随……

哎打住打住，A星算法怎么能是矩阵呢？再说了，你一个高中生不好好搞圆锥曲线和导数，反而来学线性代数干什么？

挨个列举矩阵 A 的代数余子式并把它放到一个新矩阵。

停停停！咱们这个 A星算法是用来求最优路径哒，你手机里的高德都用的就是 A星算法啦。A星是启发式搜索算法的其中一种，它还有一个迭代加深的版本 IDA……

这有啥的，我一通暴力 BFS 也能求最短路。

跟你那个不一样，人家 A星都是在数量级往上跑的，你一个 BFS 早超时啦——欸，所以你在认真听没有？我来考考你，A星是什么算法？

是矩阵 A 的伴随矩阵。

去你的吧

（鞠躬退场）

A-star 算法介绍#

如果你认真听了课，你就会知道 A星算法是~~伴随矩阵~~启发式搜索算法的一类，至于为什么是字母 A 加上一个星号——那得去问起这个名字的人，我也不清楚。

A星算法很像资本家的思维模式。对于有着庞大节点数量的图，要从起点开始搜寻到一条到终点的路径。此时的 BFS 就像一个不会做加法的完美主义者（BFS 跑最短路的要求是边权只出现一个或两个非负数），非得把所有通路都遍历一遍、才找出一条严格的最短路径；而 Dijkstra 算法又像只会做加法的完美主义者（只要边权非负即可，若要跑负权边请移步至已死的算法），和 BFS 相似，也要遍历大量的节点才找出一条路径。可是 A星思路却格外清奇——它设计了一个对当前节点进行估价的函数，根据价值大小选择是否经过该节点，因此 A星算法得到的路径一定是耗材最少的路径，并且由于省去了大量无用遍历，它的执行效率也会快很多。

要实现 A星算法，我们首先就要对堆优化的 Dijkstra 进行一个小变动：

将 Dijkstra 所使用的记录距离的优先队列改为估价函数的优先队列。

其余的和 Dijkstra 也比较相似，我们需要遍历与该节点伸展出去的边，并入队这些边。当终点第一次出队时，跳出计算并返回最短值。

那么如何给点估价？我们首先要计算当前点到起点的真实距离并记作；再将当前点到终点的估计距离（注意是估计出来的距离）记作，那么估价函数。注意到 Dijkstra 算法并不关心当前点到终点的估计距离，因此它是恒成立的特殊情况。

A-star 注意事项#

点的入队：在入队新点时，优先队列的排序关键字应该设为，也就是 dist[now] + f(now) 的形式；特殊地，入队起点时应该将排序关键字设为 f(now)（此时显然 dist[now] 的值为）。
估价函数的写法：估价函数不存在一个固定的模板。在P1379 八数码难题中，它是当前状态到目标状态的曼哈顿距离之和；在P2901 Cow Jogging G中，它又是当前点到终点的最短距离。因而对于不同的题目，估价函数都需要重新设定。
STL 使用的细节：优先队列 priority_queue 中若存储的是二元组 pair，那么将自动按照 pair 的第一关键字排序，且优先队列默认为大根堆（队头永远是最大的），而在实际算法中，我们更常使用小根堆，此时将优先队列定义为 priority_queue<PAIR, vector<PAIR>, greater<PAIR>> 即可。

A-star 典例#

洛谷 P1379 八数码难题#

题目传送门：这里

题目难度：普及+/提高

题目来源：福建省历届夏令营

在的棋盘上，摆有八个棋子，每个棋子上标有至的某一数字。棋盘中留有一个空格，空格用来表示。空格周围的棋子可以移到空格中。要求解的问题是：给出一种初始布局（初始状态）和目标布局（为了使题目简单,设目标状态为），找到一种最少步骤的移动方法，实现从初始布局到目标布局的转变。
输入
输入初始状态，一行九个数字，空格用表示。
输出
只有一行，该行只有一个数字，表示从初始状态到目标状态需要的最少移动次数。保证测试数据中无特殊无法到达目标状态数据。
样例输入 #1
1
283104765
样例输出 #1
1
4
样例 #1 解释
图中标有的是空格。绿色格子是空格所在位置，橙色格子是下一步可以移动到空格的位置。如图所示，用四步可以达到目标状态。
并且可以证明，不存在更优的策略。

先用朴素 BFS 的思路思考一遍，我们肯定是要枚举可能到达的状态，若当前状态和目标状态相同，则返回步数。由于 BFS 的最短路性质，在目标状态第一次弹出时即可返回步数。

考虑使用 A* 算法，我们就需要思考如何对状态估价，即计算当前状态与目标状态的差异度。不妨计算同一元素在当前状态和目标状态的曼哈顿距离（横坐标距离加上纵坐标距离），并对除开空格外的八个元素均使用此操作，并累加结果，就能得到描述两个状态的差异度的量了。

代码：

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
typedef pair<int, string> STATE;
6
unordered_map<string, int> dist;
7
priority_queue<STATE, vector<STATE>, greater<>> q;
8
string st, ed = "123804765";
9

10
int f(const string &now) {
11
    int res = 0;
12
    for (int i = 0; i < 9; i++) {
13
        if (now[i] == '0') continue;
14
        switch (now[i] - '0') {
15
            case 1:
16
            case 2:
17
            case 3:
18
                res += abs(i / 3) + abs(i % 3 - (now[i] - '1') % 3);
19
                break;
20
            case 4:
21
                res += abs(i / 3 - 1) + abs(i % 3 - 2);
22
                break;
23
            case 5:
24
                res += abs(i / 3 - 2) + abs(i % 3 - 2);
25
                break;
26
            case 6:
27
                res += abs(i / 3 - 2) + abs(i % 3 - 1);
28
                break;
29
            case 7:
30
                res += abs(i / 3 - 2) + abs(i % 3);
31
                break;
32
            case 8:
33
                res += abs(i / 3 - 1) + abs(i % 3);
34
                break;
35
        }
36
    }
37
    return res;
38
}
39

40
int bfs() {
41
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
42
    q.push((STATE) {f(st), st});
43
    dist[st] = 0;
44
    while (!q.empty()) {
45
        STATE s = q.top();
46
        q.pop();
47
        if (s.second == ed) return dist[s.second];
48
        int idxx = 0, idxy = 0;
49
        for (int i = 0; i < 9; i++) {
50
            if (s.second[i] == '0') {
51
                idxx = i / 3, idxy = i % 3;
52
                break;
53
            }
54
        }
55
        string src = s.second;
56
        string tmp = s.second;
57
        for (int i = 0; i < 4; i++) {
58
            int nx = idxx + dx[i], ny = idxy + dy[i];
59
            if (nx < 0 || nx > 2 || ny < 0 || ny > 2) continue;
60
            tmp = src;
61
            swap(tmp[idxx * 3 + idxy], tmp[nx * 3 + ny]);
62
            if (!dist.count(tmp) || dist[tmp] > dist[src] + 1) {
63
                dist[tmp] = dist[src] + 1;
64
                q.push((STATE) {f(tmp) + dist[tmp], tmp});
65
            }
66
        }
67
    }
68
    return -1;
69
}
70

71
int main() {
72
    ios::sync_with_stdio(false);
73
    cin.tie(nullptr);
74
    cout.tie(nullptr);
75

76
    cin >> st;
77
    cout << bfs() << endl;
78

79
    return 0;
80
}

总用时：记录

洛谷 P2901 [USACO08MAR] Cow Jogging G#

题目传送门：这里

题目难度：提高+/省选-

题目来源：USACO 2008

贝西终于尝到了懒惰的后果，决定每周从谷仓到池塘慢跑几次来健身。当然，她不想跑得太累，所以她只打算从谷仓慢跑下山到池塘，然后悠闲地散步回谷仓。
同时，贝西不想跑得太远，所以她只想沿着通向池塘的最短路径跑步。一共有条道路，其中每一条都连接了两个牧场。这些牧场从到编号，如果，则说明牧场的地势高于牧场，即下坡的道路是从通向的，为贝西所在的牛棚（最高点），为池塘（最低点）。
然而，一周之后，贝西开始对单调的路线感到厌烦，她希望可以跑不同的路线。比如说，她希望能有种不同的路线。同时，为了避免跑得太累，她希望这条路线是从牛棚到池塘的路线中最短的条。如果两条路线包含的道路组成的序列不同，则这两条路线被认为是不同的。
请帮助贝西算算她的训练强度，即将牧场网络里最短的条路径的长度分别算出来。你将会被提供一份牧场间路线的列表，每条道路用表示，意为从到有一条长度为的下坡道路。
输入
第一行三个用空格分开的整数，其中。
第二行到第行每行有三个用空格分开的整数，描述一条下坡的道路。
输出
共行，在第行输出第短的路线长度，如果不存在则输出。如果出现多种有相同长度的路线，务必将其全部输出。
数据范围
对于全部的测试点，保证，，，，，

题意简化：给定一张图，分别求从点到点的第短路的长度。

要想求这个问题，需要先明确下边的一条性质：

在 A* 算法中，当终点出队次时，此时经过的总距离就是第短路的距离。

因而我们设置一个的循环，分别求出对应情况的短路。需要注意的是，当此时的循环变量已经大于从起点到终点的总路径数时，自然就无需重复计算后面的情况，直接输出就好。对于估价函数，我们在反图上跑一遍最短路即可。

代码：

1
#include <bits/stdc++.h>
2

3
#define N 10010
4
using namespace std;
5

6
typedef long long ll;
7
typedef pair<ll, int> Point;
8
typedef pair<ll, Point> Star;
9

10
struct Edge {
11
    int ne, to;
12
    ll w;
13
} edges[N << 2];
14

15
int h[N], rh[N];
16
bool st[N];
17

18
priority_queue<Point, vector<Point>, greater<>> q;
19
priority_queue<Star, vector<Star>, greater<>> heap;
20
int astar_cnt = 0;
21
ll dist[N];
22
int idx = 0;
23
int n, m;
24

25
void add(int he[], int u, int v, ll w) {
26
    idx++;
27
    edges[idx].to = v;
28
    edges[idx].ne = he[u];
29
    edges[idx].w = w;
30
    he[u] = idx;
31
}
32

33
void dijkstra() {
34
    q.push((Point) {0, 1});
35
    dist[1] = 0;
36
    while (!q.empty()) {
37
        Point p = q.top();
38
        q.pop();
39
        int id = p.second;
40
        if (st[id]) continue;
41
        st[id] = true;
42
        for (int i = rh[id]; ~i; i = edges[i].ne) {
43
            int j = edges[i].to;
44
            if (dist[j] > dist[id] + edges[i].w) {
45
                dist[j] = dist[id] + edges[i].w;
46
                q.push((Point) {dist[j], j});
47
            }
48
        }
49
    }
50
}
51

52
ll a_star(int k) {
53
    heap.push((Star) {dist[n], (Point) {0, n}});
54
    while (!heap.empty()) {
55
        Star p = heap.top();
56
        heap.pop();
57
        if (p.second.second == 1) astar_cnt++;
58
        if (astar_cnt == k) return p.second.first;
59
        for (int i = h[p.second.second]; ~i; i = edges[i].ne) {
60
            int j = edges[i].to;
61
            heap.push((Star) {dist[j] + edges[i].w + p.second.first, (Point) {p.second.first + edges[i].w, j}});
62
        }
63
    }
64
    return -1;
65
}
66

67
void restore() {
68
    astar_cnt = 0;
69
    heap = priority_queue<Star, vector<Star>, greater<>>();
70
}
71

72
int main() {
73
    ios::sync_with_stdio(false);
74
    cin.tie(nullptr);
75
    cout.tie(nullptr);
76

77
    memset(h, -1, sizeof h);
78
    memset(rh, -1, sizeof rh);
79
    memset(dist, 0x3f, sizeof dist);
80

81
    int k;
82
    cin >> n >> m >> k;
83
    for (int i = 1; i <= m; i++) {
84
        int x, y;
85
        ll d;
86
        cin >> x >> y >> d;
87
        add(h, x, y, d);
88
        add(rh, y, x, d);
89
    }
90

91
    dijkstra();
92

93
    bool flag = false;
94
    for (int i = 1; i <= k; i++) {
95
        if (flag) cout << -1 << endl;
96
        else {
97
            restore();
98
            ll res = a_star(i);
99
            cout << res << endl;
100
            flag = (res == -1);
101
        }
102
    }
103

104
    return 0;
105
}

音乐

JustPureH₂O

穷方圆平直之情，尽规矩准绳之用

音乐

A-star 算法——启发式搜索算法

A-star 算法介绍#

A-star 注意事项#

A-star 典例#

洛谷 P1379 八数码难题#

洛谷 P2901 [USACO08MAR] Cow Jogging G#

支持与分享

评论区

音乐

目录

音乐

JustPureH2O

穷方圆平直之情，尽规矩准绳之用

音乐

A-star 算法——启发式搜索算法

A-star 算法介绍#

A-star 注意事项#

A-star 典例#

洛谷 P1379 八数码难题#

洛谷 P2901 [USACO08MAR] Cow Jogging G#

支持与分享

评论区

音乐

目录

JustPureH₂O