4.7 Uninformed search
You can trace breadth-first, depth-first, uniform-cost, depth-limited and iterative-deepening search, and say which one a problem needs.
Before:01. Mathematics for Machine Learning02. Python — Basics to Advanced
Five uninformed strategies differ only in which node they expand next, yet their completeness, optimality and memory costs differ enormously — and tracing each by hand on the same small graph once makes the differences permanent knowledge. The repeated-state problem is what separates tree search from graph search. It sits at the start of the algorithms run because informed search is these methods plus guidance. The practical default earns its place: iterative deepening, which looks wasteful and almost never is.
Work through these
Distinguish tree search from graph search, and handle the repeated-state problem
Tree search can revisit the same situation forever; graph search remembers where it has been. Handling repeated states is the difference between an algorithm that terminates and one that does not.
Trace breadth-first search with a FIFO fringe, and uniform-cost search when step costs differ
Expanding the shallowest node first finds the shortest solution in steps, and expanding the cheapest path first finds the cheapest when steps differ in cost. The two coincide only when every step costs the same.
Trace depth-first and depth-limited search, and say where each one fails
Going as deep as possible first uses very little memory and can miss a solution entirely or run forever. Adding a depth limit fixes the second problem and can introduce the first.
Explain why iterative deepening is usually the right default
Repeating a depth-limited search with increasing limits gets the memory behaviour of one method and the guarantees of the other, at surprisingly little extra cost. This is why it is the usual default.
Compare all five on completeness, optimality, time and space
Setting all five methods against the four criteria in one table. That comparison is what you should be able to reconstruct from understanding rather than memory.
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.