如何计算A-star算法的运行时间

Question

我正在使用A*算法。我有一个2D网格，带有一些障碍物，给定起始位置和最终位置，我找到它们之间的最短路径。

这是我的伪代码

while(queueNotEmpty){
  removeFromPQ;
  if(removed == destination)
    found;
  insertAllNeighbours;
}

Remove和insert是优先级队列(堆)上的函数，时间为O(log(n))。

考虑网格的维度为N*N，如何计算运行时间。也就是说，这个循环要执行多少次？有什么措施吗？

Answer 1

标准A*的运行时间在解决方案的长度上是指数的(最坏情况)。

如果您在图的网格上进行搜索，并且使用n*n - search，那么搜索将最多访问每个节点一次；因此它是O(n*n)。但是，找到的解决方案只有在使用的启发式是monotone的情况下才是最优的(除了是可接受的)。

还有用于标准A*的多项式运行时的conditions。

有关图搜索与树搜索的比较，请参阅this answer。