
related topics 
{math, number, function} 
{rate, high, increase} 
{line, north, south} 

In computer science, A* (pronounced "A star") is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes. Noted for its performance and accuracy, it enjoys widespread use. Peter Hart, Nils Nilsson, and Bertram Raphael first described the algorithm in 1968^{[1]}. It is an extension of Edsger Dijkstra's 1959 algorithm. A* achieves better performance (with respect to time) by using heuristics.
Contents
Description
A* uses a bestfirst search and finds the leastcost path from a given initial node to one goal node (out of one or more possible goals).
It uses a distancepluscost heuristic function (usually denoted f(x)) to determine the order in which the search visits nodes in the tree. The distancepluscost heuristic is a sum of two functions:
 the pathcost function, which is the cost from the starting node to the current node (usually denoted g(x))
 and an admissible "heuristic estimate" of the distance to the goal (usually denoted h(x)).
The h(x) part of the f(x) function must be an admissible heuristic; that is, it must not overestimate the distance to the goal. Thus, for an application like routing, h(x) might represent the straightline distance to the goal, since that is physically the smallest possible distance between any two points or nodes.
Full article ▸


related documents 
Topological vector space 
Banach space 
Bspline 
Normal space 
Universal quantification 
Optimization (mathematics) 
Partially ordered set 
Ordered pair 
Document Type Definition 
Free group 
Associative array 
Stokes' theorem 
Graph theory 
Algebraically closed field 
Henri Lebesgue 
LL parser 
Expander graph 
Direct product 
Parameter 
Sheffer stroke 
Minimum spanning tree 
NP (complexity) 
Net (mathematics) 
Empty set 
Greatest common divisor 
Polish notation 
Integer factorization 
Topology 
Grover's algorithm 
Affine transformation 
