上海
摘要：
1，迭代加深搜索的介绍
2，迭代加深搜索的解题步骤
3，迭代加深搜索优缺点
4，迭代加深搜索解埃及分数
1，迭代加深搜索的介绍
迭代深化深度优先搜索(iterative deepening depth-first search，简称 IDS 或 IDDFS)又称迭代加深搜索，是一种用于解决搜索问题的算法框架，它结合了深度优先搜索(DFS)和广度优先搜索(BFS)的特点，通过限制搜索深度来避免无限循环，同时逐步增加深度限制以找到解。
IDDFS通常用于那种搜索又深又宽、但是解并不是很深的情况，如果使用广度优先搜索会超空间，而深度优先搜索会爆栈。这时IDDFS很有用，可以说是在用递归方法实现广度优先搜索。
如下图所示，搜索从起始点到目标值，如果每个节点都有 n 个子节点，那么每一层节点的个数将呈指数级增长。如果树过深，使用 DFS 会超出内存限制。如果树过宽，使用 BFS 会存储大量的节点，因为 BFS 的实现基础是队列，队列需要的存储空间也非常大。
这个时候我们就可以使用迭代加深搜索(IDDFS)，IDDFS使用的还是 DFS ，只不过每次搜索会有深度限制，不会像 DFS 那样一直蒙着头往下走，导致爆栈。
像一些常见的埃及分数，八数码，跳房子等问题都可以使用IDDFS。关于八数码问题我们将会在之后的启发式搜索算法：IDA*算法中介绍，这里我们在最后会通过埃及分数的代码实现来深入理解IDDFS。
2，迭代加深搜索的解题步骤
IDDFS的解题步骤实际上就是 DFS 加个深度限制，每次搜索的时候不能超过这个最大深度，步骤如下：
1，设置一个最大深度 d 。
2，从起始点开始进行深度优先搜索，但搜索的深度不能超过 d 。
特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.
