algorithm - 为什么A*的复杂度在内存中呈指数级增长？

Question

维基百科对 A* 复杂度的描述如下 ( link here ):

More problematic than its time complexity is A*’s memory usage. In the worst case, it must also remember an exponential number of nodes.

我看不出这是正确的，因为:

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

如果在某个时候我们发现了另一条通往 B 的路径(例如，通过 Q)，这比通过 A 的路径更好，那么所需要做的就是将 B 对 A 的引用更改为指向 Q 并更新其实际成本, g(逻辑上也是 f)。

因此，如果我们在节点中存储它的名称、它的引用节点名称以及它的 g、h 和 f 分数，那么存储的最大节点数量就是图中的实际节点数量，不是吗？我真的不明白为什么算法在任何时候都需要在内存中存储一​​定数量的节点，这些节点数量与最佳(最短)路径的长度成指数关系。

谁能解释一下？

---

编辑 据我了解，现在阅读您的回答，我是从错误的问题角度进行推理的。我认为给定图是理所当然的，而指数复杂度指的是一个概念图，它仅由“分支因子”定义。

Answer 1

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

当使用常量启发式时，A* 将成为普通的广度优先搜索；准确地说是统一成本搜索。

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