Astar Search

A heuristic graph-search algorithm for finding shortest paths. The input to A* is a starting node, the goal node, plus a heuristic function h that returns an estimate of the distance from a given node to the goal node. If the heuristic h never overestimates the distance to the goal, then it is called an admissible heuristic. A* search with an admissible heuristic is guaranteed to find the shortest path between the starting node and the goal node. A* is the darling of ArtificialIntelligence courses, probably mostly because it's relatively easy to understand the proof of this fact. Furthermore, it can be shown that an algorithm which visits fewer nodes then A* could potentially miss the shortest path.

A* works by visiting one new node at time. It keeps a PriorityQueue full of nodes, and always "expands" the node with the lowest priority (sometimes called its f-value, or expected cost) which is computed as cost(node) + h(node), where cost(node) is the distance travelled so far, and h(node) is the heuristic estimate of the remaining distance to the goal node. Every time a node is "expanded", its unexplored neighbours are added to the queue. The result is that A* keeps track of a large number of potential paths radiating from the start node, and it extends these paths one node at time, always extending the one with the smallest cost(node) + h(node) value.

A* is an example of a GreedyAlgorithm. It is very similar to DijkstrasAlgorithm, the difference being that DijkstrasAlgorithm uses no heuristic, and so when deciding which node to expand next it only considers the cost from the start node.

Assuming that distances are always positive, DijkstrasAlgorithm is a degenerate case of A*, where h(node) is always zero.

If you don't have a really good heuristic function, or if the graph you are searching is large, then A* uses a lot of memory, and so for many search problems, even ones that look simple, it is infeasible. Improved variations that manage memory better have been developed, such as iterative-deepening A* (IDA*) and simplified memory-bounded A* (SMA*).

Some applications of A* search include:

Solving combinatorial puzzles, like RubiksCube (and RubiksRevenge), the FifteenPuzzle, etc. While these are toy puzzles (in more ways than one!), they suffer from CombinatorialExplosion, and so are typically difficult solve, even with BigIron. Not only that, but finding good heuristics for such non-trivial problems is non-trivial.
Pathfinding in video games, e.g. making little people move from a start point to an end point in an efficient way.
Route finding, e.g. creating an itinerary for a vacation.
Robot navigation.
VLSI layout.
Assembly sequencing.

In practice, most of these problems are best solved by specialized variations of some sort of heuristic search method, often something other than A*.

A* has a lot of intuitive appeal for me. If you compare Dijkstra's vs. A*, Dijkstra's is like a puddle of water flooding outwards on a flat floor, whereas A* is like the same puddle expanding on a bumpy and graded floor toward a drain (the target node) at the lowest point in the floor. Instead of spreading out evenly on all sides, the water seeks the path of least resistance, only trying new paths when something gets in its way. The heuristic function is what provides the 'grade' of the hypothetical floor.

That is a truly beautiful description.

I've always wanted to write an article with the title "A History of Heuristic Search: A* is Born". Ugh!

WorstPunEver?