A*时间复杂度

Question

维基百科在A*的复杂性上说:

A*的时间复杂度取决于启发式.在最坏的情况下,扩展的节点数在解的长度(最短路径)中是指数的,但是当搜索空间是树时它是多项式的...

我的问题是:"A*的时间复杂度是指数级的吗？还是时间复杂度不是存储复杂性？" 如果是内存复杂性,A*的时间复杂度是多少？

Answer 1

在最坏的情况下，A* 时间复杂度是指数级的。

但是，请考虑h(n) 估计的距离和h*(n)剩余的确切距离。如果条件| h(n) - h*(n) | < O(log *h(n) )成立，即如果我们的估计函数的误差呈次指数增长，那么 A* 时间复杂度将是多项式的。

可悲的是，大多数情况下估计误差线性增长，因此，在实践中，更快的替代方案是首选，付出的代价是不再实现最优性的事实。

Answer 2

由于存储每个扩展节点是为了避免多次访问同一节点，因此扩展节点数量的指数增长意味着指数时间和空间复杂度。

请注意，指数空间复杂度必然意味着指数时间复杂度。反之则不然。