A* Search Deep Dive, in depth: the optimality proof, consistency as reduced costs, measuring heuristics, open-list engineering and heuristics from relaxations

The algorithm, instrumented

A* searches from a start s towards a goal t over non-negative edge costs w(u,v). It keeps g(n), the cost of the best path to n found so far, and a heuristic h(n) estimating the remaining cost to t. It always expands the open node with the smallest f(n) = g(n) + h(n). With h = 0 it is exactly Dijkstra's algorithm. The reference implementation below uses a binary heap with lazy deletion and counts expansions and stale pops so you can measure it.

import heapq

def astar(start, goal, succ, h):
    """succ(n) yields (m, w) pairs; h(n) estimates cost from n to goal."""
    g = {start: 0}
    parent = {start: None}
    open_ = [(h(start), 0, start)]          # (f, g, node)
    closed = set()
    expanded = stale = 0
    while open_:
        f, gn, n = heapq.heappop(open_)
        if n in closed or gn > g[n]:        # an outdated duplicate entry
            stale += 1
            continue
        if n == goal:
            path = []
            while n is not None:
                path.append(n)
                n = parent[n]
            return gn, path[::-1], expanded, stale
        closed.add(n)
        expanded += 1
        for m, w in succ(n):
            ng = gn + w
            if ng < g.get(m, float("inf")):
                g[m], parent[m] = ng, n
                closed.discard(m)           # reopen: only matters if h is inconsistent
                heapq.heappush(open_, (ng + h(m), ng, m))
    return None, None, expanded, stale

Two details matter. The goal test happens when the goal is popped, not when it is first generated; testing on generation returns the first path found, which is not necessarily the cheapest. And the closed.discard(m) line is what makes this version correct for admissible but inconsistent heuristics; with a consistent heuristic it never fires.

Why admissible heuristics give optimal paths

Admissible means h never overestimates: h(n) is at most the true remaining cost h*(n) for every n. That alone is enough for A* to return an optimal path, provided it may reopen nodes. The proof is short. Let C* be the optimal cost and suppose the goal is popped with g(t) greater than C*. Take any optimal path. Before the goal is popped, some node n on that path is on the open list with g(n) equal to its optimal cost; the start is such a node, and each time one is expanded its successor on the path becomes one. Then f(n) = g(n) + h(n) is at most g(n) + h*(n) = C*, which is smaller than f(t) = g(t). The heap would have popped n before t. Contradiction.

The same argument gives the expansion picture. For a consistent h, A* must expand every node with f(n) below C* (any of them could start a cheaper path, as far as the algorithm knows), may expand some with f(n) equal to C* depending on tie-breaking, and never expands one with f(n) above C*. If h2 is at least h1 everywhere and both are admissible, h2 dominates: every node A* must expand with h2 it must also expand with h1. A better heuristic can only shrink the search, apart from ties.

Consistency is Dijkstra on reduced costs

Consistent means h(u) is at most w(u,v) + h(v) for every edge, with h(t) = 0. It is a triangle inequality. Consistency implies admissibility: sum the inequality along an optimal path from n to t. The converse fails; the next section shows what that costs.

The cleanest way to see what consistency buys is reweighting. Define the reduced cost w'(u,v) = w(u,v) - h(u) + h(v). Consistency says exactly that every reduced cost is non-negative. Along any path from s to n, reduced costs telescope: the reduced length is the real length plus h(n) - h(s). So shortest paths are the same in both graphs, and Dijkstra on the reduced graph pops nodes in order of g(n) + h(n) - h(s), which is f(n) minus a constant. A* with a consistent heuristic is Dijkstra on reduced costs.

Everything you know about Dijkstra transfers. Each node is expanded at most once with optimal g, and popped f values never decrease. Johnson's algorithm uses the same reweighting, which is why h is often called a potential function. If you want the Dijkstra side of that argument in full, see Dijkstra, classic and deep.

Inconsistent heuristics and reopening

Admissible but inconsistent heuristics are not exotic. Taking the maximum of several lookups with random selection, using a heuristic learned by a model, or combining pattern databases in some ways can all violate the triangle inequality while still never overestimating. A* remains optimal if it reopens closed nodes whose g improves, but it loses the expand-once property. Martelli showed in 1977 that with inconsistent heuristics the number of re-expansions can be exponential in the worst case.

Three practical responses. Measure first: count reopenings, as in the code above; often they are rare. Repair the heuristic where cheap, for example by propagating h(v) = max(h(v), h(u) - w(u,v)) along each generated edge (pathmax), which helps in many domains but is not a full fix in general graphs. Or accept a bounded-suboptimal answer by not reopening, which some planners do deliberately when reopening costs more than the small loss in path quality.

Worked example: measuring heuristics on the 8-puzzle

To compare heuristics you need a number that does not depend on the particular instance. The standard one is the effective branching factor b*: if A* expanded N nodes to find a solution of depth d, b* is the branching factor of a uniform tree of depth d with N nodes, that is, N = b* + b*^2 + ... + b*^d. Solve it by bisection. A perfect heuristic gives b* close to 1. The point is that b* is stable across depths for a given heuristic, so it predicts how the search will scale.

The experiment below runs A* on 20 random 8-puzzle instances (start states generated by 60 random moves from the goal, seed 7) with three heuristics: h = 0 (Dijkstra), the number of misplaced tiles, and the sum of Manhattan distances. All three are consistent and all three return the same optimal depths.

def h_misplaced(s):
    return sum(1 for i, t in enumerate(s) if t and t != GOAL[i])

def h_manhattan(s):
    d = 0
    for i, t in enumerate(s):
        if t:
            r, c = divmod(i, 3)
            gr, gc = POS[t]                 # goal row and column of tile t
            d += abs(r - gr) + abs(c - gc)
    return d

def ebf(n, d):                              # solve n = b + b^2 + ... + b^d for b
    lo, hi = 1.0, 10.0
    for _ in range(60):
        b = (lo + hi) / 2
        lo, hi = (b, hi) if sum(b ** i for i in range(1, d + 1)) < n else (lo, b)
    return lo

Manhattan distance expands about 47 times fewer nodes than Dijkstra and 10 times fewer than misplaced tiles, on the same instances, for the same optimal answers. The effective branching factors are computed from the mean expansions and the depth rounded to 23. The gap between 1.47 and 1.32 looks small and is not: at depth 23 it is a factor of about ten, and it compounds with every extra level of depth. Manhattan dominates misplaced tiles (each misplaced tile is at least one move from home), so this is the dominance result above, measured. With unit costs and consistent heuristics no stale entries were popped in this run; on weighted graphs with duplicate pushes you will see them, and the counter tells you how much heap traffic they cost.

Engineering the open list

Most A* time goes to the open list and the closed set. Three options for the open list:

• Binary heap with lazy deletion, as above. Simple, cache-friendly, and the usual winner. Cost: the heap can hold duplicates, bounded by the number of edge relaxations that improve g.
• Indexed heap with decrease-key. No duplicates, so memory is bounded by the open set, but every relaxation updates a position map. Worth it when memory is the binding constraint or when improvements are very frequent. See priority queues and heaps for the mechanics.
• Bucket queue. When edge costs are small integers and h is consistent, f values are integers that never decrease, so an array of buckets indexed by f, scanned forward, gives constant-time push and amortized constant-time pop. This is Dial's idea applied to A*; it is the same reasoning as 0-1 BFS for costs of 0 and 1. Within a bucket, prefer larger g (a LIFO stack per bucket approximates this) to reach the goal sooner among ties.

The closed set and the g map are usually hash maps keyed by state. For explicit graphs with integer ids, flat arrays are several times faster. For puzzles, pack the state into an integer (the 8-puzzle fits in 36 bits at 4 bits per tile) so hashing is cheap. Memory, not time, is what usually stops A*: it stores every generated node. When that bites, the answer is IDA* or a memory-bounded variant, covered on the variants page.

Where strong heuristics come from

Good heuristics are almost always exact solutions of a relaxed problem: remove a constraint, solve what is left optimally, and use that cost. Removing every constraint except "a tile must move to its square" gives misplaced tiles; allowing tiles to slide through each other gives Manhattan distance. Any optimal cost of a relaxation is admissible, because every real solution is also a solution of the relaxation, and it is consistent whenever the relaxation's cost satisfies the triangle inequality, which shortest-path costs always do.

Pattern databases push relaxation further. Pick a subset of tiles, treat the rest as indistinguishable, and solve the abstracted puzzle backwards from the goal by breadth-first search, storing the cost of every abstract state in a table. At search time, h is one lookup. Culberson and Schaeffer introduced them for the 15-puzzle; disjoint pattern databases that count only moves of their own tiles can be added together and stay admissible.

Landmarks (ALT) do the same for road networks and other explicit graphs. Precompute exact distances from a handful of landmark nodes L to every node. For a directed graph, the triangle inequality gives h(v) = max over L of max(d(L,t) - d(L,v), d(v,L) - d(t,L)), a lower bound on d(v,t) that is consistent. Landmarks on the periphery of the graph work best, because they put the goal "behind" many nodes. The cost is memory: one distance per node per landmark.

def alt_heuristic(dist_from, dist_to, target):
    """dist_from[L][v] = d(L, v); dist_to[L][v] = d(v, L); precomputed per landmark L."""
    def h(v):
        best = 0
        for L in dist_from:
            best = max(best,
                       dist_from[L][target] - dist_from[L][v],
                       dist_to[L][v] - dist_to[L][target])
        return best
    return h

Failure modes

• Goal test on generation. Returns a path that may not be optimal. Test when the goal is popped.
• Overestimating heuristic by accident. Euclidean distance multiplied by a speed factor, or Manhattan distance on a grid that allows diagonal moves, overestimates and silently breaks optimality. Check admissibility with a brute-force comparison on small instances.
• Inconsistent heuristic without reopening. Optimal paths are missed. Either reopen or prove consistency.
• Heap blow-up from duplicates. Lazy deletion with many improvements can push the heap well past the node count. Watch the stale-pop counter.

Trade-offs

What to do next

1. Write down your heuristic as the optimal cost of a named relaxation; if you cannot, test it for admissibility against brute force on small instances.
2. Check consistency on every edge of a sample graph with an assertion; if it fails, keep the reopening line and count how often it fires.
3. Instrument your A* with expansion, stale-pop and reopen counters and compute the effective branching factor on a benchmark set.
4. Rebuild the 8-puzzle experiment: add the goal tuple, a succ that swaps the blank and yields (state, 1), and a seeded 60-move scramble that never undoes its last move; then add linear conflict.
5. If your graph is a fixed road or network graph, try 8 to 16 peripheral landmarks and compare expansions with Euclidean distance.
6. If costs are small integers, replace the binary heap with a bucket queue and measure the time per expansion.