为什么 A* 在内存中的复杂度是指数级的? [英] 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 添加到开放节点列表中，每个节点都伴随着对 A 的引用，然后我们从开放节点中移动 A到封闭节点.

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)，这比通过 A 的路径更好，那么所需要做的就是将 B 对 A 的引用更改为指向 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.

谁能解释一下?

编辑 正如我现在阅读您的答案所理解的那样，我是从错误的问题角度进行推理的.我认为给定图是理所当然的，而指数复杂度指的是一个概念图，它仅由分支因子"定义.

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.

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