Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 46 ยท Informed Search

A* Search

Learn A* search step by step: the f = g + h rule, a heapq implementation with path reconstruction, grid maps, the 8-puzzle and why A* is optimal.

Uniform-cost search is careful: it never forgets what a path has already cost. Greedy best-first search is quick: it never forgets what the goal looks like. Each ignores half of the picture. A* (pronounced "A-star") uses both halves at once, and since its publication in 1968 it has become the most widely used pathfinding and planning algorithm in the world, running inside map apps, video games, warehouse robots and puzzle solvers.

The idea fits on one line. For every node n on the frontier, compute

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

where g(n) is the exact cost from the start to n and h(n) is the heuristic estimate from n to the goal. So f(n) is the estimated cost of the cheapest solution that passes through n. A* always expands the frontier node with the smallest f. If h never overestimates the true remaining cost, the first time the goal is popped from the frontier, its path is guaranteed to be cheapest.

The algorithm

A* is the uniform-cost skeleton from the previous lessons with one change: the priority is g + h instead of g. Everything else is the same bookkeeping.

flowchart TD
    A["Put start in the frontier<br/>with f = h(start)"] --> B{"Frontier empty?"}
    B -- yes --> F["Fail: no solution"]
    B -- no --> C["Pop the node with the smallest f"]
    C --> D{"Is it a goal?"}
    D -- yes --> E["Rebuild the path<br/>from parent links and stop"]
    D -- no --> G["For each successor compute g2 = g + step cost"]
    G --> H{"Cheaper than any g<br/>known for that state?"}
    H -- yes --> I["Record g2 and parent<br/>push with f = g2 + h"]
    H -- no --> B
    I --> B

The A* loop. The only difference from uniform-cost search is the priority used when pushing.

Three implementation details deserve attention:

  • A priority queue. Python's heapq keeps the smallest tuple first, so push (f, g, tie, state). The counter tie makes sure two entries with equal f never force Python to compare the states themselves, which may not be comparable.
  • Best-known g per state. If a cheaper route to a state appears later, update it and push again. The older, more expensive heap entry is stale; skip it when it pops (g > best_g[state]).
  • Parent links for the path. Store parent[state] whenever you improve best_g. At the goal, follow parents back to the start and reverse the list.

The version below is reusable: give it a way to produce neighbours (with step costs) and a heuristic, and it works for any problem.

A* on a grid map

Grid maps are the classic use. A robot or game character moves up, down, left or right on open cells (.), and walls (#) block it. Every step costs 1, and Manhattan distance to the goal is a natural heuristic: you cannot get there faster than the number of rows plus columns separating you from the goal.

Python A* on a grid map with walls

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The path costs 25 steps, and it equals the Manhattan distance from S to G (8 rows and 17 columns), so the heuristic was exactly right here. A* expanded 100 nodes. With h = 0 the very same code is uniform-cost search, and it had to expand 180. Make the walls longer, move the goal behind a wall, or change manhattan to return 0, and watch how the numbers move.

A* on the 8-puzzle

States do not have to be places. In the 8-puzzle a state is a board, a neighbour is the board after one tile slides, and every move costs 1. The program below solves a scrambled board optimally with the Manhattan heuristic. It stores, for every state, the parent and the tile that moved, so the answer can be printed as a list of moves and then replayed as a check.

Python Solving the 8-puzzle optimally

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A 24-move solution needed 1,655 expansions. Uniform-cost search would have to examine every state within 24 moves, which is a large share of all 181,440 reachable states. Because the heuristic is admissible, the 24 is not just a solution but the shortest one.

Why A* is optimal: a walkthrough

Optimality is easy to believe and easy to break, so look at it concretely. The tiny graph below has a direct but expensive edge from S to G (cost 10) and a cheaper two-step route through A (2 + 3 = 5). The first run uses an honest heuristic. The second pretends that A is 20 away from G when it is really 3, an overestimate.

Python Why overestimating breaks optimality

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

With the honest heuristic, G is first pushed with f = 10 through the bad edge, but A has f = 5, so A is popped first and offers G a better route (f = 5). Now the cheap G entry is at the top and is popped: cost 5. With the inflated h(A) = 20, node A looks hopeless (f = 22), so the expensive G (f = 10) is popped first and A* returns the cost-10 path. The algorithm did nothing wrong; it was misled.

That is the heart of the optimality proof. Suppose h never overestimates. When A* pops a goal with cost C, any better solution would have a node on the frontier whose f is at most the true cost of that better solution, which is less than C. That node would have been popped before the goal, a contradiction. So, if h is admissible, the first goal popped is optimal. The next lesson makes "admissible" precise.

What A* costs

A* is complete (on finite graphs with positive step costs) and optimal with an admissible heuristic, and it is optimally efficient in a precise sense: among all algorithms that use the same heuristic, none is guaranteed to expand fewer nodes. Its weakness is memory. It stores every generated node, so for hard problems it usually runs out of memory long before it runs out of time. The memory-bounded variants fix that, at some price in time.

When many nodes tie on f, prefer the one with larger g (deeper into the search). It is a one-token change to the heap tuple, and on grid maps with many equal-cost routes it can cut expansions dramatically.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In A* search, what does f(n) = g(n) + h(n) represent?

    g(n) is the real cost to reach n and h(n) estimates the rest, so their sum estimates the total cost of a solution through n.
  2. 2. Why does the implementation skip a popped entry when g > best_g[state]?

    heapq cannot update priorities in place, so improved routes are pushed as new entries and the older, costlier ones are discarded when they reach the top.
  3. 3. What happens to A* with h(n) = 0 for every node?

    With h = 0 the priority is just g, which is exactly uniform-cost search.
  4. 4. In the walkthrough, why did the inflated heuristic h(A) = 20 produce a cost-10 answer?

    An overestimating heuristic makes good nodes look bad. The expensive goal entry was popped first, so optimality was lost.

Summary

  • A* orders the frontier by f(n) = g(n) + h(n): cost so far plus estimated cost to go.
  • Implement it with heapq, a tie-breaking counter, a best-g table and parent links; skip stale entries when popped.
  • The same code solves grid maps and the 8-puzzle; only neighbours and h change.
  • With an admissible heuristic the first goal popped is optimal; with h = 0 A* is uniform-cost search.
  • The main limit is memory, because A* keeps all generated nodes.

Next, learn exactly which heuristics are safe in Admissible and Consistent Heuristics.