一、A星算法概述：路径规划问题背景、算法发展历史、核心思想与适用场景

1.1 路径规划问题背景——我们到底在解决什么问题？

先聊聊路径规划。说白了，就是「从A点到B点，怎么走最划算」。

我刚开始做嵌入式项目时，遇到过一个移动机器人避障的活儿。那时候我天真地以为，只要知道起点和终点，画条直线不就完了？结果机器人一头撞在墙上，电池都撞飞了。嗯，现实没那么简单。

路径规划的核心挑战有三个：

• 环境未知或部分已知——地图可能是动态的，障碍物会移动
• 资源受限——嵌入式平台的内存、算力、功耗都有限
• 实时性要求——你想想看，自动驾驶的车如果规划路径要算5秒钟，那车早就撞上了

所以，我们需要一种算法：能在有限资源下，快速找到一条从起点到终点的最优或近似最优路径。这就是A星算法登场的背景。

1.2 A星算法发展历史——从Dijkstra到启发式搜索

讲A星之前，得先提它的两位前辈。

1956年，Edsger Dijkstra提出了Dijkstra算法。这哥们儿很猛，他的算法能保证找到最短路径。但代价是什么？它像个无头苍蝇一样，从起点开始一圈一圈往外扩散，直到碰到终点。我做过测试，在一个1000×1000的网格上，Dijkstra可能要遍历几十万个节点。在嵌入式平台上，这简直是灾难。

1968年，Peter Hart、Nils Nilsson和Bertram Raphael三位大佬提出了A星算法。他们的核心贡献是什么？加了一个「启发式函数」。说白了，就是给算法一个「方向感」——告诉它「终点大概在那边，你先往那个方向试试」。

我记得第一次读到A星的原始论文时，心里就一个想法：这思路太聪明了。它不像Dijkstra那样盲目扩散，而是用估价函数f(n) = g(n) + h(n)来引导搜索方向。

• g(n)：从起点到当前节点n的实际代价
• h(n)：从当前节点n到终点的估计代价（启发式函数）
• f(n)：总估价，算法优先扩展f(n)最小的节点

后来A星被不断改进。比如1985年的D*算法（动态A星），专门处理环境变化的情况。再比如2000年后的跳点搜索（JPS），在网格地图上大幅减少了需要扩展的节点数。这些我都会在后面的章节详细讲。

1.3 算法核心思想——f(n) = g(n) + h(n) 到底在说什么？

A星的核心思想，用一句话概括就是：「既要看走过的路，也要看没走过的路」。

咱们拆开来看：

• g(n) 是「已经付出的代价」。比如从起点走到当前格子，走了5步，那g(n)=5。这部分是确定的，不会变。
• h(n) 是「预估还要付出的代价」。比如从当前格子到终点，直线距离是10米，那h(n)=10。这部分是估计值，不一定准。
• f(n) 是「总代价的估计值」。算法每次从开放列表中选f(n)最小的节点来扩展。

你可能会问：h(n)怎么选？选错了会怎样？

嗯，这里有个关键点：

h(n) 的情况	结果
h(n) = 0	A星退化为Dijkstra，保证最优但慢
h(n) ≤ 实际代价	保证找到最短路径，效率取决于h(n)的准确性
h(n) > 实际代价	可能找不到最短路径，但搜索更快
h(n) = 实际代价	完美情况，直接沿着最优路径走，不绕路

我曾经在一个仓储机器人项目里，把h(n)设成了曼哈顿距离。结果发现机器人走的路径总是「拐直角弯」，虽然距离最短，但实际运动起来反而更慢。后来我改成欧几里得距离，路径更平滑，整体效率反而提升了12%。

1.4 适用场景——A星能用在哪？不能用在哪？

A星不是万能的。我见过有人硬把A星往所有路径规划问题上套，结果碰了一鼻子灰。

适合A星的场景：

• 静态或半静态环境——地图变化不频繁，比如室内导航、游戏AI寻路
• 网格化地图——比如2D栅格地图、3D体素地图
• 需要最优路径——比如AGV小车路径规划、无人机航线规划
• 中等规模问题——节点数在几千到几万之间，嵌入式平台能扛得住

不适合A星的场景：

• 高动态环境——障碍物每秒都在变，A星每次都要重新规划，不如用D*或RRT
• 超大规模地图——几百万个节点，A星的内存开销直接爆炸
• 连续空间——不是离散网格，A星没法直接处理
• 实时性要求极高——比如毫秒级响应，A星可能扛不住

你想想看，一个扫地机器人，地图就几百个格子，用A星正合适。但如果是自动驾驶汽车，城市道路几万个节点，还不断有行人、车辆出现，A星就不够用了。这时候得用混合算法——A星做全局规划，局部用DWA或者TEB做实时避障。

1.5 一个简单的A星代码框架——先感受一下

虽然后面章节会详细讲实现，但这里先给个框架，让你对A星有个直观印象：

// A星算法核心框架（伪代码）
typedef struct {
    int x, y;          // 节点坐标
    int g;             // 起点到当前节点的代价
    int h;             // 当前节点到终点的估计代价
    int f;             // g + h
    Node* parent;      // 父节点指针
} Node;

Node* a_star_search(Node* start, Node* goal, GridMap* map) {
    // 1. 初始化开放列表和关闭列表
    PriorityQueue open_list;
    HashSet closed_list;
    
    // 2. 将起点加入开放列表
    start->g = 0;
    start->h = heuristic(start, goal);
    start->f = start->g + start->h;
    open_list.push(start);
    
    // 3. 主循环
    while (!open_list.empty()) {
        // 取出f值最小的节点
        Node* current = open_list.pop();
        
        // 到达终点？
        if (current == goal) {
            return reconstruct_path(current);
        }
        
        // 加入关闭列表
        closed_list.add(current);
        
        // 扩展邻居节点
        for (each neighbor of current) {
            if (closed_list.contains(neighbor)) continue;
            if (!map->is_walkable(neighbor)) continue;
            
            int tentative_g = current->g + cost(current, neighbor);
            
            if (!open_list.contains(neighbor)) {
                neighbor->g = tentative_g;
                neighbor->h = heuristic(neighbor, goal);
                neighbor->f = neighbor->g + neighbor->h;
                neighbor->parent = current;
                open_list.push(neighbor);
            } else if (tentative_g < neighbor->g) {
                // 找到更优路径，更新
                neighbor->g = tentative_g;
                neighbor->f = neighbor->g + neighbor->h;
                neighbor->parent = current;
                open_list.update(neighbor);  // 重新排序
            }
        }
    }
    
    // 4. 没找到路径
    return NULL;
}

这段代码虽然简单，但已经包含了A星的核心逻辑。后面我会带着你一步步优化它——从内存管理到数据结构选型，从启发式函数设计到并行化加速。每一行代码我都会解释为什么这么写，以及在嵌入式平台上有什么坑。

好了，这一章就到这里。下一章我会详细讲A星的数据结构设计——开放列表、关闭列表、节点表示，这些在嵌入式平台上都有讲究。咱们到时候见。