Iterative deepening depth-first search

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Iterative deepening depth-first search" – news · newspapers · books · scholar · JSTOR (January 2017) (Learn how and when to remove this message)

Iterative deepening depth-first search

Class	Search algorithm
Data structure	Tree, Graph
Worst-case performance	${\displaystyle O(b^{d})}$, where ${\displaystyle b}$ is the branching factor and ${\displaystyle d}$ is the depth of the shallowest solution
Worst-case space complexity	${\displaystyle O(d)}$[1]
Optimal	yes (for unweighted graphs)

In computer science, iterative deepening search or more specifically iterative deepening depth-first search^[1] (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, meaning that it finds the shallowest goal.^[2] Since it visits all the nodes in the search tree down to depth ${\displaystyle d}$ before visiting any nodes at depth ${\displaystyle d+1}$, the cumulative order in which nodes are first visited is effectively the same as in breadth-first search. However, IDDFS uses much less memory.^[1]