维基百科在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
由于赋值问题可以以单个矩阵的形式提出,如果numpy具有解决这种矩阵的函数,我就会徘徊.到目前为止,我没有找到.也许你们其中一个人知道numpy/scipy是否有一个赋值问题解决函数？
编辑:同时我在http://www.clapper.org/software/python/munkres/找到了一个python(不是numpy/scipy)实现.我仍然认为numpy/scipy实现可能会快得多,对吧？
这是一年中的那个时候,程序员想要洗牌,以便没有元素存在于其原始位置(至少在荷兰,我们庆祝Sinterklaas并选择吸管来决定谁写一首诗).有人有一个很好的Python 单一声明吗？
那么,输入示例: range(10)
输出示例: [2,8,4,1,3,7,5,9,6,0]
错误的输出将是[2,8,4,1,3,5,7,9,6,0]因为5它处于原始位置.这意味着5人必须为自己写一首诗,这样就不那么有趣了.
编辑许多人只要需要幸运就重复这项任务,并发现事实上解决方案是令人满意的.这是一种糟糕的方法,因为理论上这可能需要很长时间.巴特确实提出了更好的方法,但由于某种原因,我不能把它变成一个oneliner ......
编辑通过oneliner,我的意思是单一陈述.看起来,Python也能够在一行上压缩多个语句.我不知道.目前有非常好的解决方案,只使用分号来模拟单行上的多线行为.因此:"你能在一个声明中做到吗？"