维基百科在A *复杂性上说以下（link here）：
比时间复杂度更有问题的是A *的内存使用率 . 在最坏的情况下，它还必须记住指数数量的节点 .
我没有看到这是正确的，因为：
假设我们探索节点A，后继B，C和D.然后我们将B，C和D添加到开放节点列表中，每个节点都附带一个A的引用，我们将A从开放节点移动到关闭节点 .
如果在某个时候我们找到另一条到B的路径（比如通过Q），这比通过A的路径更好，那么所需要的只是将B的引用改为A以指向Q并更新其实际成本g（在逻辑上f） .
因此，如果我们在节点中存储其名称，其引用节点名称及其g，h和f分数，那么存储的最大节点数量是图表中的实际节点数量，不是吗？我真的不明白为什么算法在任何时候都需要在内存中存储一定数量的节点，这些节点指向最佳（最短）路径的长度 .
有人可以解释一下吗？
edit 我现在明白了解你的答案，我是从问题的错误观点推理出来的 . 我认为给定的图是理所当然的，而指数复杂性是指仅由"branching factor"定义的概念图 .
3 回答
A *只是广度优先搜索的引导版本，它在内存复杂性方面与解决方案的长度成指数关系 .
当使用常量启发式时，A *将成为普通的广度优先搜索;统一成本搜索准确 .
当使用最优启发式时，如果我们忽略启发式计算本身的复杂性，则A *在空间和时间复杂度方面都将是
O(n). 同样n是解决方案路径的长度 .我认为当你回溯到节点B以扩展它时，指数就会发挥作用，但是然后回溯到节点C以扩展它，然后回溯到节点D.现在我们必须跟踪节点A的所有子节点， B，C和D.
回溯是基于移动到下一个节点的边缘成本，所以这是一个真正的可能性，但是更糟糕的情况 .
如果每个节点正好有2个子节点，并且每个节点具有相同的成本，则方程式为2 ^ n，其中n是到目前为止的搜索深度 .
例如，你从节点0开始.0有2个孩子00和01. 00有2个孩子000和001.在更糟糕的情况下，深度为4，等式是2 ^ 4，其中2是每个孩子的数量node有，4是搜索的深度 .
我不是专家，但我研究维基百科的文章已有一段时间了，我的解释就是这个（希望我已经理解了:)
比如说，我们有一个4x4的节点矩阵 .
A，B，C，D是我们在给定时间可以采取的方向（北，南，东，西）
A *算法开始搜索 .
一个
队列：B，C，D
AA
队列：B，C，D，AB，AC，AD
AAA - >目标
队列：B，C，D，AB，AC，AD，AAB，AAC，AAD
目标已达成，但还有其他可能性需要考虑 .
d
队列：B，C，AB，AC，AD，AAB，AAC，AAD
DC
队列：B，C，AB，AC，AD，AAB，AAC，AAD，DA，DB，DD
DCA
队列：B，C，AB，AC，AD，AAB，AAC，AAD，DA，DB，DD，DCB，DCC，DCD
DCAB - >目标
队列：B，C，AB，AC，AD，AAB，AAC，AAD，DA，DB，DD，DCB，DCC，DCD，DCAA，DCAC，DCAD
等等
如您所见，对于每个步骤，将三个节点添加到队列中 .
由于A *仅遵循非循环路径[1]，因此每条路径的最大步数为15 .
在这种情况下，可能路由的最大数量是3 ^ 15，或方向^节点 .
由于每条路线都有15个步骤，因此最差的步骤是15 * 3 ^ 15 .
在绝对最坏的情况下，所采取的每一步都是"wrong" .
在那种情况下，在找到答案之前，3 * 15 * 3 ^ 15个节点在队列中 .
因此，需要保留在内存中的最坏情况的节点数量是一个常数，与可用节点数量的幂相关 . 换句话说，内存使用是节点数量的指数 .
[1] http://www.autonlab.org/tutorials/astar08.pdf，幻灯片15