A*算法
-
我们知道BFS是一种“盲目”的搜索技术，它在搜索过程中并不会理会目标在哪里，只顾自己走，当然最后总会到达终点，但是时间空间复杂度就很难说了。
-
比如说举个例子：你要从家到学校，现在有很多的路可以选择，对于聪明的你来说当然可以准确地选择最短的路，因为你毕竟不是个瞎子，能看见路途中你距离学校的距离，能够判断思考，可以随时调整新的路径。但是，对程序来说它很呆板，对于一般的BFS它会扩展各个方向尝试去搜索，哪怕是与目标背道而行，越走越远，所以我们为了让程序不去做这些不必要的搜索，可以考虑将我们的“智慧”交给程序，知道应该朝目标方向去搜索，那么这就是“启发式搜索”。这一节我们将学习其中比较简单的一种A*算法。
-
通俗说，A*算法其实就是“BFS + 贪心”。
-
在具体探讨A*算法前，我们先回顾一下上一节的优先队列BFS算法。该算法维护了一个优先队列(二叉堆)，不断从堆中取出“当前代价最小”的状态(堆顶)进行扩展。每个状态被第一次从优先队中取出时，就得了从初始状态到该状态的最小代价。
-
那么如果给定一个“目标状态”，需要求出从初始到目标状态的最小代价，那么优先队列BFS的这个“优先策略”是有局限性的。一个状态的当前代价最小，我们只能说从初始状态到该状态的代价最小，但在未来的搜索中我们不能保证这就是最优的，可能从该状态到目标状态会花费很大的代价。相反，一些状态在当前代价略大，但它能成为全局的最优解。优先队列BFS最终是可以求出全局的最优解，因为它的一个状态的最优解是在不断更新的。但是在搜索中它会优先选择前者的分支，这就会导致求出最优解的搜索量增大，在时间与空间的复杂度上增大许多。其实A*算法与这有点类似于“动态规划”与“贪心”的区别。
-
再回到刚刚的例子，我们可以将从家到学校的路看最网格状的图，此时我们要曼哈顿距离的概念：曼哈顿距离——两点在横纵方向差的和，即d（i，j）=|xi-xj|+|yi-yj|。对于一个具备正南正北、正东正西方向规则布局的城镇街道，从一点到达另外一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离，所以，曼哈顿距离又称为出租车距离。
-
为了我们搜索的效率，我们很自然可以想到，可以对未来可能产生的代价进行评估。那么我们就需要设计一个“估价函数”，它的功能主要是评估从当前任意状态到目标状态所需代价的估计值。在搜索中，仍要我们去维护一个堆，不断从堆中取出“当前代价+未来估价”最小的状态进行接下来的扩展搜索。为了摆正第一次从堆中取出目标状态是得到的就是最优解，我们设计的估价函数必须要满足一个基本准则：
-
设是当前所在的状态，是对的评估函数；
-
那么满足：
-
表示从初始状态到达当前状态的实际代价，它不体现当前状态与目标的关系；
-
表示从当前状态到目标的最优路径的评估，它实际就是“启发式”信息，我们把成为启发函数，很显然决定了A*算法的优劣。
-
特别注意:不能漏掉最优解。
-
在之前从学校到家的例子中，我们需要用到的启发函数就是曼哈顿距离，这里为什么用曼哈顿距离作为启发函数请同学们自己思考。
-
回头再看，我们说到A*算法通俗的说其实就是“BFS + 贪心”：
-
如果，有，这其实就是不同的BFS算法，会访问大量方块。
-
如果，有，这其实就是贪心算法，这就会导致在扩展时，只注重与局部的最优解，达不到全局的最优解。更有可能陷入一个状态就出不来了。
- 综上，A*算法提高搜索效率的关键，就在于能否设计出一个优秀的估价函数。在满足基本准则的前提下，还应该尽可能反映未来实际代价的变化趋势和相对大小关系，这样搜索才会较快地逼近最优解。
【例题】第k短路
题解
//DC Songxingan
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#define PII pair<int, int>
#define PIII pair<int, PII>
#define x first
#define y second
using namespace std;
const int N = 1010, M = 2e5 + 10;
int n, m, S, T, K;
int h[N], rh[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N]; // 每个点用没用过
void add(int h[], int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
// 在反向图上dijkstra()，保存估价函数(dist[]距离)
// dist存的是该点到终点的最小距离
void dijkstra()
{
priority_queue<PII, vector<PII>, greater<PII>> heap; // 优先队列，小根堆
heap.push({0, T}); //终点T是这里的起点 <距离，点编号>
memset(dist, 0x3f, sizeof dist);
dist[T] = 0;
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.y;
if (st[ver])
continue;
st[ver] = true; // 遍历过
// 在反向图上遍历，rh[]数组
for (int i = rh[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[ver] + w[i])
{
dist[j] = dist[ver] + w[i];
heap.push({dist[j], j});
}
}
}
}
int astar()
{
//
priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
// A* 算法，从起点开始搜
heap.push({dist[S], {0, S}}); // 估价值，{真实值，编号}
int cnt = 0; // 终点遍历几次
// 无解的话，返回-1
if (dist[S] == 0x3f3f3f3f)
return -1;
while (heap.size())
{
auto t = heap.top();
heap.pop();
int ver = t.y.y, distance = t.y.x; //从起点到该点的真实距离
if (ver == T)
cnt++; // 遍历一遍终点， cnt++，直到第K次
// 这个点是终点，并且是第k短路，直接返回第k短路的真实距离distance
if (cnt == K)
return distance;
// 正向扩展所有的边
// 用 起点到该点的真实距离+ 该点到终点的估价距离来作为标准
// distance + w[i] + dist[j]
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
heap.push({distance + w[i] + dist[j], {distance + w[i], j}});
}
}
return -1;
}
int main()
{
scanf("%d%d", &n, &m);
// 初始化表头
memset(h, -1, sizeof h);
memset(rh, -1, sizeof rh);
for (int i = 1; i <= m; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(h, a, b, c); // 建正边
add(rh, b, a, c); // 建反边
}
scanf("%d%d%d", &S, &T, &K);
if (S == T)
K++;
dijkstra();
printf("%d\n", astar());
}
