迭代加深搜索IDDFS

· · 个人记录

1.问题引入

搜索是我们日常代码中常用的一个算法，众所周知搜索分为深搜（DFS）和广搜（BFS），两种方法的适用性很广也各有优缺点，是做题 （骗分） 是不可多得的一个好方法，下面来做一个简单分析：

1.1 DFS：

优势：一条路走下去，可以适用于多个方面
劣势：有时时间太慢，不够优秀

1.2 BFS：

优势：一层一层扩展，先找到的解一定是最优解
劣势：用到队列扩展时可能会爆空间

所以，两种算法都有自己的缺点，那我们可不可以把它均衡一下呢？IDDFS就因此而生

2.算法分析：

2.1：算法思路

1.在我们确定了搜索树后，我们规定一个深度

2.我们从根节点开始，一次搜索一层，如果搜索深度等于层数仍未找到答案，深度加1.否则此层为最小答案。

3.循环之前步骤

2.2优劣势：

2.2.1优势：

1. 不会因为搜索太深而像dfs一样超时。

2. 没有队列储存扩展的状态，而像bfs一样超空间。

2.2.2劣势：

1.重复，容易超时

2.3.适合问题

1.从题目中直接或间接的知道答案的深浅

2.搜索树要随着深度增加，结点数快速增加

3.典型例题：

3.1加成序列

3.1.1 题目分析：

1.搜索解此题似乎都可以看得出来。

2.用迭代加深的原因：从样例我们可以看到当N=77时也只有9层，又N小于100，所以我们不难发现层数并不深。而节点数是快速增加的,具体看代码。

3.1.2：代码


#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int X=0; bool flag=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
    while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
    if(flag) return X;
    return ~(X-1);
    }
inline void write(int X)
{
    if(X<0) {X=~(X-1); putchar('-');}
    if(X>9) write(X/10);
    putchar(X%10+'0');
}
const int maxn=100+10;
int now[maxn],dep,n,s;//now表示记录答案的数组，dep深度。
bool dfs(int cur){//cur当前层数
    if(cur==dep)return now[cur]==n;//如果到了当前层数，且最后一个为所求即可返回
    bool vis[maxn]={false};
    for(int i=cur;i>=1;i--){
        for(int j=i;j>=1;j--){
            int nxt=now[i]+now[j];//下一个数必须有前面的数得到
            if(nxt<=n&&nxt>now[cur]){//下一个数的范围
                now[cur+1]=nxt;//记录下一个数
                if(dfs(cur+1)==true)return true;//搜索
                else vis[nxt]=1;
            }
        }
    }
    return false;
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    while(1){//多组数据
        n=read();
        if(n==0)break;
        dep=1;//最少一个数，也就是一层
        now[1]=1;//第一个数肯定是一
        while(dfs(1)==0)dep++;//如果没找到答案层数加一
        for(int i=1;i<=dep;i++)cout<<now[i]<<" ";//输出
        cout<<endl;
    }

    return 0;//完结散花
}

3.1.2问题总结：如果按照这个方法写肯定过不去，会出现超时的情况，所以我们该怎么办呢？

3.1.3 剪枝：

剪枝便是大家都会想到的方法，那我们来回顾一下剪枝的类型

3.1.3.1 最优性剪枝：如果当前值已大于现求出的最小答案，就不用再继续搜索了，而IDDFS先搜到的一定是最优答案，所以用不了最优性剪枝

3.1.3.2 去重剪枝：如果出现了重复，可以不用把这个点丢进搜索树，所以这个剪枝是可以用的，我们可以用一个vis数组来记录当前数字有没出现过，可以有效节省时间

3.1.3.3 可行性剪枝：如果根本就不可行就不需要继续搜下去了，我们不难发现当前最大值最多以每次翻二倍逼近答案，所以如果当前最大值乘上2的剩余层数的次方仍然无法逼近的话，就可以剪去。

结尾：剪枝可以留给各位读者自行思考，如有困难或对我内容的更正可以私信我