代码之家 › 专栏 › 技术社区 › Paul

为什么记忆中指数的复杂性?

a-star complexity-theory graph artificial-intelligence algorithm

17

Paul · 技术社区 · 16 年前

维基百科在一个复杂的问题上说( link here ):

比时间更麻烦复杂性是一种内存使用。在最坏的情况,它也必须记住节点的指数数量。

我没有看到这是正确的,因为:

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

如果在某个时候我们找到另一条到B的路径(例如,通过Q),这比通过A的路径更好,那么所需要的就是将B的引用改为指向Q,并更新它的实际成本G(和逻辑上的F)。

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

有人能解释一下吗?

编辑正如我现在读到你的答案时所理解的,我是从错误的观点来推理问题的。我认为这是理所当然的鉴于图,而指数复杂性是指 概念的 仅由“分支因子”定义的图。

3 回复 | 直到 13 年前

1

31

ziggystar 13 年前

A*只是宽度优先搜索的引导版本,它在内存中的复杂性相对于解决方案的长度是指数级的。

当使用一个恒定的启发式搜索时,A*将成为一个普通的广度优先搜索;统一的成本搜索是精确的。

当使用最佳启发式时,a*将 O(n) 如果我们忽略启发式计算本身的复杂性,那么在空间和时间上都会有复杂性。阿盖恩 n 是解决方案路径的长度。

2

7

Robert Deml 16 年前

我认为当你回溯到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是搜索深度。

3

2

littlegreen 16 年前

我不是专家,但是我研究了一段时间维基百科的文章,我的解释就是这个(希望我已经很好地理解了)。

比如,我们有一个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
直流
队列: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或directions^节点。
因为每条路线都有15个步骤,所以最坏的步骤是15*3^15。
在绝对最坏的情况下,每一步都是“错误的”。
在这种情况下,在找到答案之前,队列中有3*15*3^15个节点。
因此,最坏情况下需要保存在内存中的节点数量是一个常量,等于可用节点数量的幂。换句话说,内存使用是节点数量的指数。

〔1〕 http://www.autonlab.org/tutorials/astar08.pdf 幻灯片15