A-Star Search

A* (pronounced “A-star”) is a shortest-path algorithm with a heuristic: at each step, it expands the vertex that minimizes f(n) = g(n) + h(n), where g(n) is the actual cost so far and h(n) is a heuristic estimate of the remaining cost to the goal. With an admissible heuristic (one that never overestimates), A* is provably optimal. With a consistent heuristic, it’s also efficient (no vertex is reopened). A* is the default algorithm for game pathfinding, robotic navigation, and any “search this huge state space toward a known goal” problem — and it generalizes both Dijkstra (h = 0) and greedy best-first search (g = 0) as special cases.

1. Intuition — GPS With a Compass

Dijkstra explores outward in all directions from the source — like ripples in a pond. If you know the goal is to the northeast, that’s wasteful; ideally you’d preferentially explore northeastward.

A* adds a “compass”: a function h(n) that estimates how far node n is from the goal. It picks the next node to expand based on g(n) + h(n) — total estimated cost from source through n to goal — instead of just g(n) (Dijkstra) or just h(n) (greedy best-first, which is fast but not optimal).

If your heuristic is perfect (h gives exact remaining distance), A* explores only nodes on the optimal path. If your heuristic is terrible (h = 0), A* degenerates into Dijkstra. Real heuristics fall between the two; A*‘s practical speedup over Dijkstra depends on heuristic quality.

2. The Two Cost Functions

For each node n:

• g(n) = exact cost from source to n along the best path found so far.
• h(n) = heuristic estimate of cost from n to goal. Computed by the user; the algorithm doesn’t know the true remaining cost.
• f(n) = g(n) + h(n) = estimated total cost of the cheapest path from source to goal that goes through n.

A* always expands the open-set node with the smallest f(n). Intuitively: it pursues the route that seems cheapest right now, where “seems” combines hard data (g) with a forecast (h).

3. Pseudocode

a_star(graph, source, goal, h):
    g_score := map node → ∞
    g_score[source] := 0
    f_score := map node → ∞
    f_score[source] := h(source)
    open_set := min-heap of (f_score, node)
    push (f_score[source], source) onto open_set
    while open_set is not empty:
        (_, current) := pop min from open_set
        if current == goal:
            return reconstruct_path(came_from, current)
        for each (neighbor, w) in graph[current]:
            tentative_g := g_score[current] + w
            if tentative_g < g_score[neighbor]:
                came_from[neighbor] := current
                g_score[neighbor] := tentative_g
                f_score[neighbor] := tentative_g + h(neighbor)
                push (f_score[neighbor], neighbor) onto open_set
    return failure                            # goal unreachable

4. Python Implementation

import heapq
 
def a_star(graph, source, goal, h):
    """graph: dict node -> list of (neighbor, weight). h: callable node -> heuristic."""
    g = {source: 0}
    came_from = {source: None}
    open_set = [(h(source), source)]
    while open_set:
        _, current = heapq.heappop(open_set)
        if current == goal:
            return reconstruct(came_from, current), g[current]
        for nbr, w in graph[current]:
            tentative_g = g[current] + w
            if tentative_g < g.get(nbr, float('inf')):
                g[nbr] = tentative_g
                came_from[nbr] = current
                f = tentative_g + h(nbr)
                heapq.heappush(open_set, (f, nbr))
    return None, float('inf')
 
def reconstruct(came_from, node):
    path = []
    while node is not None:
        path.append(node)
        node = came_from[node]
    return path[::-1]

This is essentially Dijkstra’s Algorithm with f = g + h instead of f = g as the heap key. The structural similarity is no accident: A* with h = 0 is Dijkstra.

5. Admissibility — The Optimality Condition

A heuristic h is admissible iff it never overestimates the true cost:

For every node n: h(n) ≤ true_cost(n, goal)

Theorem: If h is admissible, A* finds an optimal path.

Proof sketch. Suppose A* returns a suboptimal path P with cost C. Let OPT be the true optimum cost. There must exist a node n on the optimal path that’s still in the open set when A* terminated (because A* terminates by popping goal, but if there’s a better path through some n, A* would have picked n first). For that n, f(n) = g(n) + h(n) ≤ g(n) + true_cost(n, goal) = OPT < C = f(goal). So n should have been popped before goal — contradiction.

The intuition: with h ≤ true_remaining, the f estimate is a lower bound on the actual total cost through n. We never expand a node whose lower bound exceeds the actual cost of a known-finished goal.

6. Consistency (Monotonicity) — The Stronger Condition

A heuristic is consistent (also called monotonic) iff:

For every edge (n, n') with cost w: h(n) ≤ w + h(n').

(I.e., the triangle inequality holds for the heuristic.)

Consistency implies admissibility. And consistency is a stronger guarantee: with a consistent heuristic, once a node is closed (popped from the open set), its g_score is final — A* never reopens it. The algorithm becomes essentially equivalent to Dijkstra over a reweighted graph.

With merely admissible-but-inconsistent heuristics, A* may need to reopen previously closed nodes (because a cheaper route to them is discovered later). Implementations should handle this — but in practice, almost every useful heuristic is consistent, so the reopening case is rare.

In practice, focus on consistency

The “admissible vs consistent” distinction matters mostly for academic correctness arguments. Most natural heuristics (Euclidean distance, Manhattan distance, straight-line distance) are consistent. When you design a custom heuristic, verify consistency rather than just admissibility — it’s easier to reason about and avoids the reopening complexity.

7. Common Heuristics

7.1 Grid Pathfinding

For a 2D grid where movement costs 1 per step:

• Manhattan distance |dx| + |dy| — admissible if movement is restricted to 4 directions (no diagonals). The standard choice for orthogonal-only grids.
• Chebyshev distance max(|dx|, |dy|) — admissible if 8-directional movement is allowed at uniform cost.
• Diagonal distance (|dx| + |dy|) + (√2 - 2) · min(|dx|, |dy|) — admissible for 8-directional movement when diagonal moves cost √2.
• Euclidean distance √(dx² + dy²) — admissible for any-angle movement; pessimistic (under-estimates more) than the above for grid-restricted movement.

7.2 Road Networks

• Straight-line distance (great-circle for spheres) — admissible because the road graph can’t beat the geodesic.
• Landmark-based heuristics (ALT) — precompute exact distances from selected “landmark” nodes; use the triangle inequality to derive distance estimates. State-of-the-art in many road routing systems.

7.3 Puzzles (e.g., 15-Puzzle)

• Misplaced tiles count — admissible (each misplaced tile must move at least once).
• Sum of Manhattan distances of every tile to its goal position — admissible and much tighter than misplaced-tiles. The standard choice.
• Walking-distance heuristic — even tighter, but expensive to compute.
• Pattern databases — precompute exact subgoal costs; admissible by construction.

7.4 Generic / “I Don’t Know”

• h(n) = 0 — degenerate; A* becomes Dijkstra. Use when no useful heuristic is available.

8. A* Generalizes Other Algorithms

Special case	Equivalent to
h(n) = 0	Dijkstra’s Algorithm (uniform-cost search)
h(n) = true distance	Direct goal traversal — explores only optimal path
g(n) = 0, f = h	Greedy best-first search — fast but not optimal
h ignored, BFS	Breadth-First Search (uniform edge cost)

This is why A* is taught as the general informed search algorithm: turn knobs and you get every other shortest-path strategy as a corollary.

9. Memory-Bounded Variants

A* keeps every visited node in memory. For huge state spaces, this can exhaust RAM.

9.1 IDA* (Iterative Deepening A*)

Like iterative deepening DFS but with f cost as the depth bound. Repeatedly does depth-bounded DFS; each iteration uses a higher f threshold (set to the smallest f value pruned in the previous iteration). Memory: O(d) where d is the search depth. Often exponentially less memory than A* at the cost of repeated work.

Used historically for the 15-puzzle and Rubik’s cube.

9.2 SMA* (Simplified Memory-Bounded A*)

Maintains a fixed memory budget. When the budget is reached, drop the worst-f leaf and back up its f to its parent. Complex but bounded.

9.3 Beam Search

Keep only the k best nodes in the open set; discard the rest. Not optimal — but often fast enough for practical applications.

10. Tiny Worked Example — Manhattan Distance on a Grid

3x3 grid, start at top-left (0,0), goal at bottom-right (2,2). All cell traversals cost 1, 4-directional movement.

S . .
. . .
. . G

Heuristic h(r, c) = (2 - r) + (2 - c) (Manhattan distance to goal).

Initial: g(S) = 0, h(S) = 4, f(S) = 4. Open set: [(4, S)].

Step 1: Pop S. Expand neighbors (0,1) and (1,0). Both have g = 1, h = 3, f = 4. Push both.

Step 2: Pop (0,1) [tied f=4, pop order tiebreaker]. Expand (0,2) [f=1+2=3+? wait let me recompute] and (1,1).

• (0,2): g=2, h=(2-0)+(2-2)=2, f=4
• (1,1): g=2, h=2, f=4

Step 3: Continue popping nodes with f=4 (the lower bound on the optimal cost). All optimal-path nodes have f = 4.

The trace highlights: with Manhattan distance, every optimal-path node has the same f value (= optimum). A* expands those nodes; non-optimal-path nodes have higher f and are deprioritized. With a perfect heuristic, A* would expand only the optimal path’s nodes — typically O(d) instead of O(grid size).

11. Complexity

• Worst case: O(b^d) where b is branching factor and d is goal depth — exponential. Same as uninformed search.
• Best case (perfect heuristic): O(d).
• Practical case: depends on heuristic quality. For grid pathfinding with Manhattan distance, often O(d²) to O(d · log d).
• Space: holds every visited node — O(b^d) worst case, often the binding constraint.

The “speedup over Dijkstra” depends on how informed the heuristic is — the closer to the true distance, the more dramatic the speedup. For game pathfinding, A* with Manhattan distance can be 10x-100x faster than Dijkstra on the same graph.

12. Pitfalls

12.1 Inadmissible Heuristic

If h overestimates (even by a small amount), A* may return a suboptimal path. The result will seem correct (it’s still a path) but isn’t optimal. This is a silent bug — easy to miss in testing.

12.2 Inconsistent Heuristic Without Reopen

If you use an inconsistent (admissible) heuristic but don’t handle node reopening, you may return a suboptimal path. Either ensure consistency or maintain a “closed set” with a way to reopen.

12.3 Heuristic Too Slow to Compute

If h(n) is expensive (e.g., requires a precomputed distance table), the heuristic computation can dominate the algorithm. The benefit of A* is fewer expansions, not free per-expansion work. Some pre-amortization (e.g., landmarks computed once, then queried in O(1)) is necessary for huge graphs.

12.4 Diagonal Moves with Manhattan

If your grid allows diagonal moves at cost √2 but you use Manhattan distance, the heuristic overestimates the diagonal-allowed shortest path → inadmissible → suboptimal results. Use Chebyshev or octile distance instead.

12.5 Tie-Breaking

When multiple nodes have the same f, the choice between them affects efficiency (not correctness). Tiebreaking by higher g (or equivalently lower h) — i.e., preferring nodes “closer to goal” — usually expands fewer nodes in practice.

12.6 Re-Computing h Every Time

h(n) is called repeatedly. Memoize if expensive.

12.7 Overflow / Negative g

A* assumes non-negative edge weights (inherited from Dijkstra’s structure). Negative weights break the algorithm.

12.8 Forgetting the Closed Set

Without tracking which nodes have been popped (closed), A* can re-process them and waste work. The lazy-deletion variant (skip stale heap entries on pop) is standard.

13. Diagram — A* vs Dijkstra Expansion Pattern

flowchart LR
  subgraph "Dijkstra (h=0)"
    D[Source] -.expanding.-> Dr[All directions equally]
    Dr --> DG[Goal — eventually]
  end
  subgraph "A* (good h)"
    A[Source] -.directed expansion.-> Ar[Toward goal]
    Ar --> AG[Goal — efficiently]
  end

What this diagram shows. Dijkstra expands a “ball” of explored nodes around the source — all directions equally. A* with a good heuristic expands a “cone” pointed at the goal — most explored nodes are roughly on the optimal path, with limited exploration to confirm no better detour exists. The narrower the cone, the better the heuristic.

14. Real-World Applications

• Game AI pathfinding — by far the most common use; tile-based games use A* on the navmesh or grid.
• Robotic motion planning — A* on configuration space; often combined with sampling-based methods (RRT*).
• Routing in road networks — historically A* with great-circle heuristic; modern systems use contraction hierarchies + A*.
• Puzzle solving — 15-puzzle, Rubik’s cube (often via IDA*).
• Natural language processing — beam search is a non-optimal A* variant for decoding sequence-to-sequence models.
• AI planning — STRIPS-style planners often use A* on state space with domain heuristics.

15. Common Interview Problems

Problem	Pattern
Game-style “shortest path on grid” with custom costs	A* with Manhattan/Euclidean
8-puzzle / 15-puzzle	A* with sum of Manhattan distances
Word ladder shortest path	Often BFS suffices; A* with “edit distance to goal” works
Robot motion in obstacle field	A* on grid with obstacle handling
LC 752 — Open the Lock	BFS usually suffices, but A* possible

A* shows up less in standard LeetCode-style interviews than in systems or AI / robotics interview rounds.

16. Open Questions

• Is there a principled way to learn a heuristic from data? Yes — neural-network-guided A* and learned heuristics are an active research area.
• How does A* compare to bidirectional search? Bidirectional A* is a recognized technique; tricky to terminate correctly.

17. See Also

• Dijkstra’s Algorithm — A* with h = 0
• Breadth-First Search — A* with h = 0 and uniform weights
• Bidirectional BFS — alternative speedup
• Bellman-Ford — unrelated, but a complementary “what about negative weights” tool
• Binary Heap — A* uses a heap, same as Dijkstra
• Iterative Deepening DFS — IDA* generalizes this idea
• Big-O Notation
• SWE Interview Preparation MOC