迭代加深

摘要: 迭代加深的思想与例题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

$1 迭代加深的思想和算法

DFS 回顾

DFS 的逻辑是每次选定一个分支，不断深入，直到达到递归边界才回溯。这种方法退域很多搜索问题非常有效，尤其是配合剪枝，记忆化等手段后很有威力。

但是 DFS 也有弱点：当每个节点的分支非常多，且问题的答案在比较浅的节点上的时候，DFS 一旦选错了分支，就可能在不包含答案的深层子树上浪费时间。

对于这种情况可以考虑迭代加深的做法。

迭代加深

迭代加深的思想：从小到大限制搜索的深度，如果在当前深度限制下搜不到答案，就将深度限制增加，重新搜索。重复以上流程逼近答案。

当深度限制为 d 时，1~d-1 层会重复搜索。但是当层数变大时，每层的节点数会指数增长，这点重复量可以忽略。

代码 (C++)

int depth = 1;
while(!dfs(start, 0, depth))
    ++depth;

bool dfs(state, depth, max_depth)
{
    if(depth > max_depth)
        return false;
    ...
}

迭代加深的适用性和优缺点

使用前提

首先使用迭代加深必须要保证问题有解，否则会无限循环下去。

适合使用的场景

搜索树规模随着深度增加增长很快，并且可以确保答案在较浅层的节点时，迭代加深非常适合。

此外在一般情况下，当存在大的搜索空间且解决方案的深度未知时，迭代加深是首选尝试的搜索方法。

好处

1. 时间复杂度只比 BFS 稍差一点（虽然搜索 k+1 层时会重复搜索 k 层，但是整体而言并不比 BFS 慢很多）。

2. 空间复杂度与深搜相同，比广搜小很多。

3. 利于剪枝

更多讨论参考《人工智能：一种现代的方法》。

---

$2 题目

• 111. 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明：叶子节点是指没有子节点的节点。

示例 1：
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

树中节点数的范围在 [0, 1e5] 内
-1000 <= Node.val <= 1000

算法：迭代加深

求最浅的叶节点的深度，本题可能出现树的深度很大但是答案在浅层节点。

用 BFS 也可以，但是要开队列需要 $O(2^{H})$ 空间。用迭代加深只需要 $O(H)$ 空间。

代码 (C++)

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        int depth = 1;
        while(!dfs(root, 1, depth))
            ++depth;
        return depth;
    }

private:
    bool dfs(TreeNode* node, int depth, const int max_depth)
    {
        if(!node -> left && !node -> right)
            return true;

        if(depth == max_depth)
            return false;

        if(node -> left)
            if(dfs(node -> left, depth + 1, max_depth))
                return true;
        if(node -> right)
            if(dfs(node -> right, depth + 1, max_depth))
                return true;
        return false;
    }
};

---