Iterative Deepening Search

Definition

Iterative deepening is a depth-limited depth-first search.

Explanation

The essence of iterative deepening search is still depth-first search, but with an added depth limit \(d\). When \(d\) reaches the set limit, the search returns. It is generally used to find optimal solutions. If a valid solution is not found in one search, the depth limit is increased by one, and the search restarts 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, which has a large space complexity. When there are many states or each state is large, BFS using a queue shows its disadvantage. In fact, iterative deepening is similar to BFS implemented in a DFS manner, with relatively smaller space complexity.

When the search tree has many branches, the search complexity increases exponentially with each additional layer. In such cases, the complexity contributed by the repeated earlier parts becomes almost negligible, which is why iterative deepening can be approximately viewed as BFS.

Process

First, set a small depth as a global variable and perform DFS. Each time DFS is entered, increment the current depth by one. When it is found that \(d\) exceeds the set depth limit \(\textit{limit}\), return. If an answer is found during the search, backtrack and record the path during backtracking. If no answer is found, return to the function entry, increase the depth limit, and continue the search.

Implementation (Pseudocode)

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 relatively convenient and easy to handle duplicates. When breadth-first search is not space-efficient enough and the goal is to find an optimal solution, iterative deepening should be considered.

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用