维基百科关于 A* 算法复杂度的描述如下（链接）：

比起时间复杂度，A* 算法更严重的问题是它的内存使用。在最坏的情况下，它也必须记住指数数量的节点。

我不认为这是正确的，因为：

假设我们探索节点 A，其后继节点为 B、C 和 D。然后我们将 B、C 和 D 添加到开放节点列表中，每个节点都附带对 A 的引用，并将 A 从开放节点移动到封闭节点。

如果在某个时刻我们找到另一条通往 B 的路径（例如，通过 Q），该路径比通过 A 的路径更好，那么所需要的只是将 B 对 A 的引用更改为指向 Q，并更新其实际成本 g（以及逻辑上的 f）。

因此，如果我们将节点的名字、其引用节点的名称以及其 g、h 和 f 值存储在一个节点中，那么存储的节点的最大数量就是图中节点的实际数量，不是吗？ 我真的不明白为什么在任何时候算法都需要在内存中存储的节点数量与最佳（最短）路径的长度呈指数关系。

有人能解释一下吗？

编辑 现在我理解了你的回答，我从错误的角度看待问题。我理所当然地认为有一个给定的图，而指数复杂度指的是一个仅由“分支因子”定义的概念图。

回答：

A* 只是广度优先搜索的引导版本，其内存复杂度相对于解决方案的长度呈指数级增长。

当使用恒定启发式算法时，A* 将变成一个普通的广度优先搜索；准确地说是统一成本搜索。

当使用最佳启发式算法时，如果我们忽略启发式计算本身的复杂性，A* 在空间和时间复杂度上都将是 O(n)。同样，n 是解路径的长度。