A* Search Algorithm

The Simplest Explanation

Imagine you're lost in a city and want to reach your hotel. You have two pieces of information:

1. How far you've already walked (you know this exactly)
2. How far the hotel looks from where you are (you can see the skyline and estimate)

A* says: always pick the next move that minimizes (distance walked so far) + (estimated distance remaining).

That's it. If you remember nothing else, remember this: pick the node with the smallest "cost so far + guess to goal".

$f(n) = g(n) + h(n)$

• $g(n)$ = exact cost from start to $n$ (this is known, no guessing)
• $h(n)$ = estimated cost from $n$ to goal (this is the guess/heuristic)
• $f(n)$ = total estimated cost of the best path through $n$

Why A* Works (Intuition)

Think of it this way:

• If you only use $g(n)$ (ignore the guess), you get Dijkstra's algorithm — it explores in every direction equally, like flood fill. It works but is slow because it wastes time going the wrong way.
• If you only use $h(n)$ (ignore the cost so far), you get Greedy Best-First Search — it beelines toward the goal but might find a suboptimal path because it doesn't account for how expensive its route has been.
• A combines both* — it heads toward the goal (thanks to $h$) but doesn't take unnecessarily expensive routes (thanks to $g$).

The Algorithm (Step by Step)

1. Put the start node in the open list with $g = 0$, $f = 0 + h(\text{start})$
2. While the open list is not empty:
   • Pick the node with the lowest $f(n)$ from the open list — call it current
   • If current is the goal → done! Reconstruct path
   • Move current to the closed list
   • For each neighbor of current:
     • Calculate $g(\text{neighbor}) = g(\text{current}) + \text{edge cost}$
     • Calculate $f(\text{neighbor}) = g(\text{neighbor}) + h(\text{neighbor})$
     • If neighbor is in closed list with a lower $g$ → skip
     • If neighbor is in open list with a lower $g$ → skip
     • Otherwise → add (or update) neighbor in the open list
3. If open list is empty and goal not found → no path exists

Admissibility and Consistency

Admissibility

A heuristic $h$ is admissible if it never overestimates the true cost to the goal:

$0 \leq h(n) \leq h^*(n) \quad \text{for all } n$

where $h^*(n)$ is the actual optimal cost from $n$ to the goal.

Why it matters: If $h$ is admissible, A* is guaranteed to find the optimal solution. If $h$ overestimates even once, A* might skip the optimal path.

Consistency (Monotonicity)

A heuristic is consistent if for every node $n$ and its successor $n'$ reached by action $a$:

$h(n) \leq c(n, a, n') + h(n')$

This means: the heuristic drop from $n$ to $n'$ is never more than the actual step cost.

Consistency implies admissibility (but not vice versa). Consistency also guarantees that A* never needs to re-open nodes from the closed list.

Properties Summary

Where $b$ = branching factor, $d$ = depth of the shallowest goal.

How to Design Good Heuristics

Method 1: Relaxed Problems

Remove constraints from the original problem. The optimal cost in the relaxed problem is an admissible heuristic for the original.

Example: In the 8-puzzle, if you relax "only one tile can move into the blank" to "tiles can move anywhere", you get the Misplaced Tiles heuristic. If you further relax "tiles move one step at a time" to "tiles teleport", you get the Manhattan Distance heuristic.

$h_{\text{misplaced}}(n) \leq h_{\text{manhattan}}(n) \leq h^*(n)$

A more informed heuristic (higher but still $\leq h^*$) dominates a less informed one and leads to fewer node expansions.

Method 2: Pattern Databases

Precompute optimal solution costs for sub-problems and store in a lookup table. The maximum of multiple pattern database heuristics is also admissible and more informed.

Dominance

If $h_2(n) \geq h_1(n)$ for all $n$ and both are admissible, then $h_2$ dominates $h_1$. A* with $h_2$ will never expand more nodes than with $h_1$.

$h_1(n) \leq h_2(n) \leq h^*(n) \implies h_2 \text{ dominates } h_1$

Worked Example: Step-by-Step Trace

Here's an 8-node graph. Start at S, goal is G. Heuristic values are shown in the table.

The edge costs are shown on the graph below. Click through each step to see how A* expands nodes:

Key Observations from This Trace

1. Tie at step 1: After expanding S, nodes A, B, C all have $f = 10$. We break ties by preferring lower $g$ (closer to start → more progress made), so A is expanded first.
2. Path update at step 3: When B is expanded, node E already has $g = 9$ (via A), but the path S→B→E gives $g = 8$ (cheaper). A* updates E's $g$-value. This is why we check the open list before skipping.
3. Suboptimal path rejection: The path S→A→E→G costs $3 + 6 + 4 = 13$, but A* finds S→A→D→G costs $3 + 4 + 5 = 12$. Both are explored but only the optimal one is returned.
4. Goal not expanded immediately: Even after G enters the open list, A* continues expanding nodes with $f < f(G) = 12$ (like E with $f = 10$). Only when G has the lowest $f$ is it selected — guaranteeing optimality.

Exam Practice: Harder Question

This is a Stanford/IIT-level question. The graph has a non-trivial structure where the "obvious" greedy path is not optimal. Try to solve it yourself before clicking "Show Solution".

Given: Find the shortest path from P to Z using A* search.

Why This Question Is Tricky

1. The greedy trap: Going P→Q seems attractive because $h(Q) = 6$ is lower than $h(R) = 7$, but the optimal path goes through R first.
2. Multiple paths to same node: Both Q and R can reach U. A* must correctly determine that R→U is cheaper than Q→T→U.
3. Path cost verification: P→Q→T→V→Z = 4+3+3+3 = 13 vs P→R→U→V→Z = 2+5+2+3 = 12. The first path looks "more direct" in the graph but is 1 unit more expensive.