为什么的*指数在内存中的复杂性？ [英] Why is the complexity of A* exponential in memory?

问题描述

维基百科上的A *的复杂以下（链接这里）说：

Wikipedia says on A* complexity the following (link here):

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

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:

假设我们探索节点A，与继任者B，C和D.然后，我们添加B，C和D，以开放的节点列表，并附以参照，我们移动从打开节点到闭合节点

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.

如果在一段时间内，我们发现另一个路径给B（例如，通过Q），即比通过甲路径越好，则所有需要的是改变B的参考甲指向Q和更新其实际成本，G（和逻辑F）。

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).

因此​​，如果我们存储在一个节点的名称，其指的节点名，和它的G，H，和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".

推荐答案

A *是广度优先搜索，这是指数在内存中的复杂性对于解决方案的长度只是一个引导的版本。

A* is just a guided version of breadth-first search, which is exponential in memory complexity with respect to the length of the solution.

在使用恒定的启发，A *将成为一个正常的广度优先搜索;统一成本搜索精确。

When using a constant heuristic, A* will become a normal breadth-first search; uniform cost search to be exact.

在使用最佳启发式，A *将是 O（N）中，如果我们忽略了启发式计算本身的复杂性，空间和时间复杂度。同样 N 是解决路径的长度。

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. Again n is the length of the solution path.

这篇关于为什么的*指数在内存中的复杂性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！