A*搜索算法

一、问题背景

在游戏寻路、地图导航等场景中，我们需要在巨大地图中快速找到一条接近最短的路线。

• Dijkstra 算法能保证最短路径，但搜索方向"盲目"，在超大图上效率低
• 实际应用中，往往不需要绝对最短，只需次优但足够快

A* 算法就是对 Dijkstra 的启发式改进：引入"终点方向估计"，让搜索不再跑偏。

二、从 Dijkstra 到 A*

2.1 Dijkstra 的"跑偏"问题

Dijkstra 按 g(i)（起点到当前点的实际距离）选择下一个扩展点。在地图场景中，这导致搜索可能朝远离终点的方向扩展。

graph LR
  S((S)) -->|1| A((1))
  A -->|1| B((2))
  B -->|1| C((3))
  S -->|4| D((4))
  D -->|1| T((T))

上图中，Dijkstra 会先扩展 1→2→3（离 S 近），但终点 T 在另一侧。

2.2 A* 的改进：引入启发函数

A* 综合考虑两个因素：

每次从优先队列中取 f 值最小的顶点扩展，搜索方向被"拉向"终点。

三、启发函数设计

3.1 曼哈顿距离（推荐）

h(i) = |x_i - x_t| + |y_i - y_t|

• 只涉及加减法和绝对值，计算极快
• 适用于四方向移动的网格地图

3.2 欧几里得距离

h(i) = sqrt((x_i - x_t)² + (y_i - y_t)²)

• 更精确，但涉及开方运算，较慢
• 适用于任意方向移动的场景

3.3 启发函数的约束

h(i) 必须 ≤ 实际最短距离（可采纳性），否则 A* 退化为贪心搜索，可能找不到较优解。

四、算法实现

4.1 与 Dijkstra 的三点区别

4.2 代码实现

public void astar(int s, int t, int[][] coords) {
    int n = graph.length;
    int[] dist = new int[n];
    int[] f = new int[n];
    int[] prev = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    Arrays.fill(f, Integer.MAX_VALUE);

    // 按 f 值排序的小顶堆
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    dist[s] = 0;
    f[s] = heuristic(coords[s], coords[t]);
    pq.offer(new int[]{s, f[s]});

    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int u = cur[0];

        if (u == t) break; // 到达终点即结束

        for (int[] edge : graph[u]) {
            int v = edge[0], w = edge[1];
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                f[v] = dist[v] + heuristic(coords[v], coords[t]);
                prev[v] = u;
                pq.offer(new int[]{v, f[v]});
            }
        }
    }
    // 通过 prev 数组还原路径
}

private int heuristic(int[] a, int[] b) {
    return Math.abs(a[0] - b[0]) + Math.abs(a[1] - b[1]);
}

五、网格地图寻路

游戏中的地图通常抽象为网格图：

• 每个格子 = 一个顶点
• 相邻格子之间连边，权值为 1（或带地形权重）
• 障碍物对应的顶点不可通行

graph TD
  A[0,0] --> B[0,1]
  B --> C[0,2]
  A --> D[1,0]
  D --> E[1,1]
  E --> F[1,2]
  D --> G[2,0]
  G --> H[2,1]
  H --> I[2,2]

在网格图上，A* 用曼哈顿距离作为启发函数，搜索效率远高于 BFS/Dijkstra。

六、A* 的正确性与局限

6.1 为什么不保证最短路径？

A* 在遍历到终点时立即结束，此时终点的 dist 值未必是全局最小。它利用贪心思路，只找"看起来最好"的路径。

6.2 何时退化为 Dijkstra？

当 h(i) = 0（即不使用启发函数）时，f(i) = g(i)，A* 完全退化为 Dijkstra。

6.3 何时找到最短路径？

如果 h(i) 满足一致性（consistency）：h(u) ≤ w(u,v) + h(v)，且终点出队列时才结束，则 A* 也能保证最短路径。

七、应用场景

八、相关算法族

九、总结

A* 的核心公式：f(i) = g(i) + h(i)

• g(i)：已走过的路（确定值）
• h(i)：估计还要走的路（启发值）
• 两者结合，让搜索"有方向感"

设计启发函数时的权衡：h 越大搜索越快，但越容易偏离最优解；h = 0 退化为 Dijkstra。