迭代加深

Acwing 算法提高课 迭代加深(DFS)

迭代加深 :

取一个最深深度,保证在每次dfs时不超过这个最深深度,这个最深深度逐步增加知道搜到最终答案

为什么要使用迭代加深 :

当我们要搜索一个相对效浅,而搜索深度相对较深的答案时,可以使用迭代加深

与BFS的区别 :

具有dfs的性质, 包括但不限于空间复杂度小(O(n))、可以易于记录路径等等

多次搜前面几层不会浪费空间复杂度吗 :

dfs作为指数级时间复杂度每一层随指数递增, 当分支数最少为2时,前几层对时间影响占比更大,此时前u-1层时间复杂度之和等于第u层,可以忽略不计

本题的剪枝在两个方面:

1. 优化搜索顺序, 在枚举数时从大往小枚举
2. 排除等效冗余, 用一个bool数组来判断某一数字是否填过,排除重复情况

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e2 + 10;

int n, path[N], dep;

bool dfs(int u){
    if(u > dep) return path[u - 1] == n; //迭代加深
    bool st[N] = {0}; // 如此可清空
    for(int i = u - 1; i >= 1; i --)
        for(int j = i; j >= 1; j --){
            int s = path[i] + path[j];
            if(s > n || s <= path[u - 1] || st[s]) continue;
            st[s] = true;
            path[u] = s;
            if(dfs(u + 1)) return true;
        }
    return false;
}

int main(){
    freopen("increasingquence.in", "r", stdin);
    freopen("increasingquence.out", "w", stdout);
    while(cin >> n, n){
        path[1] = 1;
        dep = 1;
        while(!dfs(2)) dep ++;
        for(int i = 1; i <= dep; i ++)
            printf("%d ", path[i]);
        puts("");
    }
    return 0;
}