维基百科在A*复杂性上说如下(链接在这里):
比时间复杂度更有问题的是A*的内存使用率.在最坏的情况下,它还必须记住指数数量的节点.
我没有看到这是正确的,因为:
假设我们探索节点A,后继B,C和D.然后我们将B,C和D添加到开放节点列表中,每个节点都附带一个A的引用,我们将A从开放节点移动到关闭节点.
如果在某个时候我们找到另一条到B的路径(比如通过Q),这比通过A的路径更好,那么所需要的只是将B的引用改为A以指向Q并更新其实际成本g(在逻辑上f).
因此,如果我们在节点中存储其名称,其引用节点名称及其g,h和f分数,那么存储的最大节点数量是图表中的实际节点数量,不是吗？我真的不明白为什么算法在任何时候都需要在内存中存储一定数量的节点,这些节点指向最佳(最短)路径的长度.
有人可以解释一下吗？
编辑正如我现在理解的那样阅读你的答案,我是从问题的错误观点推理出来的.我认为给定的图是理所当然的,而指数复杂性是指仅由"分支因子"定义的概念图.
algorithm complexity-theory artificial-intelligence graph a-star