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

Question

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

这是我的伪代码

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

删除和插入是优先队列(Heap)上的函数，时间为O(log(n))。

考虑网格的维度为 N*N。我如何计算运行时间。即这个循环将执行多少次？有什么措施吗？

Answer 1

标准 A* 的运行时间是解决方案长度的指数（最坏情况）。

如果您在 的网格上搜索n*n，并且使用图形搜索，则搜索最多会访问每个节点一次；所以它是O(n*n)。但是只有在使用的启发式是单调的（除了可以接受之外）时，找到的解决方案才是最佳的。

标准 A* 的多项式运行时间也有条件。

对于图形搜索与树搜索，请参阅此答案。