Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 46 ยท Uninformed Search

Uniform-Cost, Depth-Limited and Iterative Deepening

Learn uniform-cost search, depth-limited search, iterative deepening and bidirectional search in Python, then compare them with measured node counts.

Breadth-first search finds the solution with the fewest steps, and depth-first search uses very little memory. Each has a weakness the other does not. BFS counts every step as equal, so it can return a path that is short in steps but expensive in distance, and it must store a whole layer of the search tree. DFS is thrifty, but it can wander down an endless branch and it does not promise the shortest answer.

This lesson adds four more uninformed strategies, which means they know nothing about the problem except its rules. Uniform-cost search handles actions with different costs. Depth-limited search and iterative deepening keep DFS's small memory footprint while recovering BFS's optimality. Bidirectional search attacks the problem from both ends at once. At the end you will compare them all on the same puzzles, using real node counts.

Uniform-cost search (UCS) always expands the frontier node with the lowest path cost so far, written g(n). It is BFS with the plain queue swapped for a priority queue. If every step costs the same, UCS behaves exactly like BFS. If costs differ, UCS finds the cheapest path, and it is the same idea as Dijkstra's algorithm for shortest paths in a graph.

Two details matter and trip people up:

  1. Test for the goal when you pop a node, not when you generate it. A route to the goal may be generated early, but a cheaper route could still be waiting in the queue. Only when the goal is the cheapest item in the frontier is it certainly optimal.
  2. Keep the best known cost for each state. If you find a second, cheaper route to a state already in the frontier, record it. Older, more expensive entries stay in the heap and are skipped when popped ("stale entries").
graph LR
    A((A)) -- 4 --> B((B))
    A -- 1 --> C((C))
    C -- 2 --> B
    C -- 7 --> D((D))
    B -- 1 --> D
    B -- 5 --> E((E))
    D -- 3 --> F((F))
    E -- 1 --> F

A small road map. From A to F, the route with the fewest roads (A-B-D-F) is not the shortest in kilometres.

Python BFS versus uniform-cost search on a road map

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

BFS returns A-B-D-F with 8 km because it only counts roads. UCS pops A (cost 0), then C (1), then B (3, reached through C, not the direct 4 km road), then D (4), and finally F at 7 km. The expansion order is sorted by cost, which is the signature of UCS: it grows a "cost contour" outward from the start, like ripples on water.

UCS is complete and optimal as long as every step costs more than zero (some small positive amount). With zero-cost loops it can spin forever. Its time and memory both grow like b^(1 + C*/ฮต), where C* is the optimal cost and ฮต the smallest step cost. That can be much worse than BFS when many cheap steps exist.

Plain DFS has a famous flaw: on an infinite or very deep branch it never comes back. Depth-limited search (DLS) fixes this with a depth limit โ„“. Any node at depth โ„“ is treated as if it had no children. DLS has two different ways to fail, and a good implementation tells them apart:

  • Failure: the whole tree within the limit was searched and there is no solution there (or anywhere, if the tree is finite).
  • Cutoff: some branch was stopped by the limit, so a solution might exist deeper.

The distinction is what makes the next idea work.

Iterative deepening

Iterative deepening depth-first search (IDDFS, or IDS) runs DLS with limit 0, then 1, then 2, and so on, until it finds a solution. Each round is a cheap, memory-light DFS. The first round that succeeds has the shallowest solution, so IDDFS is complete and, with equal step costs, optimal like BFS. Its memory is only O(bยทd), like DFS.

It looks wasteful because shallow levels get re-explored every round. In practice that cost is small, because in a tree with branching factor b almost all the nodes are on the deepest level. For b = 10 and solution depth 5, BFS generates 111,111 nodes while IDDFS generates 123,456: roughly 11% extra, in exchange for a tiny memory footprint.

Python Depth-limited search and iterative deepening

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first rounds are cutoffs, each visiting about twice as many nodes as the one before. The search succeeds at limit 6, having visited 213 nodes in total, against 127 for BFS in the worst case. IDDFS paid about 1.7 times as many node visits as BFS, but it never needed to store a frontier. When the memory of BFS is the obstacle, as it is for large puzzles, that trade is excellent.

IDDFS is the default choice for uninformed search when the state space is huge, the solution depth is unknown, and every step costs the same.

If the goal state is known and actions can be reversed, you can search from the start and from the goal at the same time, and stop when the two frontiers touch. The reason this helps is exponential arithmetic: two searches of depth d/2 each generate about 2ยทb^(d/2) nodes, far fewer than the b^d of one search of depth d. For b = 10 and d = 6 that is roughly 2,000 nodes instead of 1,000,000.

graph LR
    S(("Start")) --> F1["Forward frontier<br/>grows from the start"]
    F1 --> M{{"Frontiers meet"}}
    G(("Goal")) --> F2["Backward frontier<br/>grows from the goal"]
    F2 --> M

Two small searches replace one huge one. The solution is the forward path joined to the reversed backward path.

Bidirectional search needs a goal that is a single explicit state (not "any checkmate position"), reversible actions or a way to compute predecessors, and a quick test for whether a node is already in the other frontier. It still stores a whole frontier, so memory is O(b^(d/2)).

Comparing them on the 8-puzzle

Now measure instead of guess. The program below builds three solvable 8-puzzles by scrambling the goal with a fixed random seed (so the puzzle is always solvable), then runs four algorithms and prints the solution length and the number of nodes each one expanded or visited. Every step costs 1, so uniform-cost search should match BFS exactly, which makes a handy sanity check.

Python Four uninformed searches, measured

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the table the way an engineer would. On the hard puzzle (20 moves), BFS and uniform-cost search expand 49,858 nodes, as predicted, and both need to hold a frontier of thousands of states. IDDFS expands 411,299 node visits, about eight times as many, but stores only the current path. Bidirectional search needs just 729, roughly 68 times fewer than BFS, which shows how strongly the b^(d/2) effect matters.

Algorithm Complete? Optimal? Time Memory Best for
BFS Yes Yes, equal step costs O(b^d) O(b^d) Small spaces, shallowest solution
Uniform-cost Yes, if costs > 0 Yes O(b^(1+C*/ฮต)) same Different step costs
Depth-limited No (limit may be too small) No O(b^โ„“) O(bยทโ„“) Known depth bound
Iterative deepening Yes Yes, equal step costs O(b^d) O(bยทd) Big spaces, unknown depth
Bidirectional Yes Yes, with BFS both ways O(b^(d/2)) O(b^(d/2)) Known goal, reversible actions

All of these treat the whole state space with equal suspicion. The next chapter changes that by giving the search a sense of direction. Before that, check what you have learned.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why should uniform-cost search test for the goal when a node is popped from the priority queue rather than when it is generated?

    A node that is generated first is not necessarily cheapest. Only the node at the front of the priority queue is guaranteed to have the lowest path cost found so far.
  2. 2. What is the difference between a cutoff and a failure in depth-limited search?

    Iterative deepening relies on this: it increases the limit only after a cutoff, because failure means there is nothing more to find.
  3. 3. Which algorithm combines the memory use of depth-first search with the optimality of breadth-first search (for equal step costs)?

    Iterative deepening runs depth-limited DFS with growing limits, storing only one path at a time, and returns the shallowest solution.
  4. 4. Roughly how many nodes does bidirectional search generate for branching factor b and solution depth d?

    Each of the two searches only needs to reach depth d/2, and an exponential in half the depth is vastly smaller than the full exponential.

Summary

  • Uniform-cost search expands the node with the lowest path cost g(n) using a priority queue; it is optimal for any positive step costs and is Dijkstra's algorithm applied to a search problem.
  • Test the goal when a node is popped, and skip stale queue entries.
  • Depth-limited search stops at a limit and reports either a cutoff or a real failure.
  • Iterative deepening repeats depth-limited search with growing limits: complete, optimal for equal costs, with O(bยทd) memory and only modest repeated work.
  • Bidirectional search meets in the middle and cuts time and memory to about b^(d/2), but needs an explicit goal and reversible actions.
  • Measured on the 8-puzzle, all uninformed methods still explore tens of thousands of states, which motivates heuristics.

Next, learn how a sense of direction changes everything in Heuristic Functions.