This article needs additional citations for verification. (January 2017) |
Class | Search algorithm |
---|---|
Data structure | Tree, Graph |
Worst-case performance | , where is the branching factor and is the depth of the shallowest solution |
Worst-case space complexity | [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 before visiting any nodes at depth , 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]