UVa 529 - Addition Chains ,迭代加深搜索+减枝

题目链接：

UVA ：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=470

POJ ：http://poj.org/problem?id=2248

类型： 回溯， 迭代加深搜索， 减枝

原题：

An addition chain fornis an integer sequencewith the following four properties:

• a₀= 1
• a_m=n
• a₀<a₁<a₂<...<a_m-1<a_m
• For eachk() there exist two (not neccessarily different) integersiandj() witha_k=a_i+a_j

You are given an integern. Your job is to construct an addition chain fornwith minimal length. If there is more than one such sequence, any one is acceptable.

For example, <1,2,3,5> and <1,2,4,5> are both valid solutions when you are asked for an addition chain for 5.

样例输入：

5
7
12
15
77
0

样例输出：

1 2 4 5
1 2 4 6 7
1 2 4 8 12
1 2 4 5 10 15
1 2 4 8 9 17 34 68 77

题目大意：

给一个数字n， 然后输出一个元素个数最少的从1到n的序列（可能有多种方案，输出其中一种即可）。

其中对于第k个数Ak， 它的值等于Ai+Aj() 。

分析与总结：

这一题是典型的迭代加深搜索+减枝的题目。

迭代加深的搜索（IDS，Iterative Deepening Search）：

迭代加深搜索，实质上就是限定下界的深度优先搜索。即首先允许深度优先搜索K层搜索树，若没有发现可行解，再将K+1后重复以上步骤搜索，直到搜索到可行解。

在迭代加深搜索的算法中，连续的深度优先搜索被引入，每一个深度约束逐次加1，直到搜索到目标为止。

迭代加深搜索算法就是仿广度优先搜索的深度优先搜索。既能满足深度优先搜索的线性存储要求，又能保证发现一个最小深度的目标结点。

从实际应用来看，迭代加深搜索的效果比较好，并不比广度优先搜索慢很多，但是空间复杂度却与深度优先搜索相同，比广度优先搜索小很多。

对于这一题，首先可以求出最少需要几个元素可以达到n。按照贪心的策略，对于每个元素的值，都选择让它等于一个数的两倍，即对于每个Ai = Ai-1 + Ai-1, 当Ai>=n时就跳出循环，得到最少元素个数。

然后从最少步数开始迭代加深搜索。 然后再用上一些减枝技巧即可。

// 深度迭代搜索+减枝    Time:  UVa 0.012s    POJ: 0MS
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,ans[100];
bool flag;

void dfs(int cur, int depth){
    if(flag) return;
    if(cur==depth){ 
        if(ans[cur]==n) flag=true;
        return ;
    }
    for(int i=0; i<=cur; ++i){
        for(int j=i; j<=cur; ++j)if(ans[i]+ans[j] > ans[cur] && ans[i]+ans[j]<=n ){ // 这里也进行减枝           
            // 下面这个减枝至关重要！！如果从当前一直往下都是选择最大的策略还是不能达到n，跳过
            bool ok = false;
            int sum=ans[i]+ans[j];
            for(int k=cur+2; k<=depth; ++k)
                sum *= 2;
            if(sum < n) continue;
            
            ans[cur+1] = ans[i]+ans[j];
            dfs(cur+1, depth);
            if(flag)return;
        }
    }
}

int main(){
    while(scanf("%d", &n),n){
        memset(ans, 0, sizeof(ans));
        ans[0] = 1;
        flag = false;
        
        // 计算出至少需要多少步
        int m=1, depth=0;
        while(m<n){
            m *= 2;
            depth++;
        }
        // 从最少步开始进行迭代加深搜索
        while(true){
            dfs(0, depth);
            if(flag) break; 
            depth++;
        }
        
        printf("%d", ans[0]);
        for(int i=1; i<=depth; ++i)
            printf(" %d", ans[i]);
        printf("\n");
    }
    return 0;
}

—— 生命的意义，在于赋予它意义。

    

  原创http://blog.csdn.net/shuangde800，By  D_Double (转载请标明)