A* Search
Motivation
A* search is the standard informed search algorithm: a best-first search that orders the frontier by an estimate of total path cost, \(f(n) = g(n) + h(n)\), where \(g(n)\) is the cost from the start to \(n\) and \(h(n)\) is a heuristic estimate of the cost from \(n\) to the nearest goal (Hart et al. 1968). With an admissible heuristic, A* is guaranteed to return an optimal solution while expanding at most the nodes any optimal admissible algorithm must expand.
A* generalizes both breadth-first search (special case: unit edge costs and \(h \equiv 0\), ordered by depth) and Dijkstra’s algorithm (special case: \(h \equiv 0\)). Adding a non-trivial admissible \(h\) focuses the search toward the goal without sacrificing optimality.
Problem
Given a graph with non-negative edge costs \(c(n, n') \ge 0\), a start node \(s\), a goal test, and a heuristic \(h : V \to \mathbb{R}_{\ge 0}\) with \(h(g) = 0\) at every goal, find a minimum-cost path from \(s\) to any goal.
For each node \(n\) generated during the search:
- \(g(n)\) is the cost of the best known path from \(s\) to \(n\).
- \(h(n)\) is the heuristic estimate from \(n\) to a goal.
- \(f(n) = g(n) + h(n)\) is the estimated total cost of a path through \(n\).
Key Ideas
A* sits between two extremes. Dijkstra expands nodes in order of \(g(n)\), the known cost so far; greedy best-first search expands in order of \(h(n)\), the estimated cost remaining. A* expands in order of \(f(n) = g(n) + h(n)\), the estimated total cost — exact for nodes where the path so far is fixed, estimated for the rest. This single change inherits Dijkstra’s optimality while pulling expansion toward the goal.
Two heuristic properties drive correctness.
- Admissibility: \(h(n) \le h^*(n)\), where \(h^*\) is the true cost to the nearest goal. Equivalently, \(h\) never overestimates. This is exactly the condition that prevents A* from declaring victory at a suboptimal goal: any open node with smaller \(f\) than the current best goal still has a chance of leading somewhere better.
- Consistency (or monotonicity): \(h(n) \le c(n, n') + h(n')\) for every edge \((n, n')\). The triangle-inequality form. Consistency is strictly stronger than admissibility and implies that \(f\) is non-decreasing along any path — so the first time a node is popped, its \(g\)-value is already optimal and it will never need to be reopened.
The grid walkthrough below shows the consistent-heuristic case explicitly: \(f\) stays flat at \(5\) near the start, then climbs to the true optimal cost \(7\) when the search is forced to detour, and stays there along the rest of the optimal path.
Two invariants drop out of the design.
- \(g(n)\) is monotonically non-increasing over time for every \(n\): a cheaper path always overwrites a worse one.
- A node may be re-opened from the closed list only when a strictly cheaper path to it is discovered. With a consistent heuristic, this never happens, and the reopen branch can be deleted.
Algorithm
A* maintains a priority queue (the open list or frontier) ordered by \(f\)-value, and a set of expanded nodes (the closed list).
function A-STAR(s):
open = priority queue ordered by f
open.insert(s, f(s) = h(s))
g[s] = 0
closed = empty set
while open is not empty:
n = open.pop_min()
if Goal(n): return reconstruct_path(n)
closed.add(n)
for each successor n' of n:
tentative_g = g[n] + c(n, n')
if n' in closed and tentative_g >= g[n']: continue
if n' not in open or tentative_g < g[n']:
g[n'] = tentative_g
parent[n'] = n
f_n' = tentative_g + h(n')
if n' in open: open.decrease_key(n', f_n')
else: open.insert(n', f_n')
if n' in closed: closed.remove(n'); open.insert(n', f_n')
return failureThe goal test runs when a node is popped, not when it is generated. Testing on generation is incorrect: the first time the goal node is generated, the path leading to it may not be optimal, and a better path may still be in the open list.
Walkthrough
A small grid with an obstacle
A \(6 \times 3\) grid with unit move costs (4-directional). Start \(S\) at the left, goal \(G\) at the right, and a single obstacle at \((2, 1)\) that blocks the direct path. Heuristic \(h\) is Manhattan distance to \(G\), which is consistent on a grid with unit moves. Each cell on the optimal path is annotated with \(g + h = f\).
When \(S\) is expanded, \(f(S) = 5\). The successor \((1, 1)\) also has \(f = 5\), so A* keeps exploring through it. From \((1, 1)\) the only way around the wall is up or down, which costs \(1\) in \(g\) and \(1\) more in \(h\) — pushing \(f\) to \(7\), the true optimal cost. From that point onward \(f\) stays at \(7\) along the optimal path: each step adds \(1\) to \(g\) and removes \(1\) from \(h\). With a consistent heuristic, this monotone-\(f\) property along optimal paths is what guarantees A* expands each node at most once.
Correctness
Theorem (optimality). If \(h\) is admissible, A* returns an optimal solution (Russell and Norvig 2020). (proof)
The argument is short. Suppose A* pops goal \(g\) with \(f(g) = g(g)\) (since \(h(g) = 0\)), and there exists a cheaper goal \(g'\) with \(g(g') < g(g)\). Any optimal path to \(g'\) must contain some node \(n\) still on the open list, and \(f(n) = g(n) + h(n) \le g(n) + h^*(n) = g^*(g')< g(g) = f(g)\) — contradicting that A* pops the minimum-\(f\) node. Admissibility is used in the inequality \(h(n) \le h^*(n)\).
Theorem (consistency strengthens optimality). If \(h\) is consistent, the first time any node is popped, \(g(n)\) is already optimal — so the closed-list reopen step is unnecessary, and each node is expanded at most once (Russell and Norvig 2020). (proof)
Heuristic strength interpolates between Dijkstra and an oracle.
- \(h \equiv 0\): A* reduces to Dijkstra. Optimal but uninformed.
- \(h = h^*\): A* expands only nodes along an optimal path. Optimal and minimal-effort.
- \(h \le h^*\) everywhere: optimal, with effort interpolating between the extremes.
Complexity and Tradeoffs
Time and space are both \(O(b^d)\) in the worst case, where \(b\) is the branching factor and \(d\) the optimal solution depth — A* is no better than BFS when the heuristic is uninformative. The interesting performance characterization is in terms of heuristic error \(\varepsilon = h^* - h\): the number of nodes A* expands grows exponentially in \(\varepsilon\) (loosely speaking), so even small improvements in heuristic accuracy translate into large savings.
The dominant practical issue is memory, not time. A* stores every generated node so it can compare paths and reconstruct the solution; on hard problems the open and closed lists grow until the machine runs out of memory before time. Several variants address this:
- Iterative-deepening A* (IDA*). Run depth-first search with an increasing \(f\)-cost cutoff, like iterative deepening but bounded by \(f\) rather than depth. Linear space, slightly more time due to repeated work.
- Recursive best-first search (RBFS). Linear space; tracks the best \(f\) along each branch and backtracks when surpassed.
- SMA* (simplified memory-bounded A*). Drops the worst-\(f\) leaves when memory fills, retaining a backup of their best descendant’s \(f\) to resume later.
When to Use It
| Situation | Use A*? |
|---|---|
| Non-negative edge costs, non-trivial admissible heuristic, memory sufficient | Yes — the default informed-search algorithm. |
| Edge costs only, no useful heuristic | No — A* with \(h \equiv 0\) is just Dijkstra. |
| Memory tight, problem large | Use IDA, RBFS, or SMA instead. |
| Only a good solution needed, not optimal | Weighted A* (\(f = g + w \cdot h\), \(w > 1\)) trades optimality for speed. |
| Negative edges | Not applicable — A* requires non-negative costs (use Bellman-Ford). |