A* 算法详解：从原理到实现

布莱克605

230人浏览 · 2026-10-22 11:40:34

布莱克605 · 2026-10-22 11:40:34 发布

一、A* 算法是什么

A*（读作 A-star）是一种用于在图中寻找最短路径的启发式搜索算法。它由 Peter Hart、Nils Nilsson 和 Bertram Raphael 于 1968 年提出，是 Dijkstra 算法与贪心最佳优先搜索（Greedy Best-First Search）的结合体。

简单来说，A* 在搜索过程中既考虑已经走过的代价，又考虑距离目标还有多远，从而在保证最优性的前提下大幅减少需要探索的节点数量。它被广泛应用于游戏寻路、地图导航、机器人路径规划等领域。

二、核心思想与评估函数

A* 的核心是下面这个评估函数：

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

g(n)：从起点到当前节点 n 的实际代价（已付出的代价）。
h(n)：从当前节点 n 到目标节点的估计代价，称为启发函数（heuristic）。
f(n)：经过节点 n 到达目标的总代价估计值。

A* 每次从待探索集合（通常称为 open 表）中取出 f(n) 最小的节点进行扩展，因此它总是优先探索“看起来最有希望”的方向。

与其它搜索算法的对比

算法	评估方式	是否保证最优	特点
BFS	按层扩展	是（无权图）	盲目搜索，节点多
Dijkstra	f(n) = g(n)	是	向四周均匀扩散
贪心最佳优先	f(n) = h(n)	否	速度快但可能非最优
A*	f(n) = g(n) + h(n)	取决于 h(n)	兼顾最优性与效率

三、启发函数的性质

A* 能否保证找到最优解，关键在于启发函数 h(n) 的性质。

1. 可采纳性（Admissible）

如果对所有节点 n，都有 h(n) ≤ h*(n)（h*(n) 为 n 到目标的真实最小代价），则称 h(n) 是可采纳的。可采纳的启发函数永远不会高估真实代价，此时 A* 保证找到最优解。

2. 一致性（Consistent / Monotonic）

如果对任意相邻节点 n 和 n'，满足：

h(n) ≤ c(n, n') + h(n')

其中 c(n, n') 是 n 到 n' 的实际边代价，则称 h(n) 是一致的。一致性比可采纳性更强，满足一致性的启发函数可以保证每个节点最多被扩展一次，无需重复处理。

3. 常见启发函数

曼哈顿距离：h = |x1 - x2| + |y1 - y2|，适用于只能上下左右移动的网格。
欧几里得距离：h = √((x1-x2)² + (y1-y2)²)，适用于可任意方向移动的场景。
切比雪夫距离：h = max(|x1-x2|, |y1-y2|)，适用于允许八方向移动的网格。

四、算法流程

A* 的典型实现使用两个集合：

open 表：待扩展的节点集合，通常用优先队列（最小堆）实现，按 f(n) 排序。
closed 表：已扩展过的节点集合，避免重复处理。

具体步骤如下：

将起点加入 open 表，其 g 值为 0，f 值为 h(起点)。
若 open 表为空，则搜索失败，无可行路径。
从 open 表中取出 f 值最小的节点作为当前节点。
若当前节点是目标节点，则回溯父节点，得到最优路径，算法结束。
将当前节点移入 closed 表。
遍历当前节点的所有邻居：
- 若邻居在 closed 表中，跳过。
- 计算从起点经当前节点到邻居的新 g 值。
- 若邻居不在 open 表中，或新 g 值更小，则更新其 g 值、f 值和父节点，并加入 open 表。
返回第 2 步继续循环。

五、代码实现

下面给出一个基于网格地图的 C++ 实现，使用曼哈顿距离作为启发函数。

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm>
#include <cmath>
#include <string>

struct Node {
    int x, y;
    double g, h, f;
    Node* parent;

    Node(int x, int y, Node* parent = nullptr)
        : x(x), y(y), g(0), h(0), f(0), parent(parent) {}
};

// 优先队列按 f 值从小到大排序
struct Compare {
    bool operator()(const Node* a, const Node* b) const {
        return a->f > b->f;
    }
};

static const int DIRS[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

double heuristic(int x1, int y1, int x2, int y2) {
    return std::abs(x1 - x2) + std::abs(y1 - y2);
}

std::vector<std::pair<int, int>> buildPath(Node* node) {
    std::vector<std::pair<int, int>> path;
    while (node != nullptr) {
        path.emplace_back(node->x, node->y);
        node = node->parent;
    }
    std::reverse(path.begin(), path.end());
    return path;
}

std::vector<std::pair<int, int>> aStar(const std::vector<std::vector<int>>& grid,
                                       std::pair<int, int> start,
                                       std::pair<int, int> goal) {
    int rows = grid.size();
    int cols = grid[0].size();

    std::priority_queue<Node*, std::vector<Node*>, Compare> open;
    std::unordered_set<std::string> closed;

    Node* startNode = new Node(start.first, start.second);
    startNode->g = 0;
    startNode->h = heuristic(start.first, start.second, goal.first, goal.second);
    startNode->f = startNode->h;
    open.push(startNode);

    while (!open.empty()) {
        Node* current = open.top();
        open.pop();

        std::string key = std::to_string(current->x) + "," + std::to_string(current->y);

        if (current->x == goal.first && current->y == goal.second) {
            return buildPath(current);
        }

        if (closed.count(key)) continue;
        closed.insert(key);

        for (const auto& dir : DIRS) {
            int nx = current->x + dir[0];
            int ny = current->y + dir[1];

            if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue;
            if (grid[nx][ny] == 1) continue; // 1 表示障碍物
            if (closed.count(std::to_string(nx) + "," + std::to_string(ny))) continue;

            Node* neighbor = new Node(nx, ny, current);
            neighbor->g = current->g + 1;
            neighbor->h = heuristic(nx, ny, goal.first, goal.second);
            neighbor->f = neighbor->g + neighbor->h;
            open.push(neighbor);
        }
    }
    return {}; // 无路径
}

int main() {
    std::vector<std::vector<int>> grid = {
        {0, 0, 0, 0, 0},
        {0, 1, 1, 0, 0},
        {0, 0, 0, 0, 0},
        {0, 0, 1, 1, 0},
        {0, 0, 0, 0, 0}
    };

    auto path = aStar(grid, {0, 0}, {4, 4});
    for (const auto& p : path) {
        std::cout << "(" << p.first << ", " << p.second << ")" << std::endl;
    }
    return 0;
}

上述代码中，grid 用 0 表示可通行、1 表示障碍物。算法从起点出发，每次扩展 f 值最小的节点，最终回溯得到从起点到终点的最短路径。