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, meaning that it finds the shallowest goal. Since it visits all the nodes in the search tree down to depth d {\displaystyle d} before visiting any nodes at depth d + 1 {\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.
Algorithm for directed graphs 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 by DLS, IDDFS will return it without looking deeper. 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.
Properties IDDFS achieves breadth-first search's completeness (when the branching factor is finite) using depth-first search's space-efficiency. If a solution exists, it will find a solution path with the fewest arcs. Iterative deepening visits states multiple times, and it may seem wasteful. However, if IDDFS explores a search tree to depth d {\displaystyle d} , most of the total effort is in exploring the states at depth d {\displaystyle d} . Relative to the number of states at depth d {\displaystyle d} , the cost of repeatedly visiting the states above this depth is always small. The main advantage of IDDFS in game tree searching is that the earlier searches tend to improve the commonly used heuristics, such as the killer heuristic and alpha–beta pruning, so that a more accurate estimate of the score of various nodes at the final depth search can occur, and the search completes more quickly since it is done in a better order. For example, alpha–beta pruning is most efficient if it searches the best moves first. A second advantage is the responsiveness of the algorithm. Because early iterations use small values for d {\displaystyle d} , they execute extremely quickly. This allows the algorithm to supply early indications of the result almost immediately, followed by refinements as d {\displaystyle d} increases. When used in an interactive setting, such as in a chess-playing program, this facility allows the program to play at any time with the current best move found in the search it has completed so far. This can be phrased as each depth of the search corecursively producing a better approximation of the solution, though the work done at each step is recursive. This is not possible with a traditional depth-first search, which does not produce intermediate results.
Asymptotic analysis
Time complexity The time complexity of IDDFS in a (well-balanced) tree works out to be the same as breadth-first search, i.e. O ( b d ) {\displaystyle O(b^{d})} , where b {\displaystyle b} is the branching factor and d {\displaystyle d} is the depth of the goal.
Proof In an iterative deepening search, the nodes at depth d {\displaystyle d} are expanded once, those at depth d − 1 {\displaystyle d-1} are expanded twice, and so on up to the root of the search tree, which is expanded d + 1 {\displaystyle d+1} times. So the total number of expansions in an iterative deepening search is
b d + 2 b d − 1 + 3 b d − 2 + ⋯ + ( d − 1 ) b 2 + d b + ( d + 1 ) = ∑ i = 0 d ( d + 1 − i ) b i {\displaystyle b^{d}+2b^{d-1}+3b^{d-2}+\cdots +(d-1)b^{2}+db+(d+1)=\sum _{i=0}^{d}(d+1-i)b^{i}}
… excerpt ends here. Continue reading the full article.
