A* search algorithm

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 best-first search and finds the least-cost path from a given initial node to one goal node (out of one or more possible goals).

It uses a distance-plus-cost heuristic function (usually denoted f(x)) to determine the order in which the search visits nodes in the tree. The distance-plus-cost heuristic is a sum of two functions:

  • the path-cost 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 straight-line 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
B-spline
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