Uninformed Search Algorithms

Breadth-first search (BFS) expands the shallowest unexpanded node first, implemented with a FIFO queue as the frontier: newly generated nodes are added to the back of the queue and nodes are removed from the front, guaranteeing every node at depth k is expanded before any node at depth k+1. This ordering makes BFS complete (it will find a solution if one exists, given a finite branching factor) and optimal whenever all step costs are equal, since the first goal node reached is necessarily at the shallowest — hence cheapest — depth. Its cost is steep: both time and space grow as O(b^d), where b is the branching factor and d is the depth of the shallowest goal, and because the entire frontier at depth d must be held in memory before any depth-d node is expanded, BFS's memory demand is typically the more limiting factor in practice.

Trace BFS on a small tree with root R, children A and B, and grandchildren C, D (under A) and E, F (under B), searching for goal F. The frontier starts as [R]; expanding R yields frontier [A, B]; expanding A (shallowest, added first) yields [B, C, D]; expanding B yields [C, D, E, F]; the goal test now finds F in the frontier's next few expansions before deeper nodes are ever touched — the visiting order is exactly level by level: R, then A and B, then C, D, E, F. This level-by-level guarantee is precisely what makes BFS optimal when costs are uniform: no node from a deeper level is ever expanded before all shallower nodes have been. If the goal test were instead applied only when a node is popped for expansion rather than as soon as it is generated, BFS would still find F eventually, but it would waste time expanding some shallower non-goal nodes it could otherwise have skipped — a subtle implementation detail that affects efficiency without affecting correctness.

Depth-first search (DFS), by contrast, expands the deepest unexpanded node first, using a LIFO stack (or equivalent recursion) as the frontier. On the same tree, DFS would visit R, then plunge down A's branch entirely — A, C, D — before backtracking to explore B, E, F. DFS's chief advantage is memory: it needs to store only the single path from root to current node plus the unexpanded siblings along that path, giving space complexity O(bm) where m is the maximum depth of the tree, a linear rather than exponential quantity. Its costs are correspondingly steep in a different way — DFS is neither complete (it can descend forever down an infinite or very deep branch, missing a shallow goal entirely) nor optimal (it can return the first solution it stumbles onto, however deep and costly, before ever trying a cheaper shallow one). This BFS/DFS contrast — exponential time and memory with strong guarantees versus linear memory with weak guarantees — is the exact tension that uniform-cost and iterative-deepening search, covered next, are each designed to resolve in different ways.

Uniform-cost search (UCS) generalizes BFS to problems where step costs differ: instead of a FIFO queue, UCS uses a priority queue ordered by cumulative path cost g(n), always expanding the frontier node with the lowest total cost so far. This guarantees optimality even when costs are unequal, because a node is only finalized once no cheaper path to it can possibly remain in the frontier. Trace UCS on a graph where Home connects to Market with cost 4 and to River with cost 2, Market connects to Park with cost 5, and River connects to Park with cost 6: starting from Home, the frontier holds Market (cost 4) and River (cost 2); River, being cheaper, expands first, adding Park at cumulative cost 2+6=8; Market then expands, adding Park at cumulative cost 4+5=9 — but since a lower-cost path to Park (cost 8, via River) was already found and Park is only finalized when it is popped as the minimum-cost frontier node, UCS correctly returns the path Home→River→Park with cost 8 rather than the path via Market, even though Market was reachable at a lower single-step cost than River initially suggested.

Depth-limited search addresses DFS's incompleteness on infinite or very deep spaces by imposing a cutoff depth ℓ, refusing to expand any node beyond that depth. This guarantees termination but introduces a new failure mode: if the shallowest goal lies deeper than ℓ, depth-limited search will never find it, and choosing ℓ requires knowledge of the problem — too shallow a limit misses solutions, too deep a limit forfeits the memory savings and can still miss completeness in unbounded spaces. Depth-limited search retains DFS's O(bℓ) space advantage since it still only stores the current path plus unexpanded siblings, but it sacrifices the one property DFS never had a chance at anyway (completeness on infinite spaces) in exchange for a guarantee DFS also lacked: the search is now guaranteed to terminate, one way or the other, in finite time. This makes depth-limited search a genuine improvement over plain DFS whenever some upper bound on solution depth is known or can be reasonably estimated in advance.

Iterative-deepening search (IDS) sidesteps the need to guess ℓ correctly by running depth-limited search repeatedly with increasing limits — first ℓ=0, then ℓ=1, then ℓ=2, and so on — until a goal is found. This looks wasteful, since shallow levels are re-generated on every iteration, but the redundant work is asymptotically small: because the number of nodes at the deepest level of a tree with branching factor b dominates the total node count, the cost of IDS is within a constant factor of a single BFS pass, while its space complexity stays at DFS's O(bd) rather than BFS's O(b^d). This combination — BFS-like completeness and optimality (under uniform costs) with DFS-like memory efficiency — is exactly why IDS is frequently the preferred uninformed strategy for large state spaces where the solution depth is unknown in advance. It is, in a sense, the "default" uninformed search algorithm recommended for large search spaces precisely because it never requires the programmer to guess a depth bound the way plain depth-limited search does, while still avoiding BFS's often-prohibitive memory demands.