Editing Iterative deepening depth-first search (section)

{{Short description|Search strategy}}
{{more citations needed|date=January 2017}}
{{Infobox Algorithm
|class=[[Search algorithm]]
|image=
|caption =
|data=[[Tree (data structure)|Tree]], [[Graph (data structure)|Graph]]
|time=<math>O(b^d)</math>, where <math>b</math> is the branching factor and <math>d</math> is the depth of the shallowest solution
|space=<math>O(d)</math><ref name="re1985"/>
|optimal=yes (for unweighted graphs)
|complete=yes
}}

In [[computer science]], '''iterative deepening search''' or more specifically '''iterative deepening depth-first search'''<ref name="re1985">{{cite journal|last=Korf|first=Richard|author-link=Richard E. Korf|title=Depth-first Iterative-Deepening: An Optimal Admissible Tree Search|journal=Artificial Intelligence|year=1985|volume=27|pages=97–109|doi=10.1016/0004-3702(85)90084-0|s2cid=10956233 }}</ref> (IDS or IDDFS) is a [[state space search|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.<ref name=":0" /> Since it visits all the [[node (computer science)|node]]s in the [[search tree]] down to depth <math>d</math> before visiting any nodes at depth <math>d + 1</math>, the cumulative order in which nodes are first visited is effectively the same as in [[breadth-first search]]. However, IDDFS uses much less memory.<ref name="re1985"/>