Iterative deepening depth-first search

In computer science, iterative deepening search or more specifically iterative deepening depth-first search (IDS or IDDFS) is a state space/graph search strategy in which a depth-limited version of depth-first search is run repeatedly with increasing depth limits until the goal is found. IDDFS is optimal like breadth-first search, but uses much less memory; at each iteration, it visits the nodes in the search tree in the same order as depth-first search, but the cumulative order in which nodes are first visited is effectively breadth-first. The following pseudocode shows IDDFS implemented in terms of a recursive depth-limited DFS (called DLS) for directed graphs. This implementation of IDDFS does not account for already-visited nodes. function IDDFS(root) is for depth from 0 to ∞ do found, remaining ← DLS(root, depth) if found ≠ null then return found else if not remaining then return null function DLS(node, depth) is if depth = 0 then if node is a goal then return (node, true) else return (null, true) (Not found, but may have children) else if depth > 0 then any_remaining ← false foreach child of node do found, remaining ← DLS(child, depth−1) if found ≠ null then return (found, true) if remaining then any_remaining ← true (At least one node found at depth, let IDDFS deepen) return (null, any_remaining) If the goal node is found, then DLS unwinds the recursion returning with no further iterations. Otherwise, if at least one node exists at that level of depth, the remaining flag will let IDDFS continue. 2-tuples are useful as return value to signal IDDFS to continue deepening or stop, in case tree depth and goal membership are unknown a priori. Another solution could use sentinel values instead to represent not found or remaining level results. IDDFS combines depth-first search's space-efficiency and breadth-first search's completeness (when the branching factor is finite). If a solution exists, it will find a solution path with the fewest arcs.