A* Search Algorithm

A* search algorithm (pronounced "A-star") is an informed best-first graph traversal and heuristic pathfinding algorithm within computation and algorithms that computes a minimum-cost path from a start state s to a goal state t in a weighted state-space graph G = (V, E). Formulated in 1968 by Peter E. Hart, Nils J. Nilsson, and Bertram Raphael at the Stanford Research Institute to guide the mobile robot Shakey, the algorithm extends Dijkstra's algorithm by ordering its priority-queue frontier according to an evaluation function f(n) = g(n) + h(n), where g(n) is the accumulated path cost from s to node n and h(n) is a heuristic lower-bound estimate of the remaining cost from n to t.

Within computational complexity theory and artificial intelligence, Hart, Nilsson, and Raphael proved that whenever the heuristic h(n) is admissible (never overestimating the true remaining cost h*(n)) and consistent (satisfying the triangle inequality across every edge), A* is both complete and optimally efficient: no other deterministic search algorithm with access to the same heuristic can guarantee finding an optimal path while expanding fewer state-space nodes up to tie-breaking. Consequently, A* underpins autonomous robotics motion planning, heuristic multiple sequence alignment over dynamic programming lattices, protein side-chain rotamer packing, and seed-chain genomic read alignment using trie and suffix array indexes.

The Evaluation Function f(n) = g(n) + h(n)

Let G = (V, E, w) be a locally finite directed graph with step costs w(u, v) ≥ ε > 0, start vertex s ∈ V, and goal set T ⊆ V. Let g*(n) be the true shortest-path cost from s to n, h*(n) the true shortest-path cost from n to T, and C* = h*(s) the optimal solution cost. A* maintains a priority queue (OPEN) of frontier nodes and a set (CLOSED) of expanded nodes, tracking the best known cost g(n) from s to n and ordering OPEN by:

At each step, A* extracts n ∈ OPEN minimizing f(n). If n ∈ T, the search terminates and reconstructs the optimal path. Otherwise, n enters CLOSED and each neighbor m is relaxed: if g(n) + w(n, m) < g(m), update g(m), set f(m) ← g(m) + h(m), and insert or update m in OPEN.

Admissibility vs. Consistency (Monotonicity)

Two mathematical properties of h : V → ℝ_≥0 govern optimality and node-expansion complexity:

1. Admissibility: h never overestimates the true remaining cost:

Under admissibility, A* returns an optimal solution C* because any suboptimal goal t′ has f(t′) = g(t′) > C*, whereas a frontier node n on an optimal path satisfies f(n) = g*(n) + h(n) ≤ C* and is extracted first.

1. Consistency (Monotonicity): For every edge (u, v) ∈ E, h satisfies the triangle inequality:

Every consistent heuristic is admissible, and f(v) = g(u) + w(u, v) + h(v) ≥ g(u) + h(u) = f(u) is non-decreasing along any path.

Equivalence to Dijkstra's Algorithm via Potential Reweighting

When h is consistent, the reduced weight w_h(u, v) = w(u, v) − h(u) + h(v) ≥ 0 is non-negative on every edge (mirroring Johnson's reweighting in the Bellman-Ford algorithm) and telescopes along any path p from s to n as w_h(p) = f(n) − h(s). Executing A* with consistent h on (G, w) is therefore identical to executing Dijkstra's algorithm on (G, w_h), so the first extraction of any node u achieves g(u) = g*(u) without reopening CLOSED.

Heuristic Dominance and Spatial Metrics

Given two consistent heuristics h₁ and h₂, h₂ dominates h₁ if h₁(n) ≤ h₂(n) ≤ h*(n) for all n ∈ V. Because A* must expand every node satisfying f(n) = g*(n) + h(n) < C*, a dominating heuristic expands a subset of the nodes expanded by h₁. Moreover, the pointwise maximum h_max(n) = max(h₁(n), h₂(n)) of two admissible heuristics remains admissible and dominates both. On spatial grids, Manhattan (L₁) distance |Δx| + |Δy| is consistent on 4-neighbor orthogonal grids, Octile distance max(|Δx|, |Δy|) + (√2 − 1)·min(|Δx|, |Δy|) is consistent on 8-neighbor grids, and Euclidean (L₂) distance √(Δx² + Δy²) is consistent in any-angle continuous spaces.

To overcome the memory footprint of storing OPEN and CLOSED in large state spaces, Richard Korf's Iterative Deepening A* (IDA*, 1985) executes depth-first searches pruned whenever f(n) > τ, advancing τ in each pass to the minimum f-value that exceeded the prior threshold and reducing space complexity to O(d).

In computational biology, finding an optimal multiple sequence alignment (MSA) of k sequences of length L reduces to finding a shortest path across a k-dimensional dynamic programming hypercube of L^k vertices. Carrillo–Lipman A* MSA engines evaluate an admissible sum-of-pairs heuristic h(n) by summing precomputed pairwise alignment scores over all (k choose 2) unaligned suffixes, pruning over 99% of the hypercube while guaranteeing the global optimum. In pairwise long-read genomics, seed-heuristic A* aligners (A*PA, Groot Koerkamp & Ivanov, 2024) combine k-mer seed matches with match pruning to align megabase sequences in near-linear empirical time.

What happens if the heuristic h(n) overestimates the true cost to the goal?

When h(n) > h*(n) (an inadmissible heuristic), A* is no longer guaranteed to return a minimum-cost path because a node on the optimal path can be assigned an inflated f-value and remain unexpanded in OPEN when a suboptimal goal is popped. However, if h(n) ≤ ε·h*(n) for a constant ε > 1 (Weighted A*), the returned solution cost is bounded within ε·C*.

Why is consistency stronger than admissibility for graph search?

An admissible heuristic that violates consistency can drop sharply across an edge (u, v), causing f(v) < f(u). A node v may then be expanded first along a suboptimal path and placed into CLOSED; when the shorter path to v arrives later, A* must reopen v and propagate cost reductions to its descendants, which in pathological graphs can trigger Ω(2^|V|) re-expansions.

1. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). "A formal basis for the heuristic determination of minimum cost paths." IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. https://doi.org/10.1109/TSSC.1968.300136
2. Dechter, R., & Pearl, J. (1985). "Generalized best-first search strategies and the optimality of A*." Journal of the ACM, 32(3), 505–536. https://doi.org/10.1145/3828.3830
3. Korf, R. E. (1985). "Depth-first iterative-deepening: An optimal admissible tree search." Artificial Intelligence, 27(1), 97–109. https://doi.org/10.1016/0004-3702(85)90084-090084-0)
4. Goldberg, A. V., & Harrelson, C. (2005). "Computing the shortest path: A* search meets graph theory." Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 156–165. https://doi.org/10.5555/1070432.1070455
5. Groot Koerkamp, R., & Ivanov, P. (2024). "Exact global alignment using A* with seed heuristic and match pruning." Bioinformatics, 40(Supplement_1), i202–i211. https://doi.org/10.1093/bioinformatics/btae253