为什么A*的复杂度在内存中是指数级的？
维基百科关于 A* 复杂度的说法如下（链接此处）：
问题比当时还多 复杂度是A*的内存使用量。在 最坏的情况，也必须记住 节点数量呈指数级增长。
我不认为这是正确的，因为：
假设我们探索节点 A，以及后继者 B、C 和 D。然后我们将 B、C 和 D 添加到开放节点列表中，每个节点都附有对 A 的引用，然后我们将 A 从开节点移动到闭节点。
如果在某个时候我们找到另一条通往 B 的路径（例如，通过 Q），该路径比通过 A 的路径更好，那么所需要做的就是将 B 对 A 的引用更改为指向 Q 并更新其实际成本 g (逻辑上是f)。
因此，如果我们在节点中存储其名称、引用节点名称以及 g、h 和 f 分数，那么存储的最大节点数就是图中的实际节点数，不是吗？我真的不明白为什么算法在任何时候都需要在内存中存储一定数量的节点，这些节点的数量与最佳（最短）路径的长度呈指数关系。
有人可以解释一下吗？
编辑 据我所知，现在阅读您的答案时，我是从错误的问题角度进行推理的。我认为给定的图是理所当然的，而指数复杂度是指仅由“分支因子”定义的概念图。
Wikipedia says on A* complexity the following (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.
I fail to see this is correct because:
Say we explore node A, with successors B, C, and D. Then we add B, C, and D to the list of open nodes, each accompanied by a reference to A, and we move A from the open nodes to the closed nodes.
If at some time we find another path to B (say, via Q), that is better than the path through A, then all that is needed is to change B's reference to A to point to Q and update its actual cost, g (and logically f).
Therefore, if we store in a node its name, its referring node name, and its g, h, and f scores, then the maximum amount of nodes stored is the actual amount of nodes in the graph, isn't it? I really cannot see why at any time the algorithm would need to store an amount of nodes in memory that is exponential to the length of the optimal (shortest) path.
Could someone please explain?
edit As I understand now reading your answers, I was reasoning from the wrong viewpoint of the problem. I took for granted a given graph, whereas the exponential complexity refers to a an conceptual graph that is defined solely by a "branching factor".
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
A* 只是广度优先搜索的引导版本，其内存复杂度相对于解决方案的长度呈指数增长。
当使用常量启发式时，A*将成为普通的广度优先搜索；准确地说，是统一成本搜索。
当使用最优启发式时，如果我们忽略启发式计算本身的复杂度，A* 的空间和时间复杂度都将是
O(n)。同样，n是解决方案路径的长度。A* is just a guided version of breadth-first search, which is exponential in memory complexity with respect to the length of the solution.
When using a constant heuristic, A* will become a normal breadth-first search; uniform cost search to be exact.
When using the optimal heuristic, A* will be
O(n)in both space and time complexity if we disregard the complexity of the heuristic calculation itself. Againnis the length of the solution path.我认为当你回溯到节点 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 是搜索的深度。
I think the exponential-ness comes into play when you backtrack to node B to expand it, but then backtrack to node C to expand it, and then backtrack to node D. Now we have to keep track of all the children of nodes A, B, C, and D.
The backtracking is based on the cost of the edges to move to the next node, so this is a real possibility, but is the worse case.
If each node has exactly 2 children off of it, and each node has the same cost, then the equation is 2^n, where n is the depth of the search so far.
For example, you start off with node 0. 0 has 2 children 00 and 01. 00 has 2 children 000 and 001. At the worse case with a depth of 4 the equation is 2^4, where 2 is the number of children each node has and 4 is the depth of the search.
我不是专家，但我研究了维基百科文章一段时间，我的解释就是这个（希望我已经很好地理解了:)
比如说，我们有一个 4x4 的节点矩阵。
A、B、C、D 是我们在给定时间可以采取的方向（北、南、东、西）
A*算法开始搜索。
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
直流
队列：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.autonlab.org/tutorials/astar08.pdf，幻灯片 15
I am not an expert, but I studied the Wikipedia article for a while and my explanation would be this one (hope i have understood it well :)
Say, we have a 4x4 matrix of nodes.
A,B,C,D are the directions we can take at a given time (North,South,East,West)
The A* algorithm starts searching.
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
The goal is reached but there are still other possibilities to consider.
D
Queue: B,C,AB,AC,AD,AAB,AAC,AAD
DC
Queue: B,C,AB,AC,AD,AAB,AAC,AAD,DA,DB,DD
DCA
Queue: B,C,AB,AC,AD,AAB,AAC,AAD,DA,DB,DD,DCB,DCC,DCD
DCAB-->Goal
Queue: B,C,AB,AC,AD,AAB,AAC,AAD,DA,DB,DD,DCB,DCC,DCD,DCAA,DCAC,DCAD
Etc etc
As you can see, for every step taken, three more nodes are added to the queue.
Since A* follows only acyclic paths [1], the maximum number of steps per route is 15.
The max number of possible routes in this case is 3^15, or directions^nodes.
Since every route has 15 steps,the worst case steps taken is 15*3^15.
In the absolute worst case, every step ever taken is "wrong".
In that case 3*15*3^15 nodes are in the queue before finding the answer.
So the worst case amount of nodes that needs to be kept in memory is a constant, to the power of the number of nodes available. In other words the memory use is exponential to the amount of nodes.
[1] http://www.autonlab.org/tutorials/astar08.pdf, slide 15