A* search algorithm

In computer science, A* (pronounced 'A-star') is a computer algorithm that is widely used in pathfinding and graph traversal, which is the process of finding a path between multiple points, called 'nodes'. It enjoys widespread use due to its performance and accuracy. However, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, although other work has found A* to be superior to other approaches. In computer science, A* (pronounced 'A-star') is a computer algorithm that is widely used in pathfinding and graph traversal, which is the process of finding a path between multiple points, called 'nodes'. It enjoys widespread use due to its performance and accuracy. However, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, although other work has found A* to be superior to other approaches. Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968. It can be seen as an extension of Edsger Dijkstra's 1959 algorithm. A* achieves better performance by using heuristics to guide its search. A* was created as part of the Shakey project, which had the aim of building a mobile robot that could plan its own actions.  Nils Nilsson originally proposed using the Graph Traverser algorithm for Shakey's path planning. Graph Traverser is guided by a heuristic function h ( n ) , {displaystyle h(n),} the estimated distance from node n {displaystyle n} to the goal node, it entirely ignores g ( n ) , {displaystyle g(n),} the distance from the start node to n . {displaystyle n.} Bertram Raphael suggested using the sum, g ( n ) + h ( n ) {displaystyle g(n)+h(n)} . Peter Hart invented the concepts we now call admissibility and consistency of heuristic functions.  A* was originally designed for finding least-cost paths when the cost of a path is the sum of its edge costs, but it has been shown that A* can be used to find optimal paths for any problem satisfying the conditions of a cost algebra. The original 1968 A* paper contained a theorem that no A*-like algorithm could expand fewer nodes than A* if the heuristic function is consistent and A*’s tie-breaking rule is suitably chosen. A ″correction″ was published a few years later claiming that consistency was not required, just admissibility, but this was shown to be false in Dechter and Pearl’s definitive study of A*'s optimality (optimal efficiency as it is now called), which gave an example of A* with a heuristic that was admissible but not consistent expanding arbitrarily more nodes than an alternative A*-like algorithm. A* is an informed search algorithm, or a best-first search, meaning that it is formulated in terms of weighted graphs: starting from a specific starting node of a graph, it aims to find a path to the given goal node having the smallest cost (least distance travelled, shortest time, etc.). It does this by maintaining a tree of paths originating at the start node and extending those paths one edge at a time until its termination criterion is satisfied.