基础剪枝
记忆化搜索
记忆化某些状态，不需要每一次都计算一下。
优化搜索顺序
可以配合 最优性剪枝 或者 卡时。
可行性剪枝
在搜索过程中当前解已经不可用了。
最优性剪枝
看看是否有更好的答案，如果有，当前的就不用继续了。
排除等效冗余（重复性剪枝）
一个方案可能会被搜很多次，直接判断然后去除掉。
进阶剪枝
Alpha–Beta 剪枝
图片直接扒 OIWIKI 的了。
不保证本人理解正确无误。
Minimax
首先引入是一个叫 Minimax 算法的东西。
现在在一个树的顶端，先手需要让答案更大，而后手需要让答案更小，每一次一个人可以选择一颗子树向下移动。
这一个问题可以直接在树上每一个节点找出这个节点的答案，然后根节点就是最后的答案。
图中方框节店会选择最大的子节点移动，而圆形节点会选择最小的节点向后移动，于是就建出了树。
Alpha–Beta 剪枝
刚刚的方法很好，但是当数据范围很大的时候，这个树可能就建不出来了，所以有一个剪枝：Alpha–Beta 剪枝。
看一下大概的思路：
我们每一次走到一个节点，会向下遍历，然后此时，我们就需要记录一些信息。
我们记录下 和 ，表示最小能够获得的和最大能够获得的答案。
比如这张图中，下面的 A 节点，遍历过 之后发现 很小，所以答案不可能大于 了，将 设置成 。
那这样有什么用呢？
看这张图：
途中我们算出了 A 然后现在上传到 B，由于 A 的 为 ，所以 B 的答案不小于 ，将 B 的 设置成 。
然后此时我们再来算 C 节点，要想对 B 有贡献，至少要提供 ，然后我们访问 C 中大小为 的节点，发现最大能提供的只有 ，了，所以矛盾，C 的其他节点不用访问了。
通过这种操作，我们就可以省去很多不必要的搜索。
好像也不是很难？
例题
UVA10111 Find the Winning Move
这道题中，我们就设计答案为 和 ，先手需要让答案变成 。操作就是向里面循环枚举每一个空的点位填数，然后来模拟遍历上面讲的树。
代码
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y;
};
char c[4][4];
string s,q[110];
int tot=0;
bool check(char c[4][4],char p){
for(int i=0;i<4;i++){
if(c[i][0]==p&&c[i][1]==p&&c[i][2]==p&&c[i][3]==p)return 1;
if(c[0][i]==p&&c[1][i]==p&&c[2][i]==p&&c[3][i]==p)return 1;
}
if(c[0][0]==p&&c[1][1]==p&&c[2][2]==p&&c[3][3]==p)return 1;
if(c[0][3]==p&&c[1][2]==p&&c[2][1]==p&&c[3][0]==p)return 1;
return 0;
}
bool full(char c[4][4]){
for(int i=0;i<4;i++)for(int j=0;j<4;j++)if(c[i][j]=='.')return 0;
return 1;
}
int ab(char c[4][4],int a,int b,bool m){
if(check(c,'x'))return 1;
if(check(c,'o'))return -1;
if(full(c))return 0;
int mn=1e9,mx=-1e9;
for(int i=0;i<4;i++){
for(int j=0;j<4;j++)if(c[i][j]=='.'){
char t[4][4];
for(int x=0;x<4;x++)for(int y=0;y<4;y++)t[x][y]=c[x][y];
if(m)t[i][j]='x';
else t[i][j]='o';
int go=ab(t,a,b,m^1);
if(m){
mx=max(mx,go);
a=max(a,go);
}else{
mn=min(mn,go);
b=min(b,go);
}
if(b<=a)break;
}
if(b<=a)break;
}
return (m?mx:mn);
}
node solve(char c[4][4]){
for(int i=0;i<4;i++)for(int j=0;j<4;j++)if(c[i][j]=='.'){
char t[4][4];
for(int x=0;x<4;x++)for(int y=0;y<4;y++)t[x][y]=c[x][y];
t[i][j]='x';
if(check(t,'x'))return {i,j};
if(ab(t,-1e9,1e9,0))return {i,j};
}
return {-1,-1};
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
string s;
while(getline(cin,s)&&s[0]!='$'){
while(s[0]==0)getline(cin,s);
if(s[0]=='$')break;
// cout<<" "<<(int)s[0]<<s<<endl;
for(int i=0;i<4;i++)for(int j=0;j<4;j++){
cin>>c[i][j];
// cout<<i<<' '<<j<<' '<<c[i][j]<<endl;
}
node ans=solve(c);
if(ans.x==-1)cout<<"#####\n";
else cout<<"("<<ans.x<<","<<ans.y<<")"<<'\n';
}
return 0;
}
舞蹈链（DLX）
首先这道题需要转化成另外一种暴力。
对于每一个选定的行，直接将所有的冲突的行删去，然后把变成 的列删去，重复这个过程。
这个是可以优化的。
DLX 就是一个双向二维链表，然后我们需要将为 的点加入这个巨大的链表中，起到快速维护刚刚的操作的作用。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m;
int cnt;
int l[250010],r[250010],u[250010],d[250010];
int col[250010],row[250010];
int h[250010];//每一行的第一个节点
int s[250010];//每一列的节点个数
int ans[250010];
void init(int m){//第 m 列的 DLX
for(int i=0;i<=m;i++){
r[i]=i+1;
l[i]=i-1;
u[i]=d[i]=i;
}
r[m]=0;
l[0]=m;
memset(h,-1,sizeof(h));
memset(s,0,sizeof(s));
cnt=m+1;
}
void link(int R,int C){//在 R 行地 C 列插入一个节点
/*此函数只需要保存 1 的节点就行了*/
s[C]++;
row[cnt]=R;
col[cnt]=C;
u[cnt]=C;
d[cnt]=d[C];
u[d[C]]=cnt;
d[C]=cnt;
if(h[R]==-1){
h[R]=l[cnt]=r[cnt]=cnt;
}else{
r[cnt]=h[R];
l[cnt]=l[h[R]];
r[l[h[R]]]=cnt;
l[h[R]]=cnt;
}
cnt++;
}
void del(int C){//删除 C 列
r[l[C]]=r[C];
l[r[C]]=l[C];
for(int i=d[C];i!=C;i=d[i]){
for(int j=r[i];j!=i;j=r[j]){
u[d[j]]=u[j];
d[u[j]]=d[j];
s[col[j]]--;
}
}
}
void add(int C){//恢复 C 列
/*需要和删除的操作顺序相反*/
for(int i=u[C];i!=C;i=u[i]){
for(int j=l[i];j!=i;j=l[j]){
u[d[j]]=j;
d[u[j]]=j;
s[col[j]]++;
}
}
r[l[C]]=C;
l[r[C]]=C;
}
bool dance(int x){
if(r[0]==0){
for(int i=0;i<x;i++)cout<<ans[i]<<' ';
cout<<endl;
return 1;
}
int c=r[0];
for(int i=r[0];i;i=r[i]){
if(s[i]<s[c])c=i;
}
del(c);
for(int i=d[c];i!=c;i=d[i]){
ans[x]=row[i];
for(int j=r[i];j!=i;j=r[j]){
del(col[j]);
}
if(dance(x+1)){
return 1;
}
for(int j=l[i];j!=i;j=l[j]){
add(col[j]);
}
}
add(c);
return 0;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0),cout.tie(0);
cin>>n>>m;
init(m);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
int a;
cin>>a;
if(a)link(i,j);
}
}
if(!dance(0)){
puts("No Solution!");
}
return 0;
}