A-star search algorithm

The A* search algorithm (pronounced "Ay-star") is a tree search algorithm that finds a path from a given initial node to a given goal node. 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.

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 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* constructs and outputs the successful path and stops.

If the node is not the goal node it creates new nodes for 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 (the cost is the cumulative sum of all its ancestors plus its own cost) and saves it with the node.

The algorithm then searches a closed node list (nodes whose adjoining nodes have been checked) for the same node. If the node is found in the closed list with a lower or equal cost, no further processing is done on that node with the path associated with it.

If the same node is in the closed but has a higher cost or is not in the list, A* estimates the node's distance to the goal. It then adds the cost and distance estimate together and saves them as the heuristic.

A* then checks to see if this node (i.e. identical nodes that had higher costs) is in the closed list and removes it if it is. It then checks to see if the node is in "Open" priority queue and adds it if it is not. A* then places the original node which it had removed from the "Open" and places it in the closed node list. Then A* pops the next node off of "Open" and starts all over again.

External Link

• Justin Heyes-Jones' A* algorithm tutorial (http://www.geocities.com/jheyesjones/astar)