A* 算法

概念讲解

什么是 A*？

A* 是一种启发式搜索算法，使用估价函数引导搜索方向。

估价函数

f(n)=g(n)+h(n)f(n) = g(n) + h(n)

  • g(n)：从起点到 n 的实际代价
  • h(n)：从 n 到终点的估计代价

正确性条件

h(n) 必须是可采纳的，即不高估实际代价。

实现

12345678910111213141516171819int aStar(int start, int end) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({h(start), start});
    dist[start] = 0;
    
    while (!pq.empty()) {
        auto [f, u] = pq.top();
        pq.pop();
        if (u == end) return dist[u];
        
        for (auto& [v, w] : graph[u]) {
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push({dist[v] + h(v), v});
            }
        }
    }
    return -1;
}

考点分析

初赛考查方式

  1. 程序阅读： A* 算法
  2. 编程题： 启发式搜索

常见考点

  • 估价函数设计
  • A* 与 Dijkstra 关系
  • 可采纳性

练习题

  1. A* 和 Dijkstra 的关系？
查看答案

A* 是 Dijkstra 的扩展：

  • Dijkstra 只考虑 g(n)g(n)（实际代价）
  • A* 同时考虑 g(n)g(n) 和 h(n)h(n)（估计代价）

当 h(n)=0h(n) = 0 时，A* 退化为 Dijkstra。

  1. h(n) 的正确性条件？
查看答案

h(n) 必须是可采纳的，即：

h(n)≤h∗(n)h(n) \le h^*(n)

其中 h∗(n)h^*(n) 是从 n 到终点的实际最短距离。

也就是说，h(n) 不能高估实际代价。

  1. 什么时候 A* 退化为 Dijkstra？
查看答案

当 h(n)=0h(n) = 0 时，A* 退化为 Dijkstra。

此时 f(n)=g(n)+0=g(n)f(n) = g(n) + 0 = g(n)，只考虑实际代价，不使用启发信息。

易错点

⚠️ 注意：

  1. h(n) 不能高估
  2. h(n)=0 时退化为 Dijkstra
  3. A* 通常比 Dijkstra 快
  4. 启发函数设计是关键