Uninformed Search
BFS, DFS, uniform-cost and iterative deepening, compared.
Breadth-first, depth-first, uniform-cost and iterative deepening search differ in one line of code: which frontier node to expand next. That line decides whether a search finds the shortest path, the cheapest path, or runs forever, and how much memory it needs. Here you prove which is which.
What you’ll learn
- Formalize a search problem and implement the generic search loop with the right frontier data structure.
- Derive the completeness, optimality, time and space of breadth-first, depth-first, depth-limited and iterative deepening search in terms of , , and .
- Prove that uniform-cost search is optimal for positive step costs, explain why it must test for the goal at expansion, and derive its cost.
- Show that iterative deepening generates only about times as many nodes as breadth-first search.
Problems, nodes and the generic search loop
A search problem consists of a state space , an initial state , the actions available in each state, a transition model , a goal test, and a step cost . A solution is an action sequence leading from to a goal state, and an optimal solution has the lowest path cost among all solutions.
Algorithms explore by growing a search tree of nodes. A node records a state, its parent node, the action that produced it, its path cost and its depth. Nodes are not states: one state can appear at many nodes, reached by different paths. Every algorithm in this lesson runs the same loop; only the discipline of the frontier changes.
function TREE-SEARCH(problem, frontier):
frontier.add(Node(problem.initial, g = 0, depth = 0))
while frontier is not empty:
node ← frontier.pop() # the strategy lives here
if problem.is_goal(node.state): return node
for each action a in problem.actions(node.state):
s' ← problem.result(node.state, a)
frontier.add(Node(s', parent = node, action = a,
g = node.g + problem.cost(node.state, a, s'),
depth = node.depth + 1))
return failureTree-like search: it never remembers which states it has already reached, so it can revisit them. Remembering them (graph search) is the subject of a Deep Layer lesson.
| Strategy | Frontier | pop() returns |
|---|---|---|
| Breadth-first search (BFS) | FIFO queue | the oldest node, hence a shallowest one |
| Depth-first search (DFS) | LIFO stack | the newest node, hence a deepest one |
| Uniform-cost search (UCS) | priority queue on | a node with the cheapest path so far |
Four criteria judge a strategy. Completeness: does it find a solution whenever one exists? Cost optimality: is the solution it returns an optimal one? Time: how many nodes does it generate? Space: how many nodes must it store at once? The answers are stated in terms of , the maximum branching factor; , the depth of the shallowest goal; , the maximum depth of any path (possibly ); and, for costs, and the smallest step cost .
Breadth-first search
BFS expands every node at depth before any node at depth . Because the first goal it meets is at the shallowest possible depth, BFS can apply the goal test as soon as a node is generated rather than when it is expanded. This early test saves a whole layer of the tree.
Depth of a tree with branching factor holds nodes. In the worst case, with the early goal test, BFS generates every node down to depth :
The deepest layer dominates: it holds a fraction of about of all generated nodes, 90% for . Testing at expansion instead would also generate the children of nearly every depth- node before the goal is popped:
When the goal is found, the frontier holds essentially all of layer , and every generated node must be kept to reconstruct paths or detect repeats. Space equals time:
BFS runs on a problem with and the shallowest goal at depth , storing 1 KB per node. In the worst case, about how many gigabytes of memory does it need?
Show the answer
110 GB
nodes, so about 110 GB at 1 KB each. At a million nodes per second the run takes under two minutes: BFS runs out of memory long before it runs out of time. Each extra level multiplies both by 10.
Uniform-cost search
When step costs differ, the shallowest goal need not be the cheapest. UCS always expands a frontier node with the smallest path cost . It is Dijkstra's algorithm, run on a graph that is generated as the search goes rather than given in advance. The usual implementation keeps a table of the best path found to each state, so that worse paths to a known state are discarded:
function UNIFORM-COST-SEARCH(problem):
node ← Node(problem.initial, g = 0)
frontier ← priority queue ordered by g, containing node
reached ← {problem.initial: node} # best node found per state
while frontier is not empty:
node ← frontier.pop_min()
if problem.is_goal(node.state): return node # test on expansion
for each child in EXPAND(problem, node):
s ← child.state
if s not in reached or child.g < reached[s].g:
reached[s] ← child
frontier.add(child)
return failureRussell and Norvig's best-first search with priority . A stale copy of a state popped after a cheaper copy is harmless: its children are never better than what is already reached.
Order. Step costs are nonnegative, so a child is never cheaper than its parent. When a node with cost is popped, every frontier node costs at least , and so does every child added next; by induction, the popped costs never decrease.
Optimality. Take an optimal path of cost . Until its goal is expanded, some node of lies on the frontier (the first unexpanded one), with . A goal popped before it therefore satisfies
Cost. Every expanded node has , and a node at depth has , so expanded nodes have depth at most and generated ones at most one more:
With equal step costs, and the bound becomes , slightly worse than BFS with its early test. When costs vary widely, can far exceed : UCS explores many cheap, useless paths before it commits to one expensive step.
A state space contains a cycle of actions that each cost 0, such as turning in place. What can go wrong for tree-like uniform-cost search?
- Nothing: UCS is complete whenever a solution exists
- It returns a suboptimal path
- It can expand the zero-cost cycle forever, because those paths never become more expensive than the cheapest goal path
- It runs out of memory but still returns the optimal path
Show the answer
C. It can expand the zero-cost cycle forever, because those paths never become more expensive than the cheapest goal path
Completeness needs every step to cost at least , so that grows with depth. With a zero-cost cycle, infinitely many nodes have below , and tree-like UCS can keep popping them. The reached table above fixes this in finite spaces: going around the cycle never improves a state's cost, so it is never re-added.
Depth-first and depth-limited search
DFS always expands a deepest frontier node. Tree-like DFS only needs the current path plus the unexpanded siblings of each node on it, at most nodes; a backtracking version that generates one successor at a time needs only the path, . That frugality is DFS's whole appeal.
The price is paid in guarantees. If some path is infinite (), or tree-like search walks around a cycle, DFS can dive forever and miss a shallow goal. In a finite state space, DFS that skips states already on its current path is complete, but it returns the first solution it reaches, which may be far from optimal, and its time is , terrible when .
Depth-limited search (DLS) caps the depth at and treats nodes at depth as if they had no successors. It always terminates, with time and space , but it is incomplete if . It must therefore distinguish two kinds of "no": failure (no solution exists at all) and cutoff (none within the limit, but the limit was hit).
function DEPTH-LIMITED-SEARCH(problem, node, ℓ):
if problem.is_goal(node.state): return node
if node.depth = ℓ: return CUTOFF
cutoff_occurred ← false
for each child in EXPAND(problem, node):
if child.state is already on the path to node: continue # cycle check
result ← DEPTH-LIMITED-SEARCH(problem, child, ℓ)
if result = CUTOFF: cutoff_occurred ← true
else if result ≠ FAILURE: return result
return CUTOFF if cutoff_occurred else FAILURERecursive depth-limited search. The recursion stack is the current path, so memory stays linear in .
Iterative deepening
Iterative deepening search (IDS) runs depth-limited search with until an iteration returns something other than cutoff. Each iteration is a DFS, so memory stays ; and because iteration explores every node down to depth , the first solution found is a shallowest one, as with BFS. Regenerating the top of the tree in every iteration looks wasteful. It is not:
function ITERATIVE-DEEPENING-SEARCH(problem):
for ℓ = 0, 1, 2, ...:
result ← DEPTH-LIMITED-SEARCH(problem, Node(problem.initial), ℓ)
if result ≠ CUTOFF: return result # a solution, or failureIteration generates each node at depth once, so a node at depth is generated in iterations , that is times:
Factor out and substitute . The series bounds the sum:
BFS generates , which tends to . The ratio therefore tends to : about 1.11 for and at most 2 for any .
For example, with and :
IDS searches a binary tree () whose shallowest goal is at depth (worst case). How many times as many nodes as BFS does it generate?
Show the answer
2
and : a ratio of about 1.99, close to the limit . Even in this worst case IDS at most doubles the work, while its memory drops from to .
For varying costs, iterative lengthening raises a cost limit instead of a depth limit, each time to the smallest path cost that exceeded the previous one. It inherits UCS's optimality, but when costs are real numbers that are all distinct, an iteration may add only one new node, and the overhead is no longer a constant factor. The same issue affects IDA*, as the Deep Layer shows.
The comparison, and where to go deeper
| Criterion | BFS | UCS | DFS | Depth-limited | IDS |
|---|---|---|---|---|---|
| Complete? | Yes | Yes | No | No | Yes |
| Cost-optimal? | Yes | Yes | No | No | Yes |
| Time | |||||
| Space |
Think first All four strategies have exponential worst cases. Why do route planners still answer queries on continental road networks in milliseconds?
A road network is an explicit graph with millions of states, not an exponential tree: graph search touches each state at most once, so Dijkstra's algorithm is polynomial in the size of the map. Production routers add heuristics, bidirectional search and preprocessed shortcuts on top. The exponential bounds bite when states are implicit: a sliding-tile puzzle or a planning problem has astronomically many states relative to the size of its description.
Key takeaways
- Every uninformed strategy is the same loop with a different frontier: FIFO (BFS), LIFO (DFS) or a priority queue on (UCS). Judge them by completeness, cost optimality, time and space, in terms of , , , and .
- BFS is complete and optimal for equal step costs, with time and space ; memory is its binding constraint.
- UCS is Dijkstra's algorithm on the search space: complete and optimal for step costs of at least , provided it tests for the goal at expansion. Its cost can far exceed when costs vary.
- DFS needs only memory but is incomplete on infinite paths and not optimal; depth-limited search trades completeness for guaranteed termination.
- Iterative deepening gets BFS's guarantees in memory and generates only about times as many nodes as BFS.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
BFS with the goal test at generation runs on a tree with , and the only goal is the last node generated at depth 4. How many nodes does it generate?
- 81
- 364
- 121
- 243
Show the answer
C. 121
It generates every node down to depth 4: . The last layer is two thirds of the total, as expected for .
The state space is infinite, is finite, and the shallowest solution is at depth . Which strategy is guaranteed to find a solution using only memory?
- Iterative deepening search
- Breadth-first search
- Depth-first search
- Depth-limited search with
Show the answer
A. Iterative deepening search
Iterative deepening reaches the shallowest goal in iteration , and each iteration is a depth-first search that stores one path plus siblings: nodes.
Uniform-cost search has just generated a goal node with , and the frontier still holds a node with . What should it do?
- Stop and return the goal, since a goal has been found
- Keep going: a path through the node might reach a goal for less than 7
- Switch to breadth-first search to find a shorter path
- Discard the goal node, because it was generated too early
Show the answer
B. Keep going: a path through the node might reach a goal for less than 7
A goal is certified only when it is popped: then its is minimal over the frontier, and with nonnegative step costs no path through a frontier node can be cheaper. Here the node might lead to the goal at total cost 4.
Why does iterative deepening waste so little time regenerating the shallow levels in every iteration?
- It caches the shallow levels between iterations
- A table of reached states lets it skip repeated nodes
- It repeats work only when is large
- Most nodes of a tree lie at its deepest level, so the repeats add only a factor of about
Show the answer
D. Most nodes of a tree lie at its deepest level, so the repeats add only a factor of about
A node at depth is generated times, but the shallow layers are tiny compared with layer . Summing gives : about 1.11 for , and at worst 2 for .
A problem has and solutions at depth 5, but some paths are 1,000 steps long. How do tree-like DFS and IDS compare?
- DFS is cost-optimal here, because all solutions are at depth 5
- DFS may take time on the order of in the worst case; IDS takes time with about 50 nodes in memory
- IDS needs memory on the order of
- Both take time on the order of
Show the answer
B. DFS may take time on the order of in the worst case; IDS takes time with about 50 nodes in memory
DFS's worst-case time is with : it may explore long useless branches before finding a depth-5 goal. IDS stops at iteration with time and space .
Go deeper
- Complexity of Search · Branching factors, depth and the price of completeness.
- Graph Search & Duplicate Detection · Why remembering visited states changes everything.
- Bidirectional & Memory-Bounded Search · Meeting in the middle, IDA* and limited memory.
Further reading
- S. Russell & P. Norvig, Artificial Intelligence: A Modern Approach, 4th ed. (Pearson, 2020), chapter 3.
- R. E. Korf, "Depth-first iterative-deepening: An optimal admissible tree search," Artificial Intelligence 27(1) (1985), 97–109.
- E. W. Dijkstra, "A note on two problems in connexion with graphs," Numerische Mathematik 1 (1959), 269–271.
- E. F. Moore, "The shortest path through a maze," Proceedings of an International Symposium on the Theory of Switching (Harvard University Press, 1959).