4. 核心数据结构：开放列表与关闭列表、节点类设计、F=G+H 代价函数详解

好，咱们今天来啃A*算法里最核心的几块骨头。说实话，很多初学者把A*想得太玄乎，其实说白了，它就是一套“怎么选路、怎么记路、怎么算账”的规则。今天我就带你把这套规则拆开揉碎了讲清楚。

4.1 开放列表（Open List）与关闭列表（Closed List）

这两个列表，是A*算法的“记事本”和“垃圾桶”。

开放列表（Open List）：存放“待考察”的节点。这些节点是“候选者”，算法会从里面挑一个最有可能的继续探索。我个人习惯用优先队列（最小堆）来实现它，因为每次取最小F值的节点时，效率最高。

关闭列表（Closed List）：存放“已考察”的节点。一旦某个节点被选中并扩展了它的邻居，它就会被扔进关闭列表。嗯，这里要注意：关闭列表里的节点，算法不会再回头去看它。除非你用的是变种算法（比如ARA*），否则别动它。

我在项目中遇到过一个问题：如果地图很大，Open List里塞了几万个节点，每次取最小值的效率就很重要了。用数组遍历？太慢了。用二叉堆？快很多。我建议你一开始就用堆实现，别偷懒。

4.2 节点（Node）类的设计

节点是A*算法里的“最小单元”。它代表地图上的一个位置。怎么设计这个类？我直接给你看一个我常用的模板：

class Node:
    def __init__(self, x, y):
        self.x = x          # 坐标X
        self.y = y          # 坐标Y
        self.g = float('inf')  # 从起点到当前节点的实际代价
        self.h = 0.0        # 从当前节点到目标节点的估计代价
        self.f = 0.0        # f = g + h
        self.parent = None  # 父节点指针，用于回溯路径
        self.is_walkable = True  # 是否可通行

这里有几个关键点：

• g值初始化为无穷大：这样在更新时，第一次计算一定会比无穷大小，保证能正确赋值。
• parent指针：这是路径回溯的关键。找到目标后，顺着parent一路往回走，就能得到完整路径。
• is_walkable：标记障碍物。我见过有人把这个放在地图类里，但放在节点里更灵活，每个节点可以独立控制。

4.3 F = G + H 代价函数详解

这个公式是整个A*算法的灵魂。你想想看，为什么A*比Dijkstra快？就是因为多了这个H值。

G值（实际代价）：从起点走到当前节点，已经花掉的“路费”。比如走一步代价是1，那走了5步，G就是5。

H值（启发式估计）：从当前节点到目标节点，估计还要花多少“路费”。注意是估计，不是精确值。常用的估计方法有：

启发函数	适用场景	公式
曼哈顿距离	只能上下左右移动（四方向）	|x1-x2| + |y1-y2|
欧几里得距离	可以任意方向移动（八方向）	sqrt((x1-x2)² + (y1-y2)²)
切比雪夫距离	允许对角线移动且代价相同	max(|x1-x2|, |y1-y2|)

F值（总代价）：F = G + H。算法每次从Open List里挑F值最小的节点去扩展。

为什么会这样设计？说白了，G保证了路径的“真实性”，H保证了路径的“方向性”。没有G，算法会乱跳；没有H，算法就退化成Dijkstra，效率低很多。

4.4 知识体系结构图

下面这张图，帮你把今天讲的内容串起来：

4.5 实战中的避坑指南

最后，分享几个我踩过的坑：

• Open List重复节点问题：同一个节点可能被多个邻居加入Open List。我建议在加入前检查一下，如果已经在Open List里且新G值更小，就更新它；否则忽略。
• H值选择不当：如果H值总是0，A*就变成了Dijkstra。如果H值太大（高估），算法可能找不到最短路径。我一般用曼哈顿距离，简单可靠。
• 忘记重置节点状态：在多轮规划中，一定要重置所有节点的g值和parent。否则上一轮的残留数据会污染本轮计算。

---