4.8 Informed search: greedy best-first and A*
You can trace greedy best-first search and A* on a road map, and say where each one breaks.
Before:01. Mathematics for Machine Learning02. Python — Basics to Advanced
A-star is the algorithm everyone quotes and few can justify: the evaluation adds what a path has already cost to what it is guessed to still cost, and greedy best-first — which drops the first half — shows exactly why both halves matter by getting stuck. This topic traces both on a road map, where the bookkeeping is the whole lesson. It sits at the centre of the search run. The honest limit closes it: A-star's memory appetite is what breaks it in practice, and knowing that is part of knowing the algorithm.
Work through these
Define the evaluation function f(n), and explain heuristics as guidance
Informed search scores each node by an estimate of how promising it is, and the estimate is where problem knowledge enters. Everything that follows depends on how that score is built.
Run greedy best-first search and show how it gets stuck in a loop
Choosing whichever node looks closest to the goal is fast and can walk straight into a trap it cannot leave. Seeing it fail on a worked example is more instructive than the definition.
Trace A* and keep the f(n) = g(n) + h(n) bookkeeping straight
The better method adds the cost already spent to the estimate of what remains, which is what stops it being fooled by a promising direction. Keeping the two quantities separate in your bookkeeping is the practical difficulty.
Work a full A* trace on a road map
A full worked trace on a road map, which is the standard example because distances give a natural estimate. Doing it by hand once makes the method permanent.
Explain where A* runs out of memory, and what is done about it
The method keeps every generated node in memory, which is what limits it long before time does. There are variants that trade optimality for memory, and knowing they exist is enough here.
Sign in to keep your progress.
Free resources
We haven't checked most of these for screen reader use yet.
Links last checked 29 Aug 2026.
Stuck here?
Ask a mentor. A real person answers, and they can see exactly which topic you're on. Usually within a couple of working days.
Checking your session…
Topics shown in module order.