浅谈 A* 算法

浅谈 A* 算法

概论

计算最短路，通常使用两种算法：BFS 或 Dijkstra，前者用于无权图，后者用于有权图。
两者都是计算单源多汇最短路的算法，现在我们思量一种更特别的情况，即单源单汇最短路。
由于有“单汇”这一特别条件，我们可以思考是否拥有优化的空间。
于是，我们有 A* 算法，是一种开导式搜索算法，它可以或许计算单源单汇最短路，可看尴尬刁难于 BFS 和 Dijkstra 针对“单汇”这一特性的优化。
算法流程与分析

记 \(dis\) 为 \(i\) 点到起点的最短距离。
与堆优化 Dijkstra 雷同，我们维护一个优先队列。
开始，初始化源点 \(dis[start] = 0\)，别的点 \(dis\) 设为无穷大，并将起点入队。
之后，不停取出堆顶元素 \(u\)，遍历其邻人 \(v\)，记两者边权为 \(w\)，如果 \(dis[v] > dis + w\)，就令 \(dis[v] > dis + w\)，最后将 \(v\) 入队。
如果取出了汇点，则竣事循环。
可以看到，其过程事实上与堆优化 Dijkstra 完全雷同，从而 A* 算法也只能处理没用负权的最短路，两者区别在于优先队列的排序。
A* 算法的优先队列中根据节点的 \(f(x)\) 从小到大排序，此中 \(f(x) = g(x) + h(x)\)，\(g(x)\) 体现源点到点 \(x\) 的最短路径（即 \(dis[x]\)），\(h(x)\) 是 \(x\) 点到汇点的最短路的一个估价函数（也就是对到汇点最短路的一个估计）。
因此，A* 算法的优化其实就体现在引入了一个估价函数，每一次选择 \(f(x)\) 最小的，也就是选择估计最有大概在最短路上的点优先访问，便能提高优先访问到汇点的概率，使得搜索范围降低，带来了常数上的优化，此中 \(h(x)\) 越接近现实最短路，算法越快（但不能凌驾，详见性质 \(1\)）。
值得注意的是，由于在排序上多引入了一个 \(h(x)\) 函数，导致其与 Dijkstra 产生了差异：弹出堆顶的点此时的 \(dis\) 并不一定是最短的，也就是说一个点被弹出堆顶后的 \(dis\) 仍然有大概被松懈，然后再次入堆（当然，一个好的 \(h(x)\) 函数不会让一个点重复入堆，详见性质 \(2\)）。
特别地，当 \(h(x) = 0\) 时，A* 退化为 Dijkstra，当 \(h(x) = 0\) 且边权为 \(1\) 时，A* 退化为 BFS。
性质

1. \(h(x)\) 是低估函数是 A* 算法正确的充分条件

记 \(x\) 到汇点的真实最短路长度为 \(h'(x)\)。
\(h(x)\) 可以低估，不能高估，也就是说 \(h(x) \le h'(x)\)。
证明如下：
令 \(h(x)\) 为低估函数，记源点为 \(s\)，汇点为 \(t\)。
假设最后得到的 \(dis[t]\) 错误，由于 \(dis[t]\) 一定是路径累加而成，以是 \(dis[t]\) 一定是相对正确效果大。
那么既然算法竣事，t 一定已经出堆，也就是堆中不存在 \(f(x)\) 比 \(f(t) = g(t) + h(t) = g(t) = dis[t]\) 小（低估函数，\(h(t)\) 必为 \(0\)）。
现在我们思量原先 \(s\) 到 \(t\) 的最短路，记 A* 此时沿着这条路径走到了 \(u\)（已出堆），再记在最短路上 \(u\) 后面点为 \(v\)，此时 \(v\) 在堆中，那么我们有：

\[f(v) = g(v) + h(v) \le g(v) + h'(v) = s\,到\,t\,最短路< dis[t] = f(t)\]
这与“堆中不存在 \(f(x)\) 比 \(f(t)\) 小”的结论抵牾，故假设不成立，得证。
简朴地说，就是不管错误的路径的估价多么小，可以或许被优先访问，但只要到达与汇点相邻的点，便会将 \(f(t)\) 放入堆中，此时的 \(f(t)\) 一定就是这条路径的真实长度，由于 \(h(x)\) 是低估函数，以是真实沿着最短路走到的点的 \(f(x)\) 必定不大于现实最短路，更加小于之前放入的 \(f(t)\)，使得错误的 \(f(t)\) 将始终被卡在后面，不会出堆，那么也就是只有对的才会出堆。
反之，如果高估，就大概导致真实的最短路被高估得大于入堆的错误路径长度，以至于错误的会被先弹出。
2. \(h(x)\) 满足一致性能使得出堆的点的 \(dis\) 必为最小值

一致性是对于所有的边 \((u,v)\)，都包管 \(h(u) \le w(u, v) + h(v)\)（满足三角不等式）。
只要满足一致性，那么出堆的点的 \(dis\) 就必为最小。
证明如下：
若 \(g(u)\) 能更新 \(g(v)\)，则有 \(g(u) + w(u,v)< g(v)\)。
结合一致性 \(h(u) \le w(u,v) + h(v)\)，累加两式，得 \(f(u) < f(v)\)，则 \(u\) 优先于 \(v\) 出堆。
对于所有点，可以或许更新它的点都在它之前出堆，也就是在它之后出堆的点不能更新它，这使得其出堆时的 \(dis\) 无法被松懈，即为最小。
因此我们需要注意，A* 算法与 Dijkstra 不一样的地方在于，不一定能在一个点出堆后发现其被访问过就跳过这个点，此步骤仅能在满足一致性的情况下可以或许使用。
例题

罗密欧与朱丽叶

题目大意

给出一个 \(n \times m\) 的迷宫，在两个位置分别有两个人，两者每秒分别都能往上下左右走一格，求他们相遇需要至少几秒钟。
数据范围


\(1 a.f;        }};int n, m, sx, sy, ex, ey;bool b[N][N], vis[N][N];int dis[N][N];int dx[10] = {0, 1, 0, -1, 0};int dy[10] = {0, 0, 1, 0, -1};priority_queue q;int h(int x, int y){        return abs(ex - x) + abs(ey - y);}int astar(){        dis[sx][sy] = 0;        q.push((node) {sx, sy, h(sx, sy)});        while (!q.empty())        {                int x = q.top().x, y = q.top().y;                q.pop();                if (vis[x][y])                {                        continue;                }                vis[x][y] = 1;                if (x == ex && y == ey)                {                        return dis[x][y];                }                for (int i = 1; i = 1 && nx = 1 && ny  dis[x][y] + 1)                        {                                dis[nx][ny] = dis[x][y] + 1;                                q.push((node){nx, ny, dis[nx][ny] + h(nx, ny)});                        }                }        }        return -1;}int main(){        ios :: sync_with_stdio(0);        cin.tie(0), cout.tie(0);        cin >> n >> m;        for (int i = 1; i  ch;                        if (ch == 'o')                        {                                b[j] = 1;                        }                        else if (ch == '#')                        {                                b[j] = 0;                        }                        else if (ch == 'R')                        {                                b[j] = 1;                                sx = i, sy = j;                        }                        else                        {                                b[j] = 1;                                ex = i, ey = j;                        }                        dis[j] = 1e9;                }        }        int ans = astar();        if (ans == -1)        {                cout > sp;        for (int i = 1; i > s;                s = " " + s;                for (int j = 1; j