维基百科对 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 分数，那么存储的最大节点数量就是图中的实际节点数量，不是吗？我真的不明白为什么算法在任何时候都需要在内存中存储一定数量的节点，这些节点数量与最佳(最短)路径的长度成指数关系。
谁能解释一下？
编辑 据我了解，现在阅读您的回答，我是从错误的问题角度进行推理的。我认为给定图是理所当然的，而指数复杂度指的是一个概念图，它仅由“分支因子”定义。
最佳答案
A* 只是广度优先搜索的引导版本，它的内存复杂度相对于解决方案的长度呈指数级增长。
当使用常量启发式时，A* 将成为普通的广度优先搜索；准确地说是统一成本搜索。
当使用最优启发式时，如果我们忽略启发式计算本身的复杂性，A* 的空间和时间复杂度都将是 O(n)。同样，n 是解决方案路径的长度。
关于algorithm - 为什么A*的复杂度在内存中呈指数级增长？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1715401/