How to compute the running time of A-star algorith

问题:

I am working with A* algorithm. I have a 2D grid, with some obstacles, and given the starting and final position, I find the shortest path between them.

Here's my pseudocode

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

Remove and insert are the function on priority queue(Heap), and is O(log(n)) time.

Considering the dimension of grid as N*N. How do I calculate the running time. i.e how many times will this loop execute? Is there any measure?

回答1:

Runtime of standard A* is exponential in the length of the solution (worst-case).

If you're searching on a grid of n*n, and you use graph-search, the search will visit each node at most once; so it's O(n*n). But the found solution will only be optimal if the used heuristic is monotone (in addition to being admissible).

There are also conditions for polynomial runtime of standard A*.

For Graph-Search vs. Tree-Search see this answer.