In computer science, iterative deepening search or more specifically iterative deepening depth-first search[2] (IDS or IDDFS) is a state space/graph search strategy in which a depth-limited version of Depth-first search 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.
Algorithm
Implementation
Complexity
Time
Worst-case: \(\bigo{b^d}\) where \(b\) is the branching factor (e.g. 2 for Binary trees) and \(d\) is the depth of the shallowest solution.
Bibliography
“Iterative Deepening Depth-First Search.” 2021. Wikipedia, January. https://en.wikipedia.org/w/index.php?title=Iterative_deepening_depth-first_search&oldid=1001650193.