我正在使用A*算法。我有一个二维网格，其中有一些障碍物，给定起始和终点位置，我会找到它们之间的最短路径。
这是我的伪代码
while(queueNotEmpty){ removeFromPQ; if(removed == destination) found; insertAllNeighbours;}移除和插入操作是在优先级队列（堆）上进行的，时间复杂度为O(log(n))。
考虑网格的维度为N*N。我如何计算运行时间？即这个循环会执行多少次？有什么衡量标准吗？
回答：
标准A*算法的运行时间在最坏情况下是解的长度的指数级别。
如果你在一个n*n的网格上进行搜索，并且使用图搜索，搜索将最多访问每个节点一次；因此时间复杂度为O(n*n)。但只有当使用的启发式函数是单调的（除了可接受之外），找到的解才是最优的。
标准A*算法的多项式运行时间也有条件。
关于图搜索与树搜索的区别，请参见这个回答。
