《算法竞赛进阶指南》0x24迭代加深

本文主要是介绍《算法竞赛进阶指南》0x24迭代加深，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

迭代加深

深度优先搜索每次选定发一个分支，不断深入，直到达到递归边界才回溯。但是如果每个节点的分支非常多，并且问题的答案在某一个较浅的节点，如果一开始就选错了分支，就可能在不包含答案的子树上浪费时间。
此时，我们可以从小到大限制搜索的深度，如果在当前深度下搜不到答案，就把深度限制增加，重新进行一遍搜索。这就是迭代加深的思想。
总而言之，当搜索树地规模随着层次的深入增长很快，并且我们能保证答案在较浅层地节点时，就可以使用迭代加深地深度优先搜索算法来解决问题。

例题

acwing170.加成序列

搜索框架：依次搜索序列的每个位置k，枚举i，j作为分支，把X[i]和X[j]的和填到X[k]，然后递归填写下一个位置。
加入以下剪枝
1.优化搜索顺序
为了让序列中的数金肯逼近n，在枚举i，j时从大到小枚举。
2.排除等效冗余
对于不同的i,j，X[i]+X[j]可能是相等的，我们可以对他进行排重，避免重复搜索某一个和。
经过分析，m的值不会太大，不超过10，枚举两个数的和分支会很多，因此可以使用迭代加深。

#include<iostream>
using namespace std;
int arr[110];
int n;
bool dfs(int now,int dep)
{if(now==dep)return arr[now]==n;bool st[110]={0};for(int i=now;i>=1;i--)for(int j=i;j>=1;j--){int s=arr[i]+arr[j];if(s>n||st[s]||s<=arr[now])continue;st[s]=true;arr[now+1]=s;if(dfs(now+1,dep))return true;}return false;
}
int main()
{arr[1]=1;while(cin>>n,n){int dep=1;while(!dfs(1,dep))dep++;for(int i=1;i<=dep;i++)cout<<arr[i]<<" ";cout<<endl;}return 0;
}

双向搜索

在一些题目中，问题不但具有初态，还具有明确的终态，并且从初态与终态进行搜索都能覆盖整个状态空间。在这种情况下可以使用双向搜索——从初态和终态各出发搜索一半状态，产生两棵深度减半的搜索树，在中间交会，组合成最终的答案。

例题

acwing171.送礼物
首先这道题目肯定是要搜索的,因为如果说用DP做的话,那么这个W值太大了,但是如果说只是普通搜索的话,那么O(2^N)的复杂度足以超时,而且这道题目重点就是,我们已经知道了初态而且还知道了终态,既然如此的话,我们可以选择双向搜索.
根据双向搜索的性质,我们大致可以确定当前搜索的范围,首先从前一半个物品中,挑选任意多个物品,然后将这些物品的权值总和加入到数组S中,然后我们就会发现在这个S数组中有很多很多的重复的数值,我们可使用unique进行删除.然后我们现在前半部分搜索完后,开始搜索后半部分,至于后半部分搜索,其实和前半部分一模一样,只是我们需要二分找到当前可以填写的最大值.
时间复杂度 $O(2^{N/2}log2^{N/2})=O(N*2^{N/2})$

#include<iostream>
#include<algorithm>
using namespace std;
#define M 1<<25
#define N 50
int w,n,k,cnt=1;
int g[N],sum[M];
int ans=0;
void dfs1(int now,int weight)
{if(now>k){sum[cnt++]=weight;return ;}dfs1(now+1,weight);if((long long)weight+g[now]<=w)dfs1(now+1,weight+g[now]);return ;
}
void dfs2(int now,int weight)
{if(now>n){int l=0,r=cnt;while(l<r){int mid=(l+r+1)>>1;if(sum[mid]<=w-weight)l=mid;else r=mid-1;}ans=max(ans,sum[l]+weight);return ;}dfs2(now+1,weight);if((long long)weight+g[now]<=w)dfs2(now+1,weight+g[now]);return ;
}
int main()
{cin>>w>>n;k=n/2+2;for(int i=1;i<=n;i++)cin>>g[i];sort(g+1,g+1+n);reverse(g+1,g+1+n);dfs1(1,0);sort(sum+1,sum+cnt+1);cnt=unique(sum+1,sum+cnt+1)-sum-1;dfs2(k+1,0);cout<<ans;return 0;
}