19

维基百科关于 A* 复杂性的说法如下（链接在这里）：

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

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

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

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

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

有人可以解释一下吗？

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

4

3 回答 3

36

A* 只是广度优先搜索的引导版本，它的内存复杂度与解的长度呈指数关系。

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

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

于 2009-11-11T15:38:04.740 回答
7

我认为当你回溯到节点 B 来扩展它时，指数性就会发挥作用，然后回溯到节点 C 来展开它，然后回溯到节点 D。现在我们必须跟踪节点 A 的所有子节点， B、C 和 D。

回溯是基于移动到下一个节点的边的成本，所以这是一个真正的可能性，但情况更糟。

如果每个节点恰好有 2 个子节点，并且每个节点的成本相同，则等式为 2^n，其中 n 是到目前为止的搜索深度。

例如，您从节点 0 开始。0 有 2 个子节点 00 和 01。00 有 2 个子节点 000 和 001。在深度为 4 的最坏情况下，等式是 2^4，其中 2 是每个子节点的数量节点有，4 是搜索的深度。

于 2009-11-11T14:27:43.507 回答
2

我不是专家，但我研究了维基百科的文章一段时间，我的解释是这个（希望我理解得很好:)

比如说，我们有一个 4x4 的节点矩阵。
A、B、C、D 是我们在给定时间可以采取的方向（北、南、东、西）
A* 算法开始搜索。

A
Queue: B,C,D
AA
Queue: B,C,D,AB,AC,AD
AAA-->Goal
Queue: 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。
在绝对最坏的情况下，曾经采取的每一步都是“错误的”。
在这种情况下，在找到答案之前，队列中有 3*15*3^15 个节点。
所以最坏情况下需要保存在内存中的节点数量是一个常数，取决于可用节点的数量。换句话说，内存使用与节点数量成指数关系。

[1] http://www.autolab.org/tutorials/astar08.pdf，幻灯片 15

于 2009-11-11T15:32:24.703 回答