介绍A星算法的定义和应用（内附代码实现）。
A-Star 是啥？？ A-Star 用来干啥？？
首先，A-Star 算法只能用在数据规模很大的搜索题中，这时直接用 BFS 会超时，而利用 启发函数（估价函数） 优化后的 BFS ——A-Star 算法就能处理这种问题。
A-Star 算法通过一个 “启发函数（估价函数）” 来使到达终点需要遍历的状态大大减少，以达到提高运行效率的作用。
就比如：当普通的 BFS 需要遍历 108、109 甚至 1020 个状态才能到达终点时，通过 A-Star 的启发函数 则只需要遍历极少的状态就能达到终点。
注意： 使用 A-Star 时需要判断是否有解，当无解时（或者是数据规模较小时） A-Star 的效率可能会比朴素的 BFS 还低。
A-Star 代码框架
首先，我们要把朴素的 BFS 中的队列换成优先队列。
伪代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
| while ( ! q.size() )
{
t = 优先队列（小根堆）队头 ;
if ( t == 终点 ) break ;
for ( 枚举 t 的所有邻边 )
{
if ( 子节点可取 )
{
邻边入队；
}
}
}
|
那么这个优先队列中存啥呢？
首先，肯定要把该节点到起点的真实距离存下来；
此次，要把 真实距离+该节点到终点的估计距离 的总和存下来，并作为优先队列的排序关键字。
这个总和的含义就是 起点到终点的总的估计距离 。
每次取出优先队列的队头出来即每次取一个 估计距离最小的点 来扩展。
关于估价函数
估价函数是 A-Star 算法的核心部分。
首先，要知道 估价函数是针对每个题目具体情况设计的 ，有许多种方法可以算出估值，常用的有 Manhattan 等。
设当前点为 state 。
设当前点到起点的真实距离为d[state]；
设当前点到终点的估计距离为 f[state]；
设当前点到终点的真实距离为 g[state]；
那么我们设计的估计函数必须满足如下性质：
- 对于任意的 state ，都必须满足 f[state] ≤ g[state]。
- 如果满足该条件，则当终点第一次出队时一定是最小值。
下面给出证明：
我们先证明第 1 点：
可用极限法证明：当估计距离为无限大时（此时估值绝对大于真值），该节点会被压在堆底无法取出；同样的，当最优解的估值被估计成无限大时，最优解的节点也会被压在堆底，导致非最优解上的节点被取出拓展，直到取出了终点产生错误答案。
所以，对于任意的 state ，都必须满足 f[state] ≤ g[state]。
我们再利用反证法证明第 2 点：
反正他就是这样，我也说不了什么
我们设终点第一次出队时不是最小值。
也就是说此时终点的 d[state] 严格大于 d[最优解] 。
此时队列中肯定存在最优解路径上的某一个点，设该点为 u 。
那么最优解的长度就等于 d[u]+g[u] 。
由于我们的 f[u] 是小于 g[u] 的，可以得出 最优解的长度 = d[最优解] = d[u]+g[u] ≥ d[u]+f[u] 。
又因为 d[state] 大于 d[最优解] ，所以 d[state] 大于 g[u]+f[u] 。
这也就意味着 小根堆中还存在一个比队头还小的元素 ，与小根堆的定义矛盾。
所以，如果满足该条件，则当终点第一次出队时一定是最小值。
综上：对于任意的 state ，都必须满足 f[state] ≤ g[state]；如果满足，则当终点第一次出队时一定是最小值。
证毕。
tips： 估值越接近真值，A-Star 的效率越高。
注意： 只有在终点第一次被取出时能保证是最小值，其他节点不一定是最小值。
因为我们的估计函数是针对终点设计的，估值也是针对终点计算出来的，小根堆的排序关键字也是起点到终点的总估值，所以只能保证终点第一次被取出时是最小值。
例题
八数码
ACWing题面 和 洛谷题面
题目描述
输入一行八个数字和一个 “ x ” （x 表示空格）表示 3 * 3 的一个矩阵。
请问将该矩阵恢复到原状需要如何操作（需要几步）。
原状： 1 2 3 4 5 6 7 8 x
题解
首先判定可解性：计算初态与终态的逆序对个数，如果两者奇偶性相同，则有解，否则无解。
又因为终态已经确定，逆序对个数为 0 ，所以初态的逆序对个数一定要为偶数。
注意：使用 A-Star 算法前都应判断一下可解性，因为当无解时用 A-Star 效率会非常低。
题目蛮简单的，直接在代码中解释吧。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<unordered_map>
#include<vector>
#define PIS pair<int,string>
using namespace std;
const int N = 1010;
int f(string s)
{
int ans = 0;
for (int i = 0; i < s.size(); i++)
{
if (s[i] != 'x')
{
int t = s[i] - '1';
ans += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);
}
}
return ans;
}
unordered_map < string, int > d;
unordered_map < string, pair<char, string> > pre;
priority_queue < PIS, vector <PIS>, greater<PIS> > heap;
string bfs(string st)
{
string en = "12345678x";
char op[] = "urdl";
d[st] = 0;
heap.push({f(st), st});
int fx[4] = {-1, 0, 1, 0}, fy[4] = {0, 1, 0, -1};
while (heap.size())
{
PIS t = heap.top();
heap.pop();
string state = t.second;
if (state == en)break;
int x, y;
for (int i = 0; i < 9; i++)
{
if (state[i] == 'x')
{
x = i / 3;
y = i % 3;
break;
}
}
string s = state;
for (int i = 0; i < 4; i++)
{
int a = x + fx[i], b = y + fy[i];
if (a < 0 || a > 2 || b < 0 || b > 2) continue;
state = s;
swap(state[x * 3 + y], state[a * 3 + b]);
if (!d.count(state) || d[state] > d[s] + 1)
{
d[state] = d[s] + 1;
pre[state] = {op[i], s};
heap.push({d[state] + f(state), state});
}
}
}
string ans;
while (en != st)
{
ans += pre[en].first;
en = pre[en].second;
}
reverse(ans.begin(), ans.end());
return ans;
}
int main()
{
string st, seq;
string c;
for (int i = 1; i <= 9; i++)
{
cin >> c;
st += c[0];
if (c[0] != 'x')seq += c[0];
}
int cn = 0;
for (int i = 0; i < 8; i++)
for (int j = i; j < 8; j++)
if (seq[i] > seq[j])cn++;
if (cn & 1)printf("unsolvable");
else cout << bfs(st);
return 0;
}
|
接下来还有一种题型。
第 K 短路
题目描述
给一张有向图，给出起点S、终点T、K，求出从起点到终点的第 K 短路（路径允许重复经过点或边）。
注意：每条最短路中至少要包含一条边。
题解
首先肯定是想到打暴力。
把 S 到 T 的每一条路径长都算出来，再找出第 K 短的路。
但由于数据庞大，暴力只能骗到一点分。
而数据庞大时我们可以用 A-Star 来做。
先考虑估价函数怎么打。
因为估值要小于等于真值，同时又要尽可能接近真值，那么我们可以把 当前点到终点的最短路 作为当前点到终点的估值。
而计算这个估值只需要 在反向图上跑一遍 dijkstra 就好了。
估价函数设计出来后怎么求第 K 短路？
由数学归纳法易证，当终点被第 K 次从队中取出时对应的路径就是第 K 短路。
所以，代码就很好写了。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
| #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<unordered_map>
#include<vector>
#define PII pair<int,int>
#define PIII pair<int,PII>
using namespace std;
const int N = 1010, M = 200020;
int n, m, cn, h[M], rh[M], nxt[M], to[M], w[M], d[N], v[N], S, T, K;
void addh(int a, int b, int c)
{
nxt[++cn] = h[a];
to[cn] = b;
w[cn] = c;
h[a] = cn;
}
void addrh(int a, int b, int c)
{
nxt[++cn] = rh[a];
to[cn] = b;
w[cn] = c;
rh[a] = cn;
}
void dijk()
{
priority_queue<PII, vector<PII>, greater<PII> > q;
q.push({0, T});
memset(d, 0x3f, sizeof d);
d[T] = 0;
while (q.size())
{
PII t = q.top();
q.pop();
int x = t.second;
if (v[x])continue;
v[x] = 1;
for (int i = rh[x]; i; i = nxt[i])
{
int j = to[i];
if (d[j] > d[x] + w[i])
{
d[j] = d[x] + w[i];
q.push({d[j], j});
}
}
}
}
int astar()
{
priority_queue<PIII, vector<PIII>, greater<PIII> > q;
memset(v, 0, sizeof v);
q.push({d[S], {0, S}});
while (q.size())
{
PIII x = q.top();
q.pop();
int t = x.second.second, dist = x.second.first;
v[t]++;
if (v[T] == K) return dist;
for (int i = h[t]; i; i = nxt[i])
{
int j = to[i];
if (v[j] < K) q.push({dist + w[i] + d[j], {dist + w[i], j}});
}
}
return -1;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
addh(a, b, c);
addrh(b, a, c);
}
scanf("%d%d%d", &S, &T, &K);
if (S == T)K++;
dijk();
printf("%d", astar());
return 0;
}
|
ok，笔记结束。
你学废了吗？
本文部分参考 ACWing y总 的讲解以及lyd的《算法竞赛进阶指南》。
如有错误请 @Dumby_cat 这只蒟蒻。