A* search algorithm: Encyclopedia II - A* search algorithm - Intuition

A* search algorithm - Intuition

Let's consider a motivating example. Say you are standing at intersection A, and you would like to go to an intersection B that you happen to know is north of where you currently are. In this case the intersections are the vertices of the graph and the roads are edges.

If you do a breadth-first search like Dijkstra's Algorithm dictates, you would search all points within a fixed circular radius, gradually expanding this circle to search intersections farther and farther away from your starting point. This might be an effective strategy if you don't know where your destination is, such as police searching for a criminal in hiding.

However, it is a waste of time if you have more information. A better strategy is to explore the intersection directly to the north first, because it's the closest vertex to B. Then, the roads permitting, you would continue to explore intersections closer and closer to the goal B. You might have to occasionally backtrack, but on typical maps this is a much quicker strategy. Moreover, it can be proved that this strategy will find the best possible route, just as breadth-first search does. This is the essence of A* search.

However, A* is not guaranteed to perform better than simpler search algorithms. In a maze-like environment, the only way to reach your destination might be to travel south first and eventually turn around. In this case trying nodes closer to your destination first may cost you time.

Adapted from the Wikipedia article "Intuition", under the G.N U Free Docmentation License. Please also see http://en.wikipedia.org/wiki