维基百科关于 A* 复杂度的说法如下（链接在这里 http://en.wikipedia.org/wiki/A*_search_algorithm):
比当时更成问题
复杂度是A*的内存使用量。在
最坏的情况，也必须记住
指数数量的节点。
我不认为这是正确的，因为：
假设我们探索节点 A，以及后继节点 B、C 和 D。然后我们将 B、C 和 D 添加到开放节点列表中，每个节点都附有对 A 的引用，然后将 A 从开放节点移动到封闭节点节点。
如果在某个时候我们找到另一条通往 B 的路径（例如，通过 Q），该路径比通过 A 的路径更好，那么所需要做的就是将 B 对 A 的引用更改为指向 Q 并更新其实际成本 g (逻辑上是f)。
因此，如果我们在节点中存储其名称、引用节点名称以及 g、h 和 f 分数，那么存储的最大节点数就是图中的实际节点数，不是吗？我真的不明白为什么算法在任何时候都需要在内存中存储一定数量的节点，这些节点的数量与最佳（最短）路径的长度呈指数关系。
有人可以解释一下吗？
edit据我现在阅读您的答案了解到，我是从错误的问题角度进行推理的。我认为理所当然given图，而指数复杂度是指概念性的仅由“分支因子”定义的图。
A* 只是广度优先搜索的引导版本，其内存复杂度相对于解决方案的长度呈指数增长。
当使用常量启发式时，A*将成为普通的广度优先搜索；准确地说，是统一成本搜索。
当使用最优启发式时，A* 将是O(n)如果我们忽略启发式计算本身的复杂性，那么空间和时间复杂度都会增加。再次n是解路径的长度。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
