complexity-theory - A* 时间复杂度

Question

维基百科对 A* 的复杂性做了以下说明:

The time complexity of A* depends on the heuristic. In the worst case, the number of nodes expanded is exponential in the length of the solution (the shortest path), but it is polynomial when the search space is a tree...

我的问题是:“A* 的时间复杂度是指数级的吗？或者它不是时间复杂度，而是内存复杂度？”
如果是内存复杂度，A*的时间复杂度是多少？

Answer 1

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

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

可悲的是，大多数时候估计误差是线性增长的，所以，在实践中，
更快的替代方案是首选，付出的代价是最优性
不再实现。