A-star search algorithm Guide, Meaning , Facts, Information and Description
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, A* can be proven to to be admissible. If the estimate simply always returns zero, which is never an overestimate, then A* will effectively perform Dijkstra's algorithm and still find an optimal solution, albeit not as quickly. The best possible heuristic, although usually impractical to compute, is the actual minimal distance to the goal.
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.
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 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.
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 also maintains 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.
This is an Article on A-star search algorithm. Page Contains Information, Facts Details or Explanation Guide About A-star search algorithm Description
External links