一、迭代加深
适用场景：某些分支的层数特别深，但答案在比较浅的层数里
170. 加成序列
剪枝一：优先枚举较大的数
减少搜索层数
剪枝二：排除等效冗余
前面任意两个数的和可能相等，对于每个结点，开一个bool数组记录是否枚举过
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int x[N];
bool dfs(int u,int depth)
{
if(u > depth) return false; //当前层数大于最大深度也搜不到，返回false
if(x[u-1] == n) return true; //搜到答案了
bool st[N] = {0}; //排除等效冗余，记录两数之和是否被枚举过,局部变量，无需恢复现场
for(int i = u - 1;i>=0;i--) //从大到小枚举，减少搜索层数
{
for(int j = i;j>=0;j--) //从大到小枚举
{
int s = x[i] + x[j];
if(s <= x[u-1] || s > n || st[s]) //不大于上一层数 or 大于边界 or 已经搜索过 都是不合法的情况
{
continue;
}
//合法的数字
st[s] = 1;//标记一搜索
x[u] = s;//放置序列中
if(dfs(u+1,depth)) return true; //注意：dfs有返回值，“一呼百应”
}
}
return false;
}
int main()
{
x[0] = 1; //序列第一项必是1
while(cin>>n,n)
{
int depth = 1; //每次迭代加深搜索的最大深度
while(!dfs(1,depth)) ++depth; //每次搜不到就增大搜索深度，直到搜到为止
for(int i = 0;i<depth;i++)
{
cout<<x[i]<<' ';
}
puts("");
}
return 0;
}
二、双向BFS
171. 送礼物
- 将所有物品按重量从大到小排序
- 先将前K件物品能凑出的所有重量打表，然后排序并去重
- 搜索剩下的N-K件物品的选择方式，然后在表中二分查找出不超过W的最大值
#pragma GCC optimize(3)
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
typedef pair<int, int>PII;
const int N = 47;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n,k;
int cnt = 1;
LL m;
int w[N];
int sum[1<<25];//打表处理前一半物品可以组成的所有重量
LL ans;
void dfs1(int u,LL s) //打表处理前一半物品可以组成的所有重量
{
if(u == k)
{
sum[cnt++] = s;
return;
}
dfs1(u+1,s);
if((LL)s+w[u]<=m) dfs1(u+1,(LL)s+w[u]);
return;
}
void dfs2(int u,LL s) //对后一半物品的选择方式进行搜索
{
if(u>=n)
{
int l = 0,r = cnt-1; //表中二分查找出不超过W的最大值(不可用map)
LL x = (LL)m - s;
while(l<r)
{
int mid = l+r+1>>1;
if(x >= sum[mid]) l = mid;
else r = mid - 1;
}
ans = max(ans,(LL)sum[l] + s);
return;
}
dfs2(u+1,s);
if((LL)s+w[u]<=m) dfs2(u+1,(LL)s + w[u]);
return;
}
int main()
{
scanf("%lld%d",&m,&n);
k = n/2 + 2;
LL s = 0;
for(int i = 0;i<n;i++)
{
scanf("%d",&w[i]);
s += w[i];
}
if(s<= m) //所有重量不大于能力
{
cout<<s<<endl;
exit(0);
}
sort(w,w+n);
reverse(w,w+n);//从大到小枚举，减少搜索层数
dfs1(0,0ll);
sort(sum,sum+cnt);//对所有重量表进行排序去重，方便后面二分查找
cnt = unique(sum,sum+cnt) - sum;
dfs2(k,0ll);
cout<<ans<<endl;
return 0;
}
三、IDA(迭代加深 + A估价剪枝)
基本思想：在迭代加深的同时额外添加一个剪枝，即对未来步数的启发式估计
相比A*算法更加简单实用
180. 排书
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 16;
int T,n;
int a[N];
int w[5][N];
int f() //估价函数
{
int tot = 0;
for(int i = 0;i<n-1;i++)
{
if(a[i+1]!=a[i] + 1) ++tot;
}
return (tot+2)/3;
}
bool dfs(int u,int depth)
{
if(u + f() > depth) return false;//当前层+估计层大于最大层，返回失败
if(f() == 0) return true;//若没有不正确的相邻(偏序)关系,说明全部排列正确，返回成功
for(int len = 1;len<=n;len++) //枚举区间长度
{
for(int l = 0;l + len - 1 < n;l++) //枚举区间左端点
{
int r = l + len - 1;
for(int k = r + 1;k < n;k++) //枚举将区间插入其后的位置
{
memcpy(w[u],a,sizeof a);//备份
//先把原数组[r+1,k]的所有数挪到l位置，再把[l,r]挪到[r+1,k]数组之后，完成插入
int j = l;
for(int i = r + 1;i<=k;i++,j++)
{
a[j] = w[u][i];
}
for(int i = l;i<=r;i++,j++)
{
a[j] = w[u][i];
}
if(dfs(u+1,depth)) return true; //以当前状态，搜索下一层，成功返回1
memcpy(a,w[u],sizeof a);//不成功，恢复现场
}
}
}
return false; //注意：必须写
}
int main()
{
scanf("%d", &T);
while(T--)
{
cin>>n;
for(int i = 0;i<n;i++)
{
cin>>a[i];
}
//迭代加深部分
int depth = 0;
while(depth < 5 && !dfs(0,depth)) ++depth;
if(depth >= 5) puts("5 or more");
else cout<<depth<<endl;
}
return 0;
}