CtrlK
A* (pronounced "A-star") is a best-first graph search algorithm that finds a least-cost path from a start node to a goal node. It evaluates candidate paths using the function f(n) = g(n) + h(n), where g(n) is the actual cost from the start to node n and h(n) is a heuristic estimate of the remaining cost from n to the goal. When the heuristic is admissible (never overestimates the true remaining cost), A* is guaranteed to return an optimal solution. The algorithm was introduced in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at the Stanford Research Institute (SRI) as part of the Shakey the Robot project, and it remains one of the most widely taught and deployed algorithms in artificial intelligence, used in video-game pathfinding, robot motion planning, route planning, puzzle solving, and parsing of probabilistic grammars.
A* is what happens when you take Dijkstra's algorithm and give it a sense of direction. Dijkstra spreads outward in concentric rings of cost from the start, eventually reaching the goal but expanding many nodes that lie nowhere near it. A* uses a heuristic to bias the search toward nodes that look closer to the goal, so it expands fewer nodes while still keeping Dijkstra's optimality guarantee whenever the heuristic is admissible.
Think of it as planning a road trip. The cost so far, g(n), is what your odometer says. The heuristic, h(n), is your best guess of how far you still have to go (often a straight-line distance). At each step, A* picks the city with the smallest total estimated trip length g(n) + h(n). As long as the guess never exceeds the true distance, the first city A* visits that is the destination must be reached by the shortest road network path.
If h(n) = 0 for every node, A* degenerates into Dijkstra's algorithm. If you ignore g(n) and rank nodes by h(n) alone, you get greedy best-first search, which is fast but does not guarantee an optimal path. A* sits in the middle, using both pieces of information to be both efficient and correct.
A* came out of work on Shakey, a wheeled mobile robot built at the Stanford Research Institute (now SRI International) between 1966 and 1972. Shakey was the first general-purpose mobile robot able to reason about its own actions, and it needed an algorithm that could plan a route across a known indoor environment while avoiding obstacles.
Nils Nilsson had earlier proposed a method called the Graph Traverser. Bertram Raphael suggested combining the cost so far with a heuristic estimate of the remaining cost into a single evaluation function f = g + h. Peter Hart formalized the conditions under which the resulting search is guaranteed to find an optimal solution, introducing the notions of admissibility and consistency for heuristic functions. The three published their work in 1968 as "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" in IEEE Transactions on Systems Science and Cybernetics.
The original 1968 paper claimed that A* is optimally efficient, in the sense that no other admissible algorithm with the same heuristic information could expand fewer nodes. The proof in that paper had a flaw, and the authors published a correction in 1972 in SIGART Newsletter clarifying that the optimal-efficiency result holds when the heuristic is consistent and ties are broken consistently. The algorithm itself, and the optimality result for admissible heuristics, were not affected.
Hart later said that the name "A*" came from internal SRI notation: the family of algorithms parameterized by an evaluation function was called "A", and the asterisk denoted the optimal member of the family (the version with admissible heuristics). The notation stuck.
A* operates on a weighted graph G = (V, E) with non-negative edge costs. Given a start node s in V and either a single goal t or a goal predicate, the algorithm searches for a path from s to a goal that minimizes the sum of edge costs.
The key quantities are:
| Symbol | Meaning |
|---|---|
| g(n) | Best known cost of a path from the start s to node n found so far. |
| h(n) | Heuristic estimate of the cost of a cheapest path from n to a goal. |
| f(n) = g(n) + h(n) | Estimated cost of a cheapest path from s to a goal that passes through n. |
| h*(n) | The true (optimal) remaining cost from n to a goal. |
| C* | The optimal solution cost from s to a goal. |
A* maintains two collections of nodes:
At each iteration A* removes the node with the smallest f-value from the open set, generates its successors, computes their g, h, and f values, and inserts them into the open set (or updates them if a cheaper path is found). The algorithm terminates when it removes a goal node from the open set.
A heuristic h is admissible if for every node n in the graph,
h(n) <= h*(n)
that is, h never overestimates the true cost to reach a goal. Admissibility is what makes A* optimal in tree search and is the property invoked in most introductory proofs.
A heuristic h is consistent (also called monotone) if for every node n and every successor n' of n reached through edge cost c(n, n'),
h(n) <= c(n, n') + h(n'),
with h(goal) = 0. This is a triangle-inequality condition. Every consistent heuristic is admissible, but not every admissible heuristic is consistent. Consistency guarantees that the f values along any path are non-decreasing, which lets A* close each node permanently the first time it is expanded; with admissible-but-inconsistent heuristics, the graph-search version of A* must be willing to re-open nodes (or use a closed-list check that compares g values) to remain optimal.
The canonical reference implementation is the graph-search variant. The following pseudocode assumes a consistent heuristic and uses a priority queue ordered by f(n):
function A_star(start, goal, h):
open_set := priority queue ordered by f-value
open_set.insert(start, f = h(start))
came_from := empty map // for path reconstruction
g_score := map with default value of +infinity
g_score[start] := 0
f_score := map with default value of +infinity
f_score[start] := h(start)
while open_set is not empty:
current := open_set.pop() // node with lowest f_score
if current == goal:
return reconstruct_path(came_from, current)
for each neighbor n' of current:
tentative_g := g_score[current] + cost(current, n')
if tentative_g < g_score[n']:
came_from[n'] := current
g_score[n'] := tentative_g
f_score[n'] := tentative_g + h(n')
if n' not in open_set:
open_set.insert(n', f_score[n'])
else:
open_set.decrease_key(n', f_score[n'])
return failure // no path exists
function reconstruct_path(came_from, current):
path := [current]
while current in came_from:
current := came_from[current]
path.prepend(current)
return path
When the heuristic is only admissible (not consistent), the algorithm is correct as written if a closed list is omitted, or if the closed list permits re-opening a node when a cheaper g score is later discovered.
A* is complete on graphs with finite branching factor and a positive lower bound epsilon > 0 on edge costs, provided a solution exists. Under these conditions there are only finitely many paths whose total cost is below the optimal C*, so the algorithm cannot expand nodes forever without reaching a goal.
If h is admissible, the tree-search version of A* returns an optimal solution. If h is consistent, the graph-search version (which avoids re-expanding closed nodes) is also optimal. The standard proof argument: when A* is about to expand a goal node t, the f-value of t is g(t) + h(t) = g(t), the actual cost of the path found. Any other node n still on the open set has f(n) <= f(t), since t was selected as the minimum. Because h is admissible, f(n) is a lower bound on the cost of any complete path through n, so no unexpanded path can be cheaper than g(t).
For a fixed admissible heuristic, no other algorithm in a comparable class can expand strictly fewer nodes than A* without risking missing the optimal solution. This was the result Hart, Nilsson, and Raphael set out to prove and is the result clarified in their 1972 correction. The technical statement requires careful conditions on the class of competing algorithms and on tie-breaking, but the intuition is that any node with f(n) < C* must be examined by any algorithm that is guaranteed to find an optimal path with the same heuristic information.
In the worst case, A* explores a number of nodes exponential in the depth of the optimal solution:
O(b^d)
where b is the branching factor and d is the depth of the goal. A tighter bound depends on the quality of the heuristic. If h is within a constant factor of h*, the search remains exponential, but the base of the exponent is smaller. A common analytical bound is O(b^(epsilon * d)) where epsilon is the relative error of the heuristic. With a perfect heuristic (h = h*), A* expands only the nodes on the optimal path and runs in O(d) time.
Space complexity is the same order as time complexity in the worst case, because every generated node is held in memory through the open and closed sets. This is the practical limit of A* on large state spaces, and is what motivates the memory-bounded variants discussed below.
The choice of heuristic is the single biggest performance lever in A*. A weak heuristic gives correct but slow search; a strong heuristic gives correct and fast search. Common heuristics for grid-based pathfinding are summarized below, where (x1, y1) and (x2, y2) are the coordinates of the two nodes:
| Heuristic | Formula | Movement model |
|---|---|---|
| Manhattan distance | * | x1 - x2 |
| Euclidean distance | sqrt((x1 - x2)^2 + (y1 - y2)^2) | Movement at any angle (continuous space). |
| Chebyshev distance | *max( | x1 - x2 |
| Octile distance | max(dx, dy) + (sqrt(2) - 1) * min(dx, dy) where *dx = | x1 - x2 |
| Zero heuristic | h(n) = 0 | Reduces A* to Dijkstra's algorithm. Useful when no domain knowledge is available. |
For sliding-tile puzzles such as the 8-puzzle and 15-puzzle, classic heuristics include the number of misplaced tiles, the sum of Manhattan distances between each tile and its target square, and pattern databases that store optimal subproblem costs. For routing on road networks, popular heuristics include great-circle distance, landmark-based ALT (A*, Landmarks, and Triangle inequality), and contraction-hierarchy-derived bounds.
Given two admissible heuristics h1 and h2, h2 is said to dominate h1 if h2(n) >= h1(n) for every node n. A dominating heuristic produces an A* search that expands no more nodes than the dominated heuristic, while remaining admissible. The maximum of two admissible heuristics is itself admissible and dominates each, so combining heuristics by taking the maximum is a standard trick. The trade-off is computational: a stronger heuristic typically takes longer to evaluate per node.
Decades of research have produced a family of A*-style algorithms tailored to different constraints. The most widely used are:
| Variant | Year | Key idea | Use case |
|---|---|---|---|
| Iterative deepening A* (IDA*) | 1985, Korf | Uses depth-first search bounded by an f-cost threshold that grows between iterations. | Memory-constrained problems such as the 15-puzzle and Rubik's cube, where A*'s open list would not fit in RAM. |
| Simplified Memory-bounded A* (SMA*) | 1992, Russell | Like A* but discards the highest-f leaves when memory is full, backing up their f values to ancestors. | Real-time and embedded systems with hard memory limits. |
| Weighted A* | 1970, Pohl | Replaces f = g + h with f = g + w * h for w > 1, sacrificing optimality for speed. | Time-bounded search where a near-optimal answer (within factor w) is acceptable. |
| Anytime A* / ARA* | 2003, Likhachev et al. | Runs weighted A* with decreasing weight, returning successively better solutions until time runs out. | Robotics and planning problems with deadlines. |
| D* (Dynamic A*) | 1994, Stentz | Repairs an existing plan when edge costs change, instead of replanning from scratch. | Robot navigation with partially known or changing terrain. |
| D* Lite | 2002, Koenig and Likhachev | Re-derives D*'s functionality from Lifelong Planning A* with simpler bookkeeping. | Same as D*, used in the Mars Exploration Rovers and many subsequent robots. |
| Lifelong Planning A* (LPA*) | 2001, Koenig et al. | Reuses information from previous searches when the graph changes between queries. | Repeated planning in slowly changing environments. |
| Theta* / Lazy Theta* | 2007, Daniel et al. | Allows the parent of a node to be any visible ancestor, producing any-angle paths instead of grid-aligned paths. | 3D and continuous-space pathfinding for games and robotics. |
| Jump Point Search (JPS) | 2011, Harabor and Grastien | Skips symmetric paths on uniform-cost grids by jumping over forced and natural neighbors. | Real-time game pathfinding, where speedups of an order of magnitude over plain A* are common. |
| Hierarchical Pathfinding A* (HPA*) | 2004, Botea et al. | Pre-computes an abstract graph over clusters and searches the abstract graph before refining within clusters. | Very large grid maps in strategy games. |
| Bidirectional A* | 1971, Pohl | Runs two A* searches at once, one forward from the start and one backward from the goal, meeting in the middle. | Long-distance road routing and other large graphs. |
| Field D* | 2007, Ferguson and Stentz | An any-angle, dynamic variant of D* that interpolates costs across grid faces. | Mars rovers and outdoor mobile robots. |
| Real-Time A* (RTA*) and Learning Real-Time A* (LRTA*) | 1990, Korf | Commits to actions within a fixed time bound and learns improved heuristic estimates between trials. | Agents that must act faster than full A* search would allow. |
A* sits inside a small family of best-first search procedures that differ only in how they rank nodes. Setting the g term, the h term, or both to a constant produces several other classical algorithms:
| Algorithm | Evaluation function | Notes |
|---|---|---|
| Dijkstra's algorithm | f(n) = g(n) | Equivalent to A* with h(n) = 0. Optimal but expands many irrelevant nodes. |
| Uniform-cost search | f(n) = g(n) | The AI-textbook framing of Dijkstra; same algorithm. |
| Greedy best-first search | f(n) = h(n) | Fast, but neither complete on infinite graphs nor optimal. |
| Breadth-first search | All edge costs treated equal | A* with g(n) = path length and h(n) = 0. |
| Depth-first search | LIFO ordering | Not best-first; included for contrast. |
| Best-first beam search | f(n) = h(n), but the open set is truncated to size k | Sacrifices completeness for bounded memory. |
The relationship to Dijkstra's algorithm is the most useful one to remember: A* is Dijkstra plus a heuristic, and Dijkstra is A* with the trivial heuristic h = 0. Any correctness or complexity intuition that holds for one transfers, with adjustments for h, to the other.
A* is the default pathfinding algorithm in the games industry. Real-time strategy titles such as StarCraft, Age of Empires, and the Total War series use A* (or HPA* or Jump Point Search variants) to move units across maps with thousands of tiles. Role-playing games use it for non-player character navigation and for click-to-move player movement. The algorithm is popular because it is straightforward to implement on top of a navigation mesh or grid, scales to maps of practical size, and produces plausibly direct paths.
Mobile robots use A* and its dynamic descendants (D*, D* Lite, Field D*) for global path planning over occupancy grids. Notable deployments include the Mars Exploration Rovers Spirit and Opportunity, which used a variant of D* developed at Carnegie Mellon. Manipulation planners and motion planners also use A* over discretized configuration spaces for low-dimensional problems, though sampling-based planners such as RRT and PRM dominate at higher dimensions.
Early automotive GPS navigation devices used A* with great-circle or Euclidean heuristics on road graphs. Modern web-scale route planners (Google Maps, Bing Maps, OpenStreetMap routers) generally rely on speedup techniques such as contraction hierarchies, transit-node routing, and customizable contraction hierarchies, but A* with sophisticated heuristics (notably ALT, the landmark-based heuristic from Goldberg and Harrelson, 2005) remains a strong baseline and is still used in research and in some production systems.
A* parsing applies the algorithm to chart parsing for probabilistic context-free grammars (PCFGs) and other weighted grammars. Each chart edge is a node in the search graph, and the heuristic estimates the negative log probability of completing a parse from that edge. Klein and Manning's 2003 paper "A* Parsing: Fast Exact Viterbi Parse Selection" showed that admissible heuristics can give large speedups over standard chart parsing while still returning the most probable parse, a result that has influenced subsequent work on dependency parsing and semantic parsing in natural language processing.
A* and its variants appear in puzzle solvers (15-puzzle, Rubik's cube via IDA*), automated theorem proving, protein structure prediction, VLSI routing, multiple sequence alignment, and as the inner planner in many reinforcement learning systems that combine search with learned value estimates. The 2017 AlphaZero paper, while best known for minimax and Monte Carlo tree search, popularized neural-network-guided search techniques that generalize the A* idea of combining a learned heuristic with explicit lookahead.
A*'s memory consumption is the most common production headache. Maintaining the entire open set in a priority queue, plus a closed set large enough to deduplicate revisits, becomes infeasible on graphs with billions of nodes (continental road networks, high-resolution 3D voxel grids). IDA*, SMA*, and external-memory variants are the standard mitigations, along with hierarchical decompositions that shrink the problem before A* sees it.
A second pitfall is heuristic design. An inadmissible heuristic invalidates the optimality proof, and an inconsistent admissible heuristic invalidates the simple closed-list optimization. Many published implementations on the web silently assume consistency and quietly return suboptimal paths when the heuristic is only admissible. Designers writing custom heuristics should test for consistency by checking the triangle inequality on small graphs, and should be explicit about which variant of A* they are running.
A* is also a single-source single-target algorithm. For one-to-many or many-to-many shortest paths it is often more efficient to run Dijkstra from each source, or to use specialized algorithms such as contraction hierarchies. Heuristics that are tight for one goal may be loose for another, eroding A*'s speed advantage when the goal changes.
Finally, A* assumes the graph is fixed during the search. If edge costs can change while the algorithm runs (a moving obstacle, a closing road), plain A* will return a plan that may already be obsolete. Dynamic variants such as D* Lite and LPA* exist precisely to handle this case.