我正在使用 A* 算法。我有一个二维网格，有一些障碍物，并且给定起始位置和最终位置，我找到它们之间的最短路径。
这是我的伪代码
while(queueNotEmpty){
removeFromPQ;
if(removed == destination)
found;
insertAllNeighbours;
}
删除和插入是优先级队列(堆)上的函数，时间复杂度为O(log(n))。
考虑网格的维度为N*N。我如何计算运行时间。即这个循环会执行多少次？有什么措施吗？
最佳答案
标准 A* 的运行时间与解决方案的长度呈指数关系(最坏情况)。
如果您在 n*n 网格上搜索，并且使用图形搜索，则搜索最多会访问每个节点一次；所以它是O(n*n)。但只有当使用的启发式为 monotone 时，找到的解决方案才是最佳的。 (除了可以接受之外)。
还有conditions标准 A* 的多项式运行时间。
对于图搜索与树搜索，请参阅 this answer .
关于performance - 如何计算A-star算法的运行时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16141678/