IDS

迭代深化搜索(Iterative Deepening Search, IDS)是一种改进的盲目搜索算法,它结合了深度优先搜索(DFS)和广度优先搜索(BFS)的优点。

IDS的基本思想是逐步加深搜索深度,避免了DFS可能会遇到无限深搜索的风险,同时又不会像BFS那样存储太多节点而耗尽内存。

算法步骤如下:

1. 首先设定初始搜索深度为0。
2. 使用DFS进行搜索,但限制最大深度不超过当前设定值。如果没找到目标,回到根节点。
3. 将搜索深度加1,重复步骤2。
4. 重复步骤3,直到找到目标节点或达到约定的最大深度限制。

IDS的特点是:

1. 内存占用比BFS少
2. 时间复杂度比DFS低，重复寻找次数比DFS少
3. 最优性: 当边权重都相同时,IDS和BFS一样都能找到最优解。当边权重不同时,IDS需要修改为迭代加深 A*搜索才能保证最优性。

IDS被广泛应用于一些经典的人工智能领域,例如:

• 八数码问题、十五数码问题和其他状态空间搜索问题
• 密码破译
• 机器人路径规划
• 逻辑推理与自动定理证明等

复杂度

时间复杂度：$O(bd)$,（其中 $b$ 是分支因子，$d$ 是最浅目标状态的深度） 空间复杂度：$O(b^d)$

时间复杂度

假设问题的最优解在深度为d的节点处,branching factor为b。那么IDS的搜索过程为:

1. 深度限制为1的DFS,搜索节点数为$b^1$
2. 深度限制为2的DFS,搜索节点数为$b^1+b^2$
3. 深度限制为3的DFS,搜索节点数为$b^1+b^2+b^3$
4. …
5. 深度限制为d的DFS,搜索节点数为$b^1+b^2+...+b^d$

因此IDS的总搜索节点数为:

${\sum }_{i=1}^d{b}^i=b+b^2+...+b^d=b\cdot \frac{b^d-1}{b-1}$

当b和d较大时,IDS的搜索节点数接近$b^{d+1}$。

BFS的搜索节点数

IDS的搜索节点数约为BFS的b倍。

BFS每一层的节点数就是$b^i$,因此搜索到深度d的BFS总搜索节点数为:

${\sum }_{i=0}^d{b}^i=1+b+b^2+...+b^d=\frac{b^{d+1}-1}{b-1}$

空间复杂度