How to compute the running time of A-star algorithm

Question

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?

Here: http://developer.android.com/intl/es/tools/debugging/systrace.html and here: http://developer.android.com/intl/es/tools/debugging/ddms.html You will find some information, hope it helps! — Jachu, Apr 22 '13 at 08:00
It depends on the end-points and obstacles, so I'm not sure this question is answerable. — harold, Apr 22 '13 at 08:06
The complexity is drastically dependend on your heuristic, what your pseudo code describes is actually Dijkstras algorithm which runs in O((|V|+|E|)*log(|V|) which is also the worst case of A*. — Thomas Jungblut, Apr 22 '13 at 08:11
@harold lets say that the obstacles are perpendicular lines, but are not specific. So there's no way I could actually find an upper bound on the run time? — Kraken, Apr 22 '13 at 11:49
Does that mean the obstacles could separate the start and goal so there is no route? In that case it would explore the entire area reachable from the start position. — harold, Apr 22 '13 at 13:45
@harold no, that will never happen. I am not sure how to calculate the the time complexity. The add/removing from heap will take around log(numberOfelementsInHeap) time, and how many times will the loop execute? n^2 could be the maximum time, for the worst case maybe, but what about the average case? — Kraken, Apr 22 '13 at 15:16

score 2 · Accepted Answer · edited May 23 '17 at 12:04

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.

How to compute the running time of A-star algorithm

1 Answers1

Linked