Iterative deepening depth-first search

submited by

Style Pass

2024-11-17 10:30:05

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 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.[ 1]

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.