Iterative Deepening Depth-first Search - Algorithm

Algorithm

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

IDDFS(root, goal) { depth = 0 repeat { result = DLS(root, goal, depth) if (result is a solution) return result depth = depth + 1 } }

Depth-limited search can be implemented recursively as follows. Note that it need only check for goal nodes when depth == 0, because when depth > 0, DLS is expanding nodes that it has seen in a previous iteration of IDDFS.

DLS(node, goal, depth) { if (depth == 0 and node == goal) return node else if (depth > 0) for each child in expand(node) DLS(child, goal, depth-1) else return no-solution }