浅谈 A* 算法

I_LOVE_MATH · 2025-07-07 22:48:09 · 算法·理论

浅谈 A* 算法

更好的阅读体验

概论

计算最短路，通常使用两种算法：BFS 或 Dijkstra，前者用于无权图，后者用于有权图。

两者都是计算单源多汇最短路的算法，现在我们考虑一种更特殊的情况，即单源单汇最短路。

由于有“单汇”这一特殊条件，我们可以思考是否拥有优化的空间。

于是，我们有 A* 算法，是一种启发式搜索算法，它能够计算单源单汇最短路，可看作对于 BFS 和 Dijkstra 针对“单汇”这一特性的优化。

算法流程与分析

记 dis[i] 为 i 点到起点的最短距离。

与堆优化 Dijkstra 相同，我们维护一个优先队列。

开始，初始化源点 dis[start] = 0，其余点 dis 设为无穷大，并将起点入队。

之后，不断取出堆顶元素 u，遍历其邻居 v，记两者边权为 w，如果 dis[v] > dis[u] + w，就令 dis[v] > dis[u] + 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)。

解题思路

问题可以简化为求两者最短路，最后答案除以 2 即可。

由于无边权，采用 A* 的 BFS 写法。

这是一个网格图问题，对于网格图，我们通常取到终点的曼哈顿距离作为估价函数，即 h(x) = |x_{end} - x|+|y_{end} - y|。

估价函数显然是低估的。

估价函数也符合一致性，走一步曼哈顿距离只会减小 1，则有 h(u) = w(u, v) + h(v)，一致性成立。

故套用模板即可。

代码实现

#include<bits/stdc++.h>
#define endl "\n"
using namespace std;

const int N = 2e3 + 10;

struct node
{
    int x, y, f;
    bool operator < (const node &a) const
    {
        return f > 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<node> 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 <= 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && b[nx][ny] && dis[nx][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 <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            char ch;
            cin >> ch;
            if (ch == 'o')
            {
                b[i][j] = 1;
            }
            else if (ch == '#')
            {
                b[i][j] = 0;
            }
            else if (ch == 'R')
            {
                b[i][j] = 1;
                sx = i, sy = j;
            }
            else
            {
                b[i][j] = 1;
                ex = i, ey = j;
            }
            dis[i][j] = 1e9;
        }
    }
    int ans = astar();
    if (ans == -1)
    {
        cout << "forever" << endl;
    }
    else
    {
        cout << fixed << setprecision(1) << 1.0 * ans / 2 << endl;
    }
    return 0;
}

无人驾驶

题目大意

给出一个 n\times m 的迷宫，空地上有 1\sim 9 的数字表示走入这一格的费用，并且还有 p 次撞破墙走入该格子的机会，会产生 1 的额外费用，求从 (a, b) 到 (n, m) 的最小代价。

数据范围

解题思路

由于有边权，采用 A* 的 Dijkstra 写法。

对于估价函数，我们仍然采用到终点的曼哈顿距离，证明已经给出。

这里还有 p 次撞墙的机会，考虑使用拆点和分层图解决，将一个点 (x, y) 拆成若干个点 (x, y, p)，其中 p 表示还有几次撞墙的机会。

撞墙实际上就是从 (x, y, p) 走到 (nx, ny, p - 1)，边权为 1，其他情况照做即可。

答案即为 \min_{0 \le x \le p}(n, m, x)。

代码

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;

const int N = 210, M = 50;

struct node
{
    int x, y, p, f;
    bool operator < (const node &a) const
    {
        return f > a.f;
    }
};

int n, m, sx, sy, sp;
int a[N][N];
int dis[N][N][M];
bool vis[N][N][M];
int dx[10] = {0, 1, 0, -1, 0};
int dy[10] = {0, 0, 1, 0, -1};

priority_queue<node> q;

int h(int x, int y)
{
    return n - x + m - y;
}

void astar()
{
    dis[sx][sy][sp] = a[sx][sy];
    q.push((node) {sx, sy, sp, dis[sx][sy][sp] + h(sx, sy)});
    while (!q.empty())
    {
        int x = q.top().x, y = q.top().y, p = q.top().p;
        q.pop();
        if (vis[x][y][p])
        {
            continue;
        }
        vis[x][y][p] = 1;
        if (x == n && y == m)
        {
            return;
        }
        for (int i = 1; i <= 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i], np = p, w = a[nx][ny];
            if (a[nx][ny] == -1)
            {
                if (!np)
                {
                    continue;
                }
                np--;
                w = 1;
            }
            if (1 <= nx && nx <= n && 1 <= ny && ny <= m && !vis[nx][ny][np] && dis[nx][ny][np] > dis[x][y][p] + w)
            {
                dis[nx][ny][np] = dis[x][y][p] + w;
                q.push((node) {nx, ny, np, dis[nx][ny][np] + h(nx, ny)});
            }
        }
    }
}

int main()
{
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> sx >> sy >> sp;
    for (int i = 1; i <= n; i++)
    {
        string s;
        cin >> s;
        s = " " + s;
        for (int j = 1; j <= m; j++)
        {
            if (s[j] == '#')
            {
                a[i][j] = -1;
            }
            else
            {
                a[i][j] = s[j] - '0';
            }
            fill(dis[i][j], dis[i][j] + sp + 1, INT_MAX);
        }
    }
    astar();
    int ans = *min_element(dis[n][m], dis[n][m] + sp + 1);
    if (ans == INT_MAX)
    {
        cout << "mission impossible" << endl;
    }
    else
    {
        cout << ans << endl;
    }
    return 0;
}