深度优先搜索的优化与技巧

深度优先搜索的优化与技巧"/>

深度优先搜索的优化与技巧

迭代加深

DFS在一些问题模型中可能无限扩展，如8数码问题，无限扩展会有些问题，增
加深度限制：假设目标状态所处深度不超过某阈值。人为设定，当搜索深度到达阈
值时直接剪枝，不再往下搜索。
Iterative Deepening Depth - First Search
适用：求最优/深度最低/步数最少解，当问题深度和广度都大的时候
方式：不断放宽迭代深度限制第一次找到的目标状态即为最优解。
迭代加深是深搜和广搜的结合,普通深搜求最优解必须遍历所有状态打擂台得到，
迭代加深后，第一次遇见目标状态即可得到最优解。
深度优先搜索优化-迭代加深（IDDFS）

for(int dep=1;;dep++)
{//限定每次搜索的深度if(dfs(1,dep)) break;//找到答案就退出
}

例题1443：【例题4】Addition Chains
n范围较小，初略推出最多十项左右就能得到答案，即答案在搜索树的浅层，可
以使用迭代加深的方法，限制每一次的搜索深度。
例题代码

#include<iostream>
#include<cstring>
using namespace std;
int n,a[105],vis[10005];
bool flag = false;int dfs(int x,int depth)
{if(x>depth)return 0;if(flag==true)return 1;bool vis[5500] = {0};for (int i = x