迭代加深

  |  

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

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


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

DFS 回顾

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

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

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

迭代加深

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

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

代码 (C++)

1
2
3
4
5
6
7
8
9
10
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 题目

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

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

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

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

提示:

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

算法:迭代加深

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

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

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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;
}
};

Share