4.7 Uninformed search
Standard classical-AI course material — written August 2026
What this is and why it exists
Five strategies, and they differ in exactly one thing: which state on the fringe gets expanded next. From that single choice, completeness, optimality and memory cost diverge enormously — which is the most economical demonstration in this whole unit that a small design decision can decide whether an algorithm is usable. Trace each of them by hand on one small graph, once, and the differences stop being a table to memorise.
The vocabulary
- Uninformed — using no information about the problem beyond its definition.
- Fringe — the states generated but not yet expanded.
- Expand — generate a state's successors and add them to the fringe.
- Tree search — searching without remembering where you have been.
- Graph search — searching while keeping a record of visited states.
- Repeated state — a state reached again by a different path.
- Depth limit — a cut-off beyond which a path is not extended.
- Step cost — what one action costs.
The mental model
Every one of these algorithms is the same loop. Take a state off the fringe; if it passes the goal test, stop; otherwise expand it and put its successors on the fringe. The only difference between the five is which state gets taken off next, and it is worth holding that firmly, because it means the differences in behaviour are consequences of one line rather than of five separate algorithms.
First, the distinction that decides whether an algorithm terminates at all. Tree search keeps no record of where it has been, so a state reachable by two paths is explored twice, and a cycle is followed forever. Graph search keeps a set of already-expanded states and refuses to expand any of them again. On a graph with cycles — which includes almost every real problem, since most actions can be undone — tree search does not merely waste effort, it fails to terminate. The cost of the fix is memory proportional to the states visited, which is real; the benefit is termination and, in spaces where many paths lead to the same place, an enormous reduction in work.
Breadth-first expands the shallowest unexpanded state, achieved with a first-in, first-out fringe: successors go on the back, expansion takes from the front, so the whole of one level is done before the next begins. It is complete, and it finds the solution with the fewest steps. Its cost is memory: it must hold an entire level of the space at once, and the last level is the largest. This is the algorithm that fails on space rather than time, and the failure is abrupt.
Uniform-cost expands the state with the cheapest path so far. When every step costs the same, this is breadth-first with extra bookkeeping. When steps differ in cost, the two come apart, and the distinction matters: a solution with the fewest steps is not the cheapest solution when steps have different costs. Uniform-cost is optimal for cost, which is what you want on a road map where the roads have lengths. It also needs the goal test applied when a state is selected for expansion rather than when it is generated — testing on generation returns the first goal found rather than the cheapest path to it, which is the classic error in implementing this method.
Depth-first expands the deepest unexpanded state, achieved with a last-in, first-out fringe. Its virtue is memory: it holds only the current path and the unexplored siblings along it, which grows with depth rather than exponentially, and that difference is the reason it exists. Its failures are two. In an infinite or very deep space it goes down forever and never returns — it is not complete. And it is not optimal: it returns the first solution it stumbles on, which may be far deeper than the shallowest.
Depth-limited search is depth-first with a cut-off: do not extend a path beyond a set depth. That fixes the infinite descent — the search always terminates. It introduces the other failure in exchange: if the limit is smaller than the solution depth, the search terminates having found nothing, and the solution was there. So you must know something about the solution depth to choose the limit, and if you knew that you would already know more than an uninformed search is supposed to assume.
Iterative deepening resolves this, and it is the strategy people skip. Run a depth-limited search with a limit of zero, then one, then two, and so on until a solution is found. It is complete, it finds the shallowest solution, and its memory cost is that of depth-first — which is the combination you actually want.
The objection is obvious: it repeats work, re-expanding the shallow levels once for every increase in the limit. The answer is that the repetition costs much less than it appears, because in a tree with a branching factor above one, the bottom level contains most of the states. Re-generating every level above the last is a modest overhead on top of generating the last level once, and the ratio improves as the branching factor grows. You pay a small constant factor in time and you save an exponential factor in memory. That is why it is the usual default for uninformed search on a large space, and why it is a standard interview question.
| Strategy | Complete | Optimal | Time | Space |
|---|---|---|---|---|
| Breadth-first | Yes | Fewest steps only | Exponential in solution depth | Exponential in solution depth |
| Uniform-cost | Yes | Yes, by cost | Exponential | Exponential |
| Depth-first | No | No | Exponential in maximum depth | Linear in maximum depth |
| Depth-limited | Only if limit is deep enough | No | Exponential in the limit | Linear in the limit |
| Iterative deepening | Yes | Fewest steps only | Exponential in solution depth | Linear in solution depth |
Reconstruct that table from the reasoning rather than memorising it. Completeness follows from whether the strategy can miss part of the space or descend forever. Optimality follows from the order states are reached in. Space follows from how much of the fringe must be held at once — a whole level, or one path. Every entry is a consequence of which state gets expanded next.
What you should now be able to explain or do
State the common loop and say what distinguishes the five. Explain the repeated-state problem and why tree search fails to terminate on cyclic graphs. Trace breadth-first with a first-in, first-out fringe and uniform-cost when costs differ, and say where the two diverge. Say why uniform-cost must test the goal on expansion rather than on generation. Trace depth-first and depth-limited and name each one's failure. Give the argument for why iterative deepening's repeated work is cheap. Reconstruct the comparison table from the reasoning.
Check yourself
What actually differs between these five algorithms?
Which state is taken off the fringe next. Everything else — completeness, optimality, time and space — follows from that one choice.
Why does tree search fail on a graph with cycles?
It keeps no record of visited states, so it follows a cycle forever and never terminates. Since most actions can be undone, nearly every real problem has cycles.
When do breadth-first and uniform-cost come apart?
When step costs differ. Fewest steps and cheapest path are then different solutions, and only uniform-cost finds the cheapest.
What does adding a depth limit fix, and what does it break?
It fixes infinite descent, so the search always terminates. It breaks completeness — if the limit is shallower than the solution, the search reports nothing while the solution was there.
Why is iterative deepening's repeated work acceptable?
Because in a tree with a branching factor above one, most states are in the bottom level. Re-generating everything above it is a small constant overhead, and in exchange the memory cost drops from exponential to linear.
Go deeper
We haven't checked most of these for screen reader use yet.
- Week 0 Search · Harvard CS50 · Videovideo, with transcript