简介

迭代加深是一种 每次限制搜索深度的 深度优先搜索。

它的本质还是深度优先搜索，只不过在搜索的同时带上了一个深度 d ，当d 达到设定的深度时就返回，一般用于找最优解。如果一次搜索没有找到合法的解，就让设定的深度+1 ，重新从根开始。

既然是为了找最优解，为什么不用 BFS 呢？我们知道 BFS 的基础是一个队列，队列的空间复杂度很大，当状态比较多或者单个状态比较大时，使用队列的 BFS 就显出了劣势。事实上，迭代加深就类似于用 DFS 方式实现的 BFS，它的空间复杂度相对较小。

当搜索树的分支比较多时，每增加一层的搜索复杂度会出现指数级爆炸式增长，这时前面重复进行的部分所带来的复杂度几乎可以忽略，这也就是为什么迭代加深是可以近似看成 BFS 的。

步骤

首先设定一个较小的深度作为全局变量，进行 DFS。每进入一次 DFS，将当前深度 d + + ，当发现 d 大于设定的深度就返回。如果在搜索的途中发现了答案就可以回溯，同时在回溯的过程中可以记录路径。如果没有发现答案，就返回到函数入口，增加设定深度，继续搜索。

好处

1.时间复杂度只比BFS稍差一点（虽然搜索k+1层时会重复搜索k层，但是整体而言并不比广搜慢很多）。

2.空间复杂度与深搜相同，却比广搜小很多。

3.利于剪枝。

题目

n的加法链是整数序列<a0，a1，a2，...，am>，具有以下四个属性：
请在这里输入引用内容
a0 = 1
am = n
a0 <a1 <a2 <... <am-1 <am
对于每个k（1 <= k <= m），存在两个（不一定是不同的）整数i和j（0 <= i，j <= k-1），其中ak = ai + aj
你得到一个整数n。你的工作是为n构建一个最小长度的附加链。如果存在多个这样的序列，则任何一个都是可接受的。
请在这里输入引用内容
例如，当要求输入5的加法链时，<1,2,3,5>和<1,2,4,5>都是有效的解决方案。

输入

输入将包含一个或多个测试用例。每个测试用例由一行包含一个整数n（1 <= n <= 100）组成。对于n，输入以零（0）的值终止。

输出

对于每个测试用例，打印一行包含所需的整数序列。将数字分隔一个空格。

样本输入

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
通过贪心的策略得知: ∵a_{0} <a_{1} <a_{2} <... <a_{k-1}，a_{k}=a_{i}+a_{j}（0≤i,j<k）
所以让a每一项等于前一项的两倍，可以使数列增长最快。如果这样一个数列的第m项刚好大于等于n，那么可行解的长度一定大于等于m，否则不可能得到n。于是可以把下界从m开始加起，每次DFS搜一遍，最先搜出的一定最优。

此题的乐观估计函数也可以用这个数列来推断：从搜到的数出发，以增长最快的方式乘2一直推到下界位置，如果都小于n，那么此路继续搜下去一定无法在限界内得到n，就返回。

坑点：每次枚举前面的项时要倒着枚举。

include

include

include

include

using namespace std;
int n,k,l,a[105];
bool f;
void iddfs(int x){//迭代加深
if(x>l){//控制搜索深度
if(a[x-1]==n)f=1;
return;
}
for(int i=x-1;i>0;i--){
for(int j=i;j>0;j--){
if(a[i]+a[j]>a[x-1]&&a[i]+a[j]<=n&&!f){//枚举前面两个数相加
a[x]=a[i]+a[j];
int s=a[x];
s<<=(l-x);
if(s<n)continue;//乐观估计
iddfs(x+1);
}
}
}
}
int main()
{
scanf("%d",&n);
while(n){
int s=1;
l=1;f=0;a[1]=1;
while(s<n)s<<=1,l++;
for(;!f;l++)//扩宽下界
iddfs(2);/由于a1必为1，所以从a2搜起
for(int i=1;i<l;i++){
if(i-1)putchar(' ');
printf("%d",a[i]);
}
putchar('\n');
scanf("%d",&n);
}
return 0;
}