迭代加深 SDOI2007 数列

问题链接

我花了好长时间来理解这一个题目表述:对于任意a[k],存在1<=i<=j<=n使得a[k]=a[i]+a[j]。这道题要用深度优先搜索,先用一个数组a[n]储存数组顺序中的每一个元素。为了避免重复,设数组为递增数组。在每一层递归中,通过已经“假设”的数列,枚举加法的两个变量,得到a[i+1],进行下一层递归。

观察发现,假如说要使一个长度为n的数组的a[n]最大,那么必须是以2^n的形式增长的。因为由a[i]推到a[i+1]的时候,a[i]之前的元素都比a[i]小,要使a[i+1]最大,只能a[i+1]=a[i]+a[i]=2*a[i]。

另外一个问题,这个递归时间复杂度会很大。只有当a[i]>=a[n]时才会停止递归。那么中间有多少情况会被浪费?

引入的一个新的算法就叫迭代加深。限制一个深度来搜索,看有没有解,没有解就增加深度,没有时间就停止,给一个目前的最优解。迭代加深有一个非常大的好处:可以为剪枝提供很方便的条件!

看代码:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[20],depth,dest;
bool dfs(int stage){//递归
    if(a[stage]==dest){//发现了!
        return true;//返回说找到了
    }
    if(stage==depth){//到达目标深度,不能再往下,而且不符合条件
        return false;
    }
    for(int i=1;i<=stage;i++){
        for(int j=i;j<=stage;j++){//枚举数列下标小于等于stage的元素的和
            a[stage+1]=a[i]+a[j];
            if(a[stage+1]>a[stage]&&a[stage+1]<=dest&&(a[stage+1]<<(depth-stage-1))>=dest){
                /*
                这里包含了三个剪枝。
                第一个是保证数列为递增的;
                第二个是保证数列还在an范围之内,
                因为如果超范围了后面新增的讨论也一定是会超范围的;
                第三个是看在增长最快的情况下,在当前迭代层数限制下,
                是否可能达到最高值。
                */
                if(dfs(stage+1)){//搜索
                    return true;
                }
            }
        }
    }
    return false;
}
int main(){
    cin>>dest;
    a[1]=1;
    depth=0;
    while((1<<depth)<dest){//初始化迭代条件,至少需要log2dest层才能达到目标的a[n]
        depth++;
    }
    depth++;
    while(!dfs(1)){
        depth++;//加深。这一级不够,就继续往下加深一级。
    }
    cout<<depth;
}

感觉这个代码还可以继续优化。因为在每一层递归的时候前面小于等于stage的和全部都枚举过了,是否还需要在stage+1上枚举这些和呢?应该是不需要的了。在新的一层递归中新增的和只与a[stage+1]有关系,所以在枚举这个和的时候只需要使用第一层for,第二层直接用a[stage+1]就好了。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[20],depth,dest;
bool dfs(int stage){
    if(a[stage]==dest){
        return true;
    }
    if(stage==depth){
        return false;
    }
    for(int i=1;i<=stage;i++){
        a[stage+1]=a[i]+a[stage];
        if(a[stage+1]<=dest&&(a[stage+1]<<(depth-stage-1))>=dest){
            if(dfs(stage+1)){
                return true;
            }
        }
    }
    return false;
}
int main(){
    cin>>dest;
    a[1]=1;
    depth=0;
    while((1<<depth)<dest){
        depth++;
    }
    depth++;
    while(!dfs(1)){
        depth++;
    }
    cout<<depth;
}

我把这个代码重新提交了一遍,也是AC的。说明刚才的推断是正确的!

avatar
Kerry Su