Iterative Deepening Search

Definition

Iterative deepening is a depth-first search that limits the search depth on each iteration.

Explanation

The essence of iterative deepening search is still depth-first search, except that it carries a depth $d$ during the search and returns when $d$ reaches the set depth; it is generally used to find an optimal solution. If one search does not find a valid solution, increase the set depth by one and start again from the root.

Since the goal is to find an optimal solution, why not use BFS? We know that BFS is based on a queue, and the space complexity of a queue is large. When there are many states or a single state is large, BFS using a queue reveals its disadvantages. In fact, iterative deepening is similar to implementing BFS using DFS, and its space complexity is relatively small.

When the search tree has many branches, the search complexity increases exponentially with each additional level. At that point, the complexity brought by the parts repeated earlier can almost be ignored, which is why iterative deepening can be regarded as approximately equivalent to BFS.

Process

First, set a small depth as a global variable and perform DFS. Each time DFS is entered, increase the current depth by one; when $d$ is found to be greater than the set depth $\textit{limit}$, return. If an answer is found during the search, backtrack; the path can also be recorded during backtracking. If no answer is found, return to the function entry, increase the set depth, and continue searching.

IDDFS(u,d)
    if d>limit
        return
    else
        for each edge (u,v)
            IDDFS(v,d+1)
return

Notes

In most problems, breadth-first search is still more convenient and makes duplicate detection easier. When breadth-first search is not sufficiently space-efficient and the problem requires finding an optimal solution, iterative deepening should be considered.