Search Strategies Compared

The companion lesson, Uninformed Search, built the state-space formulation, the Tree-Search / Graph-Search skeleton, and the two strategies that grow the frontier outward: breadth-first search (a FIFO queue) and uniform-cost search (a priority queue). Both are complete and — under the right cost conditions — optimal, but both hold $O(b^d)$ nodes in memory, and that memory cost is the limit uninformed search keeps hitting. This lesson develops the strategies that trade that memory away by diving deep, then lines all six up side by side. Recall the through-line: the algorithm is fixed, and the frontier's queue discipline is the one knob.

Depth-first search

Depth-first search (DFS) goes the other way from breadth-first: always expand the deepest node on the frontier. It is Graph-Search with a LIFO queue — a stack — so the most recently generated node comes out next, which is necessarily one deeper than its parent. The search plunges to the bottom of the tree, and as those leaves are exhausted it backs up to the shallowest node that still has unexpanded children. DFS is commonly written as a recursion that calls itself on each child in turn.

DFS's virtues and vices both come from that stack. Its properties hinge on tree- versus graph-search. The graph-search version, which drops repeated states, is complete in finite state spaces. The tree-search version is not complete: on the Romania map it can chase the Arad-Sibiu-Arad loop forever, and in infinite state spaces both versions can run down an endless non-goal path. DFS is not optimal either — it returns the first goal it stumbles into, which may lie deep in a subtree while a shallower goal waits elsewhere. Time is $O(b^m)$ with $m$ the maximum depth, and $m$ can far exceed $d$.

The reason to keep DFS is memory. A depth-first tree search needs to store only a single root-to-leaf path plus the unexpanded siblings along it — $O(bm)$ nodes — and once a node's whole subtree is explored it can be dropped from memory. At $b=10$, $d=16$, that is kilobytes where BFS wanted exabytes. The backtracking variant generates one successor at a time and modifies the current state in place, cutting storage to $O(m)$. Modest memory is why DFS underlies constraint satisfaction, satisfiability, and logic programming.

Depth-limited and iterative-deepening search

DFS's failure on infinite paths is fixed by a depth limit $\ell$: treat nodes at depth $\ell$ as if they had no successors. Depth-limited search is DFS that never descends past $\ell$; it always terminates. But the limit adds its own trap. If $\ell <d$ the search is incomplete — the goal sits beyond the cutoff — and if $\ell >d$ it is nonoptimal. Time is $O(b^{\ell })$, space $O(b\ell )$. It returns failure or a distinct cutoff value, so the caller can tell no solution apart from no solution within $\ell$. Depth-first search is the special case $\ell =\infty$.

Picking $\ell$ needs knowledge of the problem. On the Romania map there are $20$ cities, so any solution has length at most $19$; studied more closely, the diameter of the map is only $9$, a tighter and better limit. But for most problems $d$ is unknown in advance, and a bad guess costs completeness or optimality.

Iterative-deepening search (IDS) removes the guessing. Run depth-limited search with limit $0$, then $1$, then $2$, and so on, until a goal is found; the search that finds it does so at limit $\ell =d$. IDS combines the strengths of both worlds: the $O(bd)$ memory of depth-first search and, when $b$ is finite, the completeness of breadth-first search (and optimality when cost is nondecreasing in depth).

Regenerating the shallow levels on every pass seems wasteful, but it is cheap. In a tree with branching factor $b$, most nodes live in the bottom level, and those are generated only once; the level above twice, and so on up to the root generated $d$ times. The total is

asymptotically the same as breadth-first search. At $b=10$, $d=5$, IDS generates $123,450$ nodes against BFS's $111,110$ — about $11\%$ more, for a factor-$b$-and-then-some cut in memory. Iterative deepening is the preferred uninformed method when the state space is large and the solution depth is unknown.

Bidirectional search

Every strategy so far grows one search outward from the start. Bidirectional search runs two at once: one forward from $s_0$ and one backward from the goal, stopping when the two frontiers meet. The motivation is arithmetic. A single breadth-first search to depth $d$ generates $O(b^d)$ nodes; two searches that meet in the middle each reach only depth $d/2$, for $b^{d/2}+b^{d/2}$ nodes total — and $2b^{d/2}$ is vastly smaller than $b^d$. At $b=10$, $d=6$, a forward BFS generates about $1,111,110$ nodes, while two searches meeting at depth $3$ generate roughly $2,220$: a five-hundred-fold cut.¹

Bidirectional search replaces the goal test with a frontier-intersection check: a solution is found the moment a node generated in one direction already sits on the other frontier, which a hash table decides in constant time. Time and space are both $O(b^{d/2})$; using iterative deepening in one direction can trim the space by half, but at least one frontier must stay in memory for the intersection check, and that memory demand is the method's main weakness.

Two subtleties keep it from being free. First, searching backward needs a way to compute predecessors — the states that have a given state as a successor. When every action is reversible (as on the Romania map) predecessors are just successors, but in general this takes work. Second, the goal must be a concrete state to run backward from; a single goal state (Bucharest) or a short explicit list is fine, but an abstract goal like no queen attacks another gives the backward search no foothold. When those conditions hold, though, the $b^{d/2}$ saving is the largest any uninformed method offers.

The strategies side by side

Every strategy across these two lessons is the same skeleton under a different frontier discipline, and the four criteria line them up cleanly. The table is for the tree-search versions; $b$ is the branching factor, $d$ the solution depth, $m$ the maximum depth, $\ell$ the depth limit, $C^{\ast }$ the optimal cost, and $\epsilon$ a lower bound on step cost.

${}^a$ complete if $b$ is finite. ${}^b$ complete if every step cost exceeds some $\epsilon >0$. ${}^c$ optimal if step costs are all identical. ${}^d$ if both directions use breadth-first search and predecessors are computable. For the graph-search versions the differences are that depth-first search becomes complete in finite state spaces, and its time and space are bounded by the size of the state space.

Two readings of the table. Down the rows: no uninformed strategy escapes the exponential — the best any of them does on time is $O(b^d)$, and the whole point of informed search is to beat that by feeding the frontier a heuristic estimate of distance-to-goal, so it expands promising nodes first. Across the columns: iterative-deepening is usually the default uninformed choice, pairing breadth-first's completeness and optimality with depth-first's linear memory. The lesson to carry forward is the one that recurs through the whole subject — the algorithm is fixed, and the frontier's ordering is the knob.

Where these algorithms come from and where they went

The skeleton in these lessons is old and still moving. Uniform-cost search is Dijkstra's single-source shortest-path algorithm (Dijkstra, 1959, Numerische Mathematik) cast as a search over an implicit graph; the open and closed lists in that literature are the frontier and explored set here. The shortest-paths treatment develops the same priority-queue expansion with an explicit adjacency structure and a decrease-key operation — the same replace a frontier node at higher cost step performed by uniform-cost search.

Iterative deepening as a general technique came to the fore through Korf (1985, Artificial Intelligence 27), who used depth-first iterative deepening to make optimal heuristic search run in linear space; the same idea had been used earlier inside the C/HESS 4.5 game-playing program (Slate and Atkin, 1977) to fit a search to the constraints of a chess clock. The lesson on informed search is where iterative deepening earns its keep, in the memory-bounded IDA* algorithm.

Bidirectional search was introduced by Pohl (1971). Its promise — an $O(b^{d/2})$ frontier instead of $O(b^d)$ — went underused for decades because guaranteeing that the first meeting of the frontiers is optimal is delicate. Holte, Felner, Sharon, and Sturtevant (2017, Artificial Intelligence 252) settled the modern form with MM, a bidirectional search that provably meets in the middle: every node it expands has $g$ no more than half the optimal cost, which finally made bidirectional heuristic search competitive with unidirectional A*. On the industrial side, Goldberg, Kaplan, and Werneck's work on landmark-based routing (2006) combined bidirectional search with precomputed landmark distances to answer shortest-path queries on a $24$-million-node road graph of the United States while touching under $0.1\%$ of it — the lineage behind the routing in online map services.

Two more strands sit just past the chapter. On grid maps, where the branching factor is uniform and paths are highly symmetric, jump point search (Harabor and Grastien, 2011, AAAI) prunes the enormous number of symmetric paths a plain search would explore by jumping over interior grid nodes to the next point where the optimal path could turn, cutting node expansions by an order of magnitude with no loss of optimality; it is standard in game pathfinding. And for graphs far too large to fit in RAM, external-memory and parallel search (Korf, 2008; Korf and Schultze, 2005) push the same frontier-and-explored-set machinery onto disk and across cores — the frontier's memory cost, diagnosed in these lessons, is precisely the problem those systems exist to manage.