Pau*_*aul 18 algorithm complexity-theory artificial-intelligence graph a-star
维基百科在A*复杂性上说如下(链接在这里):
比时间复杂度更有问题的是A*的内存使用率.在最坏的情况下,它还必须记住指数数量的节点.
我没有看到这是正确的,因为:
假设我们探索节点A,后继B,C和D.然后我们将B,C和D添加到开放节点列表中,每个节点都附带一个A的引用,我们将A从开放节点移动到关闭节点.
如果在某个时候我们找到另一条到B的路径(比如通过Q),这比通过A的路径更好,那么所需要的只是将B的引用改为A以指向Q并更新其实际成本g(在逻辑上f).
因此,如果我们在节点中存储其名称,其引用节点名称及其g,h和f分数,那么存储的最大节点数量是图表中的实际节点数量,不是吗？我真的不明白为什么算法在任何时候都需要在内存中存储一定数量的节点,这些节点指向最佳(最短)路径的长度.
有人可以解释一下吗？
编辑正如我现在理解的那样阅读你的答案,我是从问题的错误观点推理出来的.我认为给定的图是理所当然的,而指数复杂性是指仅由"分支因子"定义的概念图.
zig*_*tar 34
A*只是广度优先搜索的引导版本,它在内存复杂性方面与解决方案的长度成指数关系.
当使用常量启发式时,A*将成为普通的广度优先搜索; 统一成本搜索准确.
当使用最优启发式时,O(n)如果我们忽略启发式计算本身的复杂性,则A*将具有空间和时间复杂度.再次n是解决方案路径的长度.
我认为当你回溯到节点B以扩展它时,指数就会发挥作用,但是然后回溯到节点C以扩展它,然后回溯到节点D.现在我们必须跟踪节点A的所有子节点, B,C和D.
回溯是基于移动到下一个节点的边缘成本,所以这是一个真正的可能性,但是更糟糕的情况.
如果每个节点正好有2个子节点,并且每个节点具有相同的成本,则方程式为2 ^ n,其中n是到目前为止的搜索深度.
例如,你从节点0开始.0有2个孩子00和01. 00有2个孩子000和001.在更糟糕的情况下,深度为4,等式是2 ^ 4,其中2是每个孩子的数量node有,4是搜索的深度.