How to find the running time of an algorithm that involves heuristics

Question

I am working with A* algorithm, in which I have a 2D grid and given two points, find the shortest distance between them, while not running into any obstruction.

Now, for each cell, I find the distance from the source, and calculate the distance from destination. Add the two quantities, and the one that has the minimum value, that cell is considered next.

Now, How do I calculate the running time of such an algorithm, since I'll never know how many times this process will be repeated. i.e how many cells will I have to work, with, before I reach my destination. Kindly help.

I am looking for the upper bound of running time. In terms of the length of side of grid, i.e. N.

Thanks.

Answer 1

Your 2D grid obviously has N^2 points.

The absolute worst case is that the heuristic always misdirects the algorithm, so the algorithm avoids the target point. With A*, that can happen with an extremely complex set of barriers, so that trying to move towards the target is generally a bad search strategy.

It's possible to construct a map where the only route to the target visits every single non-target cell before the reaching the target. Having constructed that map, you can remove the barriers that aren't really affecting how the algorithm searches (the algorithm still does the same search even with those barriers removed) to superficially allow more freedom, yet that freedom is never exploited.

Basically, that means the worst case is quadratic - the algorithm may search every one of those N^2 cells before finding the target.

One way to improve the algorithm is to use a measure of distance that's sensitive to the barriers - not just as-the-crow-flies. Obviously if the only route to the target requires visiting every cell that makes no difference, but the heuristic is much less likely to misdirect the search if there's some freedom to choose.

The problem is that getting a perfect measure of distance is as complex as finding the perfect route to the target anyway. However, you could precompute a shortest possible distance for each cell if the target is always in the same place, and use that as a lookup table later.