迭代加深

佚名 4年前 (2020-07-27) 算法 929人围观抢沙发百度已收录

迭代加深

1. 算法分析

迭代加深就是防止答案在比较浅的层时，dfs搜索到很深而找不到答案的情况，通过设置一个最大迭代深度来解决这个情况

2. 例题

acwing170加成序列
满足如下条件的序列X（序列中元素被标号为1、2、3…m）被称为“加成序列”：
1、X[1]=1
2、X[m]=n
3、X[1]<X[2]<…<X[m-1]<X[m]
4、对于每个 k（2≤k≤m）都存在两个整数 i 和 j （1≤i,j≤k−1，i 和 j 可相等），使得X[k]=X[i]+X[j]。
你的任务是：给定一个整数n，找出符合上述条件的长度m最小的“加成序列”。
如果有多个满足要求的答案，只需要找出任意一个可行解。
n~100

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

/*
本题的n为100，考虑极端情况：1，2，4，8，16，32，64，128，如此才8个就已经超过了100，所以可能在
dfs很浅的情况就能找到答案，使用迭代加深算法；
考虑剪枝情况：
1.优化搜索顺序：尽量从大的数字开始枚举，这样可以保证后面搜索的情况尽可能少
2.冗余性剪枝：比如一个序列1，2，3，4，现在第5个数字可以填上5，而5既可以由2+3得到，也可以由1+4得到
只需要做好记录，不需要重复这个工作
*/
#include<bits/stdc++.h>

using namespace std;

int n;
int path[101];

int dfs(int u, int max_depth)  // u:当前层数，max_depth:最大深度
{
    if (u > max_depth) return false;  // 当前层数大于最大层数，剪枝
    if (path[u - 1] == n) return true;  // 上一层就达到n，剪枝
    bool st[101] = {0};  // 记录每个数字是否被使用
    for (int i = u - 1; i >= 0; --i)
        for (int j = i; j >= 0; --j)
        {
            int s = path[i] + path[j];  // 本次可以使用的数字
            if (st[s] || s <= path[u - 1] || s > n) continue;  // 这个数字被使用过，这个数字大于n，这个数字小于等于先前的数字
            path[u] = s;
            st[s] = true;
            if (dfs(u + 1, max_depth)) return true;  
        }
    return false;  // 如果放入哪个数字都不行，那么这个方案不行
}

int main()
{
    while (scanf("%d", &n) && n)
    {
        path[0] = 1;
        int depth = 1;  // 设定的最大深度
        while (!dfs(1, depth)) depth++;  // 如果depth深度找不到，那么找depth+1深度
        for (int i = 0; i < depth; ++i) cout << path[i] << " ";
        cout << endl;
    }
    return 0;
}