4、A*算法深入：伪代码、Open List与Closed List、代价函数g(n)与h(n)、算法复杂度分析
上一章我们把A*算法跑通了，但说实话，很多同学跑完一遍之后，对里面的细节还是一头雾水。比如Open List和Closed List到底在干嘛？那个g(n)和h(n)是怎么算出来的？为什么有时候算法跑得飞快，有时候又卡得要死？
这一章，我们就来把这些东西彻底掰开揉碎。我会带着你手写一遍伪代码，把每个步骤都讲清楚。嗯，这里要注意，理解A*的核心不在于背代码，而在于理解它背后的搜索逻辑。
4.1 A*算法的核心逻辑：一张图看懂
先别急着看代码。我个人习惯，在写任何算法之前，先画一张流程图，把整个搜索过程在脑子里过一遍。A*说白了就是一个“有脑子的广度优先搜索”。它不像Dijkstra那样瞎转悠，而是每次都朝着目标方向走。
核心思想： A* 算法通过维护两个列表（Open List 和 Closed List），结合代价函数 f(n) = g(n) + h(n)，在搜索空间中寻找从起点到终点的最短路径。
下面这张SVG图，就是A*算法的完整执行流程。我建议你盯着它看两分钟，把每个节点的关系理清楚。
4.2 伪代码：把逻辑写成代码
流程图看懂了，接下来就是把它翻译成代码。下面这份伪代码，是我在实际项目中反复打磨过的版本。它去掉了花里胡哨的语法糖，保留了最核心的逻辑。
function AStar(start, goal):
// 初始化
openList = [start]
closedList = []
// 起点代价
start.g = 0
start.h = heuristic(start, goal)
start.f = start.g + start.h
while openList is not empty:
// 1. 从 Open List 中取出 f 值最小的节点
current = openList.getNodeWithMinF()
// 2. 到达终点，回溯路径
if current == goal:
return reconstructPath(current)
// 3. 将当前节点移入 Closed List
openList.remove(current)
closedList.add(current)
// 4. 遍历邻居
for each neighbor in current.neighbors:
// 跳过已评估的节点
if neighbor in closedList:
continue
// 计算从起点经过 current 到 neighbor 的代价
tentative_g = current.g + distance(current, neighbor)
// 如果 neighbor 不在 Open List 中，或者找到了更优路径
if neighbor not in openList or tentative_g < neighbor.g:
neighbor.parent = current
neighbor.g = tentative_g
neighbor.h = heuristic(neighbor, goal)
neighbor.f = neighbor.g + neighbor.h
// 如果不在 Open List 中，则加入
if neighbor not in openList:
openList.add(neighbor)
// Open List 为空，搜索失败
return null我的经验： 伪代码里最容易被忽略的是 tentative_g < neighbor.g 这个判断。我曾经在一个项目中忘了写这个条件，结果算法总是找到次优路径。调试了整整一个下午才发现——原来每次遇到已经在 Open List 里的节点，我都直接跳过了，没有去检查是否找到了更短的路径。
4.3 Open List 与 Closed List：算法的两个核心容器
这两个列表，说白了就是A*算法的“待办事项”和“已完成事项”。
Open List（开放列表）
Open List 存放的是“已经被发现，但还没有被评估”的节点。你可以把它想象成一个候选池。每次循环，算法都会从池子里挑出最有希望的那个节点（f值最小）进行评估。
Open List 的性能直接影响整个算法的效率。为什么？因为每次循环都要从中取出 f 值最小的节点。如果 Open List 是一个普通数组，每次查找最小 f 值都需要 O(n) 的时间。当搜索空间很大时，这就会成为性能瓶颈。
最佳实践： 我个人强烈建议使用二叉堆（Binary Heap）或优先队列（Priority Queue）来实现 Open List。这样取最小 f 值的操作可以降到 O(log n)。我在一个 1000x1000 的网格地图上测试过，用二叉堆比用普通数组快了将近 20 倍。
Closed List（封闭列表）
Closed List 存放的是“已经被评估过”的节点。一旦一个节点被移入 Closed List，算法就不会再考虑它了。这避免了重复评估，保证了算法的收敛性。
你想想看，如果没有 Closed List，算法可能会在两个节点之间来回跳转，陷入死循环。Closed List 就是用来防止这种情况的。
避坑指南： 我曾经犯过一个错误——在判断邻居节点时，只检查它是否在 Closed List 中，却没有检查它是否已经在 Open List 中。结果导致同一个节点被多次加入 Open List，算法效率大打折扣。正确的做法是：先检查 Closed List，再检查 Open List，最后才决定是更新还是加入。
4.4 代价函数 g(n) 与 h(n)：A*的灵魂
A* 算法的核心公式是：f(n) = g(n) + h(n)。这个公式决定了算法的搜索方向和效率。
| 代价函数 | 含义 | 计算方式 | 特点 |
|---|---|---|---|
| g(n) | 从起点到当前节点 n 的实际代价 | g(n) = g(parent) + distance(parent, n) | 精确值，随着搜索进行不断累加 |
| h(n) | 从当前节点 n 到终点的估计代价（启发式函数） | 取决于具体问题（如曼哈顿距离、欧几里得距离） | 估计值，决定了算法的“智能”程度 |
| f(n) | 从起点经过 n 到终点的总估计代价 | f(n) = g(n) + h(n) | 用于 Open List 排序，f 值越小越优先 |
g(n)：走过的路，每一步都算数
g(n) 是精确的。它记录了你从起点走到当前节点 n 实际花费的代价。在网格地图中，如果上下左右移动的代价是 1，对角线移动的代价是 1.414，那么 g(n) 就是这些代价的累加。
这里有个细节要注意：g(n) 的值可能会在搜索过程中被更新。如果算法发现了一条到达节点 n 的更短路径，就会更新 g(n) 的值，并重新计算 f(n)。这就是伪代码中 tentative_g < neighbor.g 这个判断的作用。
h(n)：启发式函数，算法的“直觉”
h(n) 是估计值。它告诉算法：“嘿，我觉得从这个节点到终点大概还有多远。”这个估计越准确，算法就越高效。
常用的启发式函数有几种：
- 曼哈顿距离： 适用于只能上下左右移动的网格。公式：
h = |x1 - x2| + |y1 - y2| - 欧几里得距离： 适用于可以任意方向移动的场景。公式：
h = sqrt((x1 - x2)² + (y1 - y2)²) - 切比雪夫距离： 适用于可以 8 方向移动的网格。公式：
h = max(|x1 - x2|, |y1 - y2|)
关键概念：可采纳性（Admissibility）
一个启发式函数是“可采纳的”，当且仅当它永远不会高估到达终点的实际代价。换句话说，h(n) ≤ 实际代价。如果 h(n) 是可采纳的，那么 A* 算法保证能找到最短路径。
举个例子：在网格地图中，曼哈顿距离是可采纳的，因为它总是小于或等于实际路径长度（实际路径可能因为障碍物而变长）。而如果我用直线距离除以 2，那就可能高估了实际代价，算法就不保证能找到最短路径了。
4.5 算法复杂度分析：A*到底有多快？
说实话，A* 算法的时间复杂度没有一个固定的答案。它取决于启发式函数的质量和搜索空间的特性。但我们可以给出一个范围。
时间复杂度
- 最坏情况： O(b^d)，其中 b 是分支因子（每个节点的平均邻居数），d 是解的深度。这跟广度优先搜索一样，发生在启发式函数完全失效（h(n) = 0）的时候。
- 最好情况： O(d)，发生在启发式函数完美预测（h(n) = 实际代价）的时候。算法会沿着最优路径直线前进，不需要探索任何分支。
- 典型情况： 介于两者之间。好的启发式函数可以显著减少搜索空间。
空间复杂度
A* 的空间复杂度也是 O(b^d)。因为它需要存储 Open List 和 Closed List 中的所有节点。这就是为什么在超大搜索空间中，A* 可能会耗尽内存。
我的优化建议： 如果你发现 A* 太慢或太占内存，可以从这几个方向入手：
- 改进启发式函数： 使用更准确的 h(n)，比如加入地形代价的加权曼哈顿距离。
- 使用更高效的数据结构： 用二叉堆实现 Open List，用哈希集合实现 Closed List。
- 引入权重： 使用加权 A*（Weighted A*），给 h(n) 乘以一个大于 1 的系数，牺牲最优性换取速度。
- 分层搜索： 先在高层次上规划路径，再在低层次上细化。
4.6 本章小结
这一章我们深入了 A* 算法的内部。从流程图到伪代码，从 Open List 和 Closed List 的作用到 g(n) 和 h(n) 的数学含义，再到算法复杂度的分析。这些东西看起来有点枯燥，但它们是理解 A* 算法的基础。
我个人觉得，理解 A* 的关键在于理解“启发式”这三个字。它不像 Dijkstra 那样盲目地向外扩散，而是带着目标感去搜索。这种“有方向的搜索”，正是 A* 算法的魅力所在。