191031-搜索剪枝专题
几种剪枝方法
1、可行性剪枝
所谓可行性剪枝，顾名思义，就是当当前状态和题意不符，并且由于题目可以推出，往后的所有情况和题意都不符，那么就可以进行剪枝，直接把这种情况及后续的所有情况判负，直接返回。
即：不可行，就返回。
2、排除等效冗余
所谓排除等效冗余，就是当几个枝桠具有完全相同的效果的时候，只选择其中一个走就可以了。
即：都可以，选一个。
3、最优性剪枝
所谓最优性剪枝，是在我们用搜索方法解决最优化问题的时候的一种常用剪枝。就是当你搜到一半的时候，已经比已经搜到的最优解要不优了，那么这个方案肯定是不行的，即刻停止搜索，进行回溯。
即：有比较，选最优。
4、顺序剪枝
普遍来讲，搜索的顺序是不固定的，对一个问题来讲，算法可以进入搜索树的任意的一个子节点。但假如我们要搜索一个最小值，而非要从最大值存在的那个节点开搜，就可能存在搜索到最后才出解。而我们从最小的节点开搜很可能马上就出解。这就是顺序剪枝的一个应用。一般来讲，有单调性存在的搜索问题可以和贪心思想结合，进行顺序剪枝。
即：有顺序，按题意。
5、记忆化
记忆化搜索其实是搜索的另外一个分支。在这里简单介绍一下记忆化的原理：
就是记录搜索的每一个状态，当重复搜索到相同的状态的时候直接返回。
即：搜重了，直接跳。
T1 小猫爬山
题目描述
Freda和rainbow只好花钱让它们坐索道下山。索道上的缆车最大承重量为W，而N只小猫的重量分别是C1、C2……CN。当然，每辆缆车上的小猫的重量之和不能超过W。每租用一辆缆车，Freda和rainbow就要付1美元，所以他们想知道，最少需要付多少美元才能把这N只小猫都运送下山？
解析
搜索剪枝 1，最优化剪枝，如果当前的缆车数量已经超过ans，那么直接return 2，顺序剪枝，按小猫重量大小降序排序，以此来快速去掉无效分支
题解
#include<bits/stdc++.h>
using namespace std
;
bool comp(const int &a
,const int &b
)
{
return a
>b
;
}
int n
,w
,a
[10001],ans
,used
[10001];
void dfs(int cur
,int num
)
{
if(num
>=ans
)
return;
if(cur
==n
+1)
{
ans
=min(ans
,num
);
return;
}
for(int i
=1;i
<=num
;i
++)
if(used
[i
]+a
[cur
]<=w
)
{
used
[i
]+=a
[cur
];
dfs(cur
+1,num
);
used
[i
]-=a
[cur
];
}
int cnt
=num
+1;
used
[cnt
]+=a
[cur
];
dfs(cur
+1,cnt
);
used
[cnt
]-=a
[cur
];
}
int main()
{
scanf("%d%d",&n
,&w
);
for(int i
=1;i
<=n
;i
++)
scanf("%d",&a
[i
]);
sort(a
+1,a
+1+n
,comp
);
ans
=1e8;
dfs(1,1);
printf("%d",ans
);
return 0;
}
T2 Sudoku Poj2676
解析
搜索（细节比较多，需要注意）
题解
#include <cmath>
#include <cstdio>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std
;
const int fx
[10]={0,0,0,0,1,1,1,2,2,2};
const int fy
[10]={0,1,1,1,2,2,2,3,3,3};
int f
[11][11],bel
[11][11],T
;
bool row
[11][11],col
[11][11],squ
[11][11],bj
;
char ch
[11][11],s
;
void clear()
{
memset(row
,0,sizeof(row
));
memset(col
,0,sizeof(col
));
memset(bel
,0,sizeof(bel
));
memset(squ
,0,sizeof(squ
));
memset(f
,0,sizeof(f
));
bj
=0;
}
void out()
{
for(int i
=1;i
<=9;i
++)
{
for(int j
=1;j
<=9;j
++)
printf("%d",f
[i
][j
]);
printf("\n");
}
}
void dfs(int x
,int y
)
{
if(bj
) return;
if(f
[x
][y
])
{
if(x
==9&&y
==9)
{
out();
bj
=1;
return;
}
else if(y
==9) dfs(x
+1,1);
else dfs(x
,y
+1);
}
else
{
for(int i
=1;i
<=9;i
++)
if(!squ
[bel
[x
][y
]][i
]&&!row
[y
][i
]&&!col
[x
][i
])
{
f
[x
][y
]=i
;
squ
[bel
[x
][y
]][i
]=row
[y
][i
]=col
[x
][i
]=true;
if(x
==9&&y
==9)
{
out();
bj
=1;
return;
}
else if(y
==9) dfs(x
+1,1);
else dfs(x
,y
+1);
squ
[bel
[x
][y
]][i
]=row
[y
][i
]=col
[x
][i
]=false;
f
[x
][y
]=0;
}
}
}
int main()
{
scanf("%d",&T
);
while(T
--)
{
clear();
for(int i
=1;i
<=9;i
++)
{
scanf("%c",&s
);
for(int j
=1;j
<=9;j
++)
{
scanf("%c",&ch
[i
][j
]);
f
[i
][j
]=ch
[i
][j
]-'0';
bel
[i
][j
]=3*fx
[i
]+fy
[j
];
row
[j
][f
[i
][j
]]=1;
col
[i
][f
[i
][j
]]=1;
squ
[bel
[i
][j
]][f
[i
][j
]]=1;
}
}
dfs(1,1);
}
return 0;
}
题外话
该题还可以继续优化，比如可以先搜索限制比较多的点，这样可以快速去掉无用分支 如16*16数独例题，传送门 （poj3076）
T3 彩票
解析
搜索剪枝 1,可行性剪枝1，如果当前得到的和加上剩余可选的最大的和小于
x
y
\frac{x}{y}
yx,直接return 2,可行性剪枝2，如果当前得到的和加上剩余可选的最小的和大于
x
y
\frac{x}{y}
yx,直接return
题解
#include<bits/stdc++.h>
using namespace std
;
int x
,y
,n
,m
,maxn
;
double ans
,sum
[100];
void dfs(int cur
,int num
,double dx
)
{
if(num
==n
)
{
if(fabs(dx
-ans
)<0.000000001)
maxn
++;
return;
}
if(dx
+sum
[n
-num
+cur
-1]-sum
[cur
-1]<ans
-0.000000001)
return;
if(dx
+sum
[m
]-sum
[m
-n
+num
]>ans
)
return;
if(cur
>m
)
return;
dfs(cur
+1,num
+1,dx
+(1.0/cur
));
dfs(cur
+1,num
,dx
);
}
int main()
{
scanf("%d%d%d%d",&n
,&m
,&x
,&y
);
for(int i
=1;i
<=m
;i
++)
sum
[i
]=sum
[i
-1]+(1.0/i
);
ans
=1.0*x
/y
;
dfs(1,0,0);
printf("%d",maxn
);
return 0;
}
