IDS Finds the Shallowest Solution
Claim
Iterative deepening search (IDS) returns a goal node at the minimum depth among all goal nodes reachable from the start. For unit-cost graphs, minimum depth equals minimum cost, so IDS is optimal (Russell and Norvig 2020).
Proof
Let \(d^*\) be the minimum depth of any goal node reachable from the start node \(s\). IDS runs DLS(0), DLS(1), DLS(2), \(\ldots\) in increasing order.
Claim 1: DLS(\(\ell\)) returns failure for all \(\ell < d^*\).
A depth-limited search with limit \(\ell\) only examines nodes at depth \(\leq \ell\). Since every goal node has depth \(\geq d^*\) and \(\ell < d^*\), no goal node lies within the search horizon. DLS(\(\ell\)) therefore returns failure.
Claim 2: DLS(\(d^*\)) finds a goal node.
By assumption a goal node \(g\) exists at depth \(d^*\). There is an acyclic path \(s = v_0, v_1, \ldots, v_{d^*} = g\) of length \(d^*\). DLS(\(d^*\)) performs a depth-first traversal that explores all nodes at depth \(\leq d^*\), so it reaches \(g\) and returns it.
Main result.
By Claim 1, IDS fails on iterations \(\ell = 0, 1, \ldots, d^* - 1\). By Claim 2, iteration \(\ell = d^*\) succeeds and returns a goal at depth \(d^*\). Since \(d^*\) is the minimum depth of any goal node, the solution returned is shallowest. \(\square\)
Corollary (optimality for unit-cost graphs). If every edge has cost 1, depth equals path cost. The minimum-depth solution is also a minimum-cost solution, so IDS is cost-optimal.
Contrast with BFS
The BFS optimality proof (proof) works by showing that the queue processes nodes in non-decreasing depth order, so no goal at depth \(< d^*\) is skipped. The IDS proof works differently: rather than a queue ordering argument, it uses the fact that failure at depth \(\ell\) is a certificate that no solution exists at depth \(\leq \ell\). This certificate is what allows IDS to achieve BFS-quality optimality while using only \(O(bd)\) memory instead of \(O(b^d)\).