Iterative deepening depth-first search

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 maximum depth
Worst-case space complexity	${\displaystyle O(d)}$

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 equivalent to breadth-first search, but uses much less memory; on 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.

The following pseudocode shows IDDFS implemented in terms of a recursive depth-limited DFS (called DLS).

IDDFS combines depth-first search's space-efficiency and breadth-first search's completeness (when the branching factor is finite). It is optimal when the path cost is a non-decreasing function of the depth of the node.

Since iterative deepening visits states multiple times, it may seem wasteful, but it turns out to be not so costly, since in a tree most of the nodes are in the bottom level, so it does not matter much if the upper levels are visited multiple times.

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 ${\displaystyle d}$, they execute extremely quickly. This allows the algorithm to supply early indications of the result almost immediately, followed by refinements as ${\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.

...
Wikipedia