迭代加深搜索:

从小到大限制搜索的深度,如果当前限制下搜不到答案,再把深度限制增加,重新进行一次搜素(没错,会存在重复搜索)。
例题:

POJ 2248 Addition Chains

满足如下条件的序列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。
当输入为单行的0时,表示输入结束。
输出格式
对于每个测试用例,输出一个满足需求的整数序列,数字之间用空格隔开。
每个输出占一行。
数据范围
1≤n≤100
输入样例:
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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
#include <cstring>

const int maxn = 110;
using namespace std;
int n, x, a[maxn], sum[maxn];

int dfs(int now, int deep, int last) {//当前now深度,deep最大深度,last为上一次的数值,我们要满足数列的单调递增性.
if (a[now] == n) return 1;
if (now >= deep) return 0;
for (int i = now; i >= 1; i--)
for (int j = i; j >= 1; j--) {
if (!sum[a[i] + a[j]] && a[i] + a[j] >=last){
a[now+1] = a[i] +a[j];
sum[a[i]+a[j]] = 1;
int sm=dfs(now+1,deep,a[i]+a[j]);
if (sm) return sm;
sum[a[i]+a[j]] = 0;
a[now+1];
}else{
if (!sum[a[i]+a[j]]) break;
}
}
return 0;
}

int main() {
while (cin >> n && n) {
a[1] = 1;
a[2] = 2;
int s, k = n;
if (n > 2) {
if (n > 20) k = 6;//这个剪枝非常精髓
else k = 3;
for (; k <= 10; k++) {//k一定小于10因为1 2 4 8 16 32 64 128
memset(sum, 0, sizeof(sum));
memset(a, 0, sizeof(a));
a[1] = 1;
a[2] = 2;
s = dfs(2, k, 3);
if (s != 0) break;
}
}
for (int i = 1; i <= k; i++)
cout << a[i] << ' ';
cout << endl;
}
}

双向搜索

从初态和终态出发各搜索一半状态,产生两颗深度减半的搜索树,在中间教会,组合成为最终的答案。
双向搜索又名折半搜索。当搜索的复杂度在指数级的时候,我们可以通过将指数折半的方法降低搜索复杂度。
具体做法是从初态和终态出发各搜索一半状态,产生两颗深度减半的搜索树,两颗树交汇在一起形成最终答案,将O(nk)O(nk)降低到O(nk/2+nk/2+1)O(nk/2+nk/2+1)的复杂度。
其实对于这样的指数级复杂度,如果指数除以2后可以接受的话,可以考虑双向搜索。

CH2401 送礼物

传送门
达达帮翰翰给女生送礼物,翰翰一共准备了N个礼物,其中第i个礼物的重量是G[i]。
达达的力气很大,他一次可以搬动重量之和不超过W的任意多个物品。
达达希望一次搬掉尽量重的一些物品,请你告诉达达在他的力气范围内一次性能搬动的最大重量是多少。

输入格式
第一行两个整数,分别代表W和N。

以后N行,每行一个正整数表示G[i]。

输出格式
仅一个整数,表示达达在他的力气范围内一次性能搬动的最大重量。

数据范围
1≤N≤45,
1≤W,G[i]≤231−1
输入样例:
20 5
7
5
4
18
1
输出样例:
19


​ 因为w过大,没法使用背包,可是直接的搜索是 级别的,可是我们这题的N的范围到45,正常无法解决。所以考虑双向搜索。
把礼物分为两半,首从前一半礼物中选出若干个,可能达到的0~W之间的所有重量值,放在数组里排序去重。再进行第二次搜索.
​ 对于每一个第一部分达到的重量t,在第二部分数组中二分查找<=w-t的数值中的最大值。这个算法的时间复杂度是
分半也存在一些细节可以优化时间,不要耿直的 N/2,资料上说 1~N/2+2 分法经过随机数据验证是最快的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
const int N=(1<<24)+1;
long long ans,n,m,a[N],s[N],n_2;
long long find(int val)//二分查找
{
int l=1,r=n_2,check=m-val;//最大可以承受的值
while(l<r)
{
int mid=(l+r+1)>>1;
if (s[mid]<=check)
l=mid;
else
r=mid-1;
}
ans=max(ans,s[l]+val);//当前最大值与全局最大值开始比较
}
int cmp(long long a,long long b)
{
return a>b;
}
int dfs(int x,long long sum)
{
if (x==(n/2+2)+1)
{
s[++n_2]=sum;//新的权值出现,压入数组中
return true;//返回必不可少,否则RE
}
dfs(x+1,sum);//不放这个进去
if (sum+a[x]<=m)//可以放进去
dfs(x+1,sum+a[x]);
}
int dfs2(int x,int sum)
{
// cout<<x<<endl;
if (x==n+1)
{
find(sum);//求出当前可以填充的最大值
return true;
}
dfs2(x+1,sum);
if (sum+a[x]<=m)//如果可以放进去
dfs2(x+1,sum+a[x]);
}
int main()
{
ios::sync_with_stdio(false);
cin>>m>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
sort(a+1,a+1+n,cmp);//从大到小排序
dfs(1,0);
sort(s+1,s+n_2+1);
n_2=unique(s+1,s+n_2+1)-(s+1);//去掉重复后,多少个数
dfs2(n/2+3,0);
cout<<ans<<endl;
return 0;
}