A-star search algorithm

From Wikipedia, the free encyclopedia.

The title given to this article is incorrect due to technical limitations. The correct title is A* search algorithm.

The A* search algorithm (pronounced "eigh star") is a graph search algorithm that finds a path from a given initial node to a given goal node (or one passing a given goal test). It employs a "heuristic estimate" which ranks each node by an estimate of the best route that goes through that node. It visits the nodes in order of this heuristic estimate. The A* algorithm is therefore an example of best-first search.

A search algorithm that is guaranteed always to find the shortest path to a goal is called admissible. If A* uses a heuristic that never overestimates the distance (or in general, the cost) to the goal and that is growing monotonely, A* can be proven to to be admissible. If the estimate simply always returns a constant (positive) value, then A* will effectively perform a Breadth-first search. When the costs of the individual steps are exactly known (not estimated), it will behave like Dijkstra's algorithm. The best possible heuristic, although usually impractical to compute, is the actual minimal distance to the goal.

Note: The previous paragraph is a bit imprecise. A better description would use both a cost function and a cost increase estimation function.

A* provably considers fewer nodes than any other admissible search algorithm, provided that the alternative algorithm does not have a more accurate heuristic estimate. In this sense, A* is the computationally most-efficient algorithm that's guaranteed to find the shortest path.

Description

A* begins at a selected node. Applied to this node are the "cost" of entering this node (usually zero for the initial node). A* then estimates the distance to the goal node from the current node. This estimate and the cost added together are the heuristic which is assigned to the path leading to this node. The node is then added to a priority queue, often called "open".

The algorithm then removes the next node from the priority queue (because of the way a priority queue works, the node removed will have the lowest heuristic). If the queue is empty, there is no path from the initial node to the goal node and the algorithm stops. If the node is the goal node, A* reconstructs and outputs the successful path using Backtracking and stops. This path reconstruction from the stored closed nodes (see below) means it is not necessary to store the path-so-far within each node. (Some applications will not need want to do this, and just drop the interim nodes when closed) It is also possible to use this algorithm to find multiple solutions, sorted by quality.

If the node is not the goal node, new nodes are created for all admissible adjoining nodes; the exact way of doing this depends on the problem at hand. For each successive node, A* calculates the "cost" of entering the node and saves it with the node. This cost is calculated from the cumulative sum of costs stored with its ancestors, plus the cost of the operation which reached this new node.

The algorithm often also needs to maintain a 'closed' list of nodes which have been checked. If a newly generated node is already in this list with an equal or lower cost, no further processing is done on that node or with the path associated with it. If a node in the closed list matches the new one, but has been stored with a higher cost, it is removed from the closed list, and processing continues on the new node.

Next, an estimate of the new node's distance to the goal is added to the cost to form the heuristic for that node. This is then added to the 'open' priority queue, unless an identical node with lesser or equal heuristic is found there.

Once the above three steps have been repeated for each new adjoining node, the original node taken from the priority queue is added to the 'closed' list. The next node is then popped from the priority queue and the process is repeated.

See also

Depth-first Serach Breadth-first Search

External links

• Justin Heyes-Jones' A* algorithm tutorial (http://www.geocities.com/jheyesjones/astar.html)
• Another A* Pathfinding for Beginners (http://www.policyalmanac.org/games/aStarTutorial.htm)
• Amit's Thoughts on Path-Finding and A* (http://theory.stanford.edu/~amitp/GameProgramming/)
• Sven Koenig's Lifelong Planning A* vs. A* demo (http://www.cc.gatech.edu/fac/Sven.Koenig/greedyonline/applet.html)
• Squeaky Dolphin's Description of Iterative Deepening A* (IDA*) (http://ai.squeakydolphin.com/wiki.php?pagename=AIAWiki.IterativeDeepeningSearch)