Simple Algorithm
Artificial Intelligence · Hidden Layer · 22 min

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 bb, dd, mm and ℓ\ell.
  • Prove that uniform-cost search is optimal for positive step costs, explain why it must test for the goal at expansion, and derive its O(b1+⌊C∗/ε⌋)\order{b^{1+\lfloor C^*/\varepsilon\rfloor}} cost.
  • Show that iterative deepening generates only about b/(b−1)b/(b-1) times as many nodes as breadth-first search.

Problems, nodes and the generic search loop

A search problem consists of a state space SS, an initial state s0s_0, the actions Actions(s)\mathrm{Actions}(s) available in each state, a transition model Result(s,a)\mathrm{Result}(s,a), a goal test, and a step cost c(s,a,s′)c(s,a,s'). A solution is an action sequence leading from s0s_0 to a goal state, and an optimal solution has the lowest path cost C∗C^* 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 g(n)g(n) 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.

text
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 failure

Tree-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.

StrategyFrontierpop() returns
Breadth-first search (BFS)FIFO queuethe oldest node, hence a shallowest one
Depth-first search (DFS)LIFO stackthe newest node, hence a deepest one
Uniform-cost search (UCS)priority queue on gga node with the cheapest path so far
Three data structures, three strategies. A* (the next Hidden Layer lesson) is a priority queue on g+hg+h.

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 bb, the maximum branching factor; dd, the depth of the shallowest goal; mm, the maximum depth of any path (possibly ∞\infty); and, for costs, C∗C^* and the smallest step cost ε>0\varepsilon>0.

Breadth-first search

BFS expands every node at depth kk before any node at depth k+1k+1. 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.

DerivationCounting the cost of BFS
  1. NBFS(b,d)=∑k=0dbk=bd+1−1b−1=O(bd)N_{\mathrm{BFS}}(b,d)=\sum_{k=0}^{d}b^k=\frac{b^{d+1}-1}{b-1}=\order{b^d}

    Depth kk of a tree with branching factor bb holds bkb^k nodes. In the worst case, with the early goal test, BFS generates every node down to depth dd:

  2. goal test at expansion:O(bd+1)\text{goal test at expansion:}\quad\order{b^{d+1}}

    The deepest layer dominates: it holds a fraction of about (b−1)/b(b-1)/b of all generated nodes, 90% for b=10b=10. Testing at expansion instead would also generate the children of nearly every depth-dd node before the goal is popped:

  3. time=O(bd),space=O(bd)\text{time}=\order{b^d},\qquad\text{space}=\order{b^d}

    When the goal is found, the frontier holds essentially all of layer dd, and every generated node must be kept to reconstruct paths or detect repeats. Space equals time:

Predict before you look

BFS runs on a problem with b=10b=10 and the shallowest goal at depth d=8d=8, storing 1 KB per node. In the worst case, about how many gigabytes of memory does it need?

Show the answer

110 GB

N=(109−1)/9≈1.1×108N=(10^9-1)/9\approx1.1\times10^8 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 g(n)g(n). 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:

text
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 failure

Russell and Norvig's best-first search with priority gg. A stale copy of a state popped after a cheaper copy is harmless: its children are never better than what is already reached.

DerivationProof sketch
  1. g(n′)=g(n)+c(s,a,s′) ≥ g(n)g(n')=g(n)+c(s,a,s')\ \ge\ g(n)

    Order. Step costs are nonnegative, so a child is never cheaper than its parent. When a node with cost vv is popped, every frontier node costs at least vv, and so does every child added next; by induction, the popped costs never decrease.

  2. g(G′)≤g(n)≤C∗⟹g(G′)=C∗g(G')\le g(n)\le C^*\quad\Longrightarrow\quad g(G')=C^*

    Optimality. Take an optimal path PP of cost C∗C^*. Until its goal is expanded, some node nn of PP lies on the frontier (the first unexpanded one), with g(n)≤C∗g(n)\le C^*. A goal G′G' popped before it therefore satisfies

  3. nodes generated ≤ ∑k=01+⌊C∗/ε⌋bk=O(b1+⌊C∗/ε⌋)\text{nodes generated}\ \le\ \sum_{k=0}^{1+\lfloor C^*/\varepsilon\rfloor}b^k=\order{b^{1+\lfloor C^*/\varepsilon\rfloor}}

    Cost. Every expanded node has g≤C∗g\le C^*, and a node at depth kk has g≥kεg\ge k\varepsilon, so expanded nodes have depth at most ⌊C∗/ε⌋\lfloor C^*/\varepsilon\rfloor and generated ones at most one more:

  4. C∗=εd⟹O(bd+1)C^*=\varepsilon d\quad\Longrightarrow\quad\order{b^{d+1}}

    With equal step costs, C∗=εdC^*=\varepsilon d and the bound becomes bd+1b^{d+1}, slightly worse than BFS with its early test. When costs vary widely, C∗/εC^*/\varepsilon can far exceed dd: UCS explores many cheap, useless paths before it commits to one expensive step.

Check your understanding

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?

  1. Nothing: UCS is complete whenever a solution exists
  2. It returns a suboptimal path
  3. It can expand the zero-cost cycle forever, because those paths never become more expensive than the cheapest goal path
  4. 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 ε>0\varepsilon>0, so that gg grows with depth. With a zero-cost cycle, infinitely many nodes have gg below C∗C^*, 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 bmbm nodes; a backtracking version that generates one successor at a time needs only the path, O(m)\order{m}. That frugality is DFS's whole appeal.

The price is paid in guarantees. If some path is infinite (m=∞m=\infty), 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 O(bm)\order{b^m}, terrible when m≫dm\gg d.

Depth-limited search (DLS) caps the depth at ℓ\ell and treats nodes at depth ℓ\ell as if they had no successors. It always terminates, with time O(bℓ)\order{b^\ell} and space O(bℓ)\order{b\ell}, but it is incomplete if ℓ<d\ell<d. 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).

text
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 FAILURE

Recursive depth-limited search. The recursion stack is the current path, so memory stays linear in ℓ\ell.

Iterative deepening

Iterative deepening search (IDS) runs depth-limited search with ℓ=0,1,2,…\ell=0,1,2,\dots until an iteration returns something other than cutoff. Each iteration is a DFS, so memory stays O(bd)\order{bd}; and because iteration ℓ\ell explores every node down to depth ℓ\ell, 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:

text
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 failure
DerivationCounting the repeated work
  1. NIDS(b,d)=∑k=0d(d+1−k) bkN_{\mathrm{IDS}}(b,d)=\sum_{k=0}^{d}(d+1-k)\,b^k

    Iteration ℓ\ell generates each node at depth k≤ℓk\le\ell once, so a node at depth kk is generated in iterations k,k+1,…,dk,k+1,\dots,d, that is d+1−kd+1-k times:

  2. NIDS=bd∑j=0d(j+1) b−j < bd(bb−1)2N_{\mathrm{IDS}}=b^d\sum_{j=0}^{d}(j+1)\,b^{-j}\ <\ b^d\Big(\frac{b}{b-1}\Big)^2

    Factor out bdb^d and substitute j=d−kj=d-k. The series ∑j≥0(j+1)xj=1/(1−x)2\sum_{j\ge0}(j+1)x^j=1/(1-x)^2 bounds the sum:

  3. NIDSNBFS ⟶ bb−1(d→∞)\frac{N_{\mathrm{IDS}}}{N_{\mathrm{BFS}}}\ \longrightarrow\ \frac{b}{b-1}\qquad(d\to\infty)

    BFS generates NBFS=bd∑j=0db−jN_{\mathrm{BFS}}=b^d\sum_{j=0}^{d}b^{-j}, which tends to bd⋅b/(b−1)b^d\cdot b/(b-1). The ratio therefore tends to b/(b−1)b/(b-1): about 1.11 for b=10b=10 and at most 2 for any b≥2b\ge2.

  4. NIDS=6+50+400+3,000+20,000+100,000=123,456vs.NBFS=111,111N_{\mathrm{IDS}}=6+50+400+3{,}000+20{,}000+100{,}000=123{,}456\quad\text{vs.}\quad N_{\mathrm{BFS}}=111{,}111

    For example, with b=10b=10 and d=5d=5:

Predict before you look

IDS searches a binary tree (b=2b=2) whose shallowest goal is at depth d=10d=10 (worst case). How many times as many nodes as BFS does it generate?

Show the answer

2

NIDS=∑k=010(11−k)2k=4,083N_{\mathrm{IDS}}=\sum_{k=0}^{10}(11-k)2^k=4{,}083 and NBFS=211−1=2,047N_{\mathrm{BFS}}=2^{11}-1=2{,}047: a ratio of about 1.99, close to the limit b/(b−1)=2b/(b-1)=2. Even in this worst case IDS at most doubles the work, while its memory drops from O(2d)\order{2^d} to O(d)\order{d}.

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

CriterionBFSUCSDFSDepth-limitedIDS
Complete?Yes1^1Yes1,2^{1,2}NoNoYes1^1
Cost-optimal?Yes3^3YesNoNoYes3^3
TimeO(bd)\order{b^d}O(b1+⌊C∗/ε⌋)\order{b^{1+\lfloor C^*/\varepsilon\rfloor}}O(bm)\order{b^m}O(bℓ)\order{b^\ell}O(bd)\order{b^d}
SpaceO(bd)\order{b^d}O(b1+⌊C∗/ε⌋)\order{b^{1+\lfloor C^*/\varepsilon\rfloor}}O(bm)\order{bm}O(bℓ)\order{b\ell}O(bd)\order{bd}
1^1 if bb is finite and the state space either has a solution or is finite; 2^2 if every step costs at least ε>0\varepsilon>0; 3^3 if all step costs are equal. DFS becomes complete in finite state spaces when it checks for cycles. After Russell & Norvig, 4th ed., Figure 3.15.
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 gg (UCS). Judge them by completeness, cost optimality, time and space, in terms of bb, dd, mm, C∗C^* and ε\varepsilon.
  • BFS is complete and optimal for equal step costs, with time and space O(bd)\order{b^d}; memory is its binding constraint.
  • UCS is Dijkstra's algorithm on the search space: complete and optimal for step costs of at least ε>0\varepsilon>0, provided it tests for the goal at expansion. Its cost O(b1+⌊C∗/ε⌋)\order{b^{1+\lfloor C^*/\varepsilon\rfloor}} can far exceed bdb^d when costs vary.
  • DFS needs only O(bm)\order{bm} 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 O(bd)\order{bd} memory and generates only about b/(b−1)b/(b-1) 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.

Question 1

BFS with the goal test at generation runs on a tree with b=3b=3, and the only goal is the last node generated at depth 4. How many nodes does it generate?

  1. 81
  2. 364
  3. 121
  4. 243
Show the answer

C. 121

It generates every node down to depth 4: 1+3+9+27+81=121=(35−1)/21+3+9+27+81=121=(3^5-1)/2. The last layer is two thirds of the total, as expected for b=3b=3.

Question 2

The state space is infinite, bb is finite, and the shallowest solution is at depth dd. Which strategy is guaranteed to find a solution using only O(bd)\order{bd} memory?

  1. Iterative deepening search
  2. Breadth-first search
  3. Depth-first search
  4. Depth-limited search with ℓ=10\ell=10
Show the answer

A. Iterative deepening search

Iterative deepening reaches the shallowest goal in iteration dd, and each iteration is a depth-first search that stores one path plus siblings: O(bd)\order{bd} nodes.

Question 3

Uniform-cost search has just generated a goal node with g=7g=7, and the frontier still holds a node with g=3g=3. What should it do?

  1. Stop and return the goal, since a goal has been found
  2. Keep going: a path through the g=3g=3 node might reach a goal for less than 7
  3. Switch to breadth-first search to find a shorter path
  4. Discard the goal node, because it was generated too early
Show the answer

B. Keep going: a path through the g=3g=3 node might reach a goal for less than 7

A goal is certified only when it is popped: then its gg is minimal over the frontier, and with nonnegative step costs no path through a frontier node can be cheaper. Here the g=3g=3 node might lead to the goal at total cost 4.

Question 4

Why does iterative deepening waste so little time regenerating the shallow levels in every iteration?

  1. It caches the shallow levels between iterations
  2. A table of reached states lets it skip repeated nodes
  3. It repeats work only when bb is large
  4. Most nodes of a tree lie at its deepest level, so the repeats add only a factor of about b/(b−1)b/(b-1)
Show the answer

D. Most nodes of a tree lie at its deepest level, so the repeats add only a factor of about b/(b−1)b/(b-1)

A node at depth kk is generated d+1−kd+1-k times, but the shallow layers are tiny compared with layer dd. Summing gives NIDS/NBFS→b/(b−1)N_{\mathrm{IDS}}/N_{\mathrm{BFS}}\to b/(b-1): about 1.11 for b=10b=10, and at worst 2 for b=2b=2.

Question 5

A problem has b=10b=10 and solutions at depth 5, but some paths are 1,000 steps long. How do tree-like DFS and IDS compare?

  1. DFS is cost-optimal here, because all solutions are at depth 5
  2. DFS may take time on the order of 10100010^{1000} in the worst case; IDS takes O(105)\order{10^5} time with about 50 nodes in memory
  3. IDS needs memory on the order of 10100010^{1000}
  4. Both take time on the order of 10510^5
Show the answer

B. DFS may take time on the order of 10100010^{1000} in the worst case; IDS takes O(105)\order{10^5} time with about 50 nodes in memory

DFS's worst-case time is O(bm)\order{b^m} with m=1000m=1000: it may explore long useless branches before finding a depth-5 goal. IDS stops at iteration d=5d=5 with time O(bd)\order{b^d} and space O(bd)=O(50)\order{bd}=\order{50}.

Go deeper

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).