摘要:
1,迭代加深搜索的介绍
2,迭代加深搜索的解题步骤
3,迭代加深搜索优缺点
4,迭代加深搜索解埃及分数
1,迭代加深搜索的介绍
迭代深化深度优先搜索(iterative deepening depth-first search,简称 IDS 或 IDDFS)又称迭代加深搜索,是一种用于解决搜索问题的算法框架,它结合了深度优先搜索(DFS)和广度优先搜索(BFS)的特点,通过限制搜索深度来避免无限循环,同时逐步增加深度限制以找到解。
IDDFS通常用于那种搜索又深又宽、但是解并不是很深的情况,如果使用广度优先搜索会超空间,而深度优先搜索会爆栈。这时IDDFS很有用,可以说是在用递归方法实现广度优先搜索。
如下图所示,搜索从起始点到目标值,如果每个节点都有 n 个子节点,那么每一层节点的个数将呈指数级增长。如果树过深,使用 DFS 会超出内存限制。如果树过宽,使用 BFS 会存储大量的节点,因为 BFS 的实现基础是队列,队列需要的存储空间也非常大。
![](https://static.ws.126.net/163/frontend/images/2022/empty.png)
打开网易新闻 查看更多图片
这个时候我们就可以使用迭代加深搜索(IDDFS),IDDFS使用的还是 DFS ,只不过每次搜索会有深度限制,不会像 DFS 那样一直蒙着头往下走,导致爆栈。
像一些常见的埃及分数,八数码,跳房子等问题都可以使用IDDFS。关于八数码问题我们将会在之后的启发式搜索算法:IDA*算法中介绍,这里我们在最后会通过埃及分数的代码实现来深入理解IDDFS。
2,迭代加深搜索的解题步骤
IDDFS的解题步骤实际上就是 DFS 加个深度限制,每次搜索的时候不能超过这个最大深度,步骤如下:
1,设置一个最大深度 d 。
2,从起始点开始进行深度优先搜索,但搜索的深度不能超过 d 。