A* search algorithm

From Wikipedia, the free encyclopedia

The A* search algorithm (pronounced "A 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" that 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* 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.