暴力求解
我们经常说暴力出奇迹,但是往往我们选择的方法都是暴力模拟,可以说对其的优化基本为0,最近看了刘汝佳的暴力求解章,在此文中对暴力枚举的几个方向选择进行简单的归类。本章的算法主要是对解答树进行处理与剪枝,让搜索最优。
- 直接枚举(纯暴力)
- 枚举子集和排列
- dfs+回溯
- 状态空间搜索
- 迭代加深搜索(IDA*)
直接枚举(纯暴力)
最基本的直接枚举但是这种算法往往枚举效率不高,对于数据较小或者部分数据点的情况下可以去卡点偷分,在这不在赘述。
枚举子集和排列
n个元素的子集有2n个,可以用递归的方法枚举。
第一个问题就是全排列问题,此处注意生成全排列时重复产生的问题,如(1,2,2,4,5)的全排列,同时也要学会STL中(next_permutation)的使用。
1 do{
2 for(int i=0;i<n;i++) printf("%d ",p[i]);
3 printf("\n");
4 } while(next_permutation(p,p+n));
第二个问题就是枚举子集,这下面三个枚举方法非常典型,在今年的蓝桥总赛上就非常适合偷分。
增量构造法,每次选择一个元素往里添加。
1 void print_subset(int n,int a[],int cur) 2 { 3 for(int i=0;i<cur;i++) cout<<a[i]<<" "; 4 cout<<endl; 5 int s=cur?a[cur-1]+1:0; 6 for(int i=s;i<n;i++) 7 { 8 a[cur]=i; 9 print_subset(n,a,cur+1); 10 } 11 }
位增量法,用tar标记是否出现元素。
1 void print_subset(int n,int a[],int cur) 2 { 3 if(cur==n) 4 { 5 for(int i=0;i<cur;i++) if(a[i]) printf("%d ",i); 6 cout<<"\n"; 7 return; 8 } 9 a[cur]=1; print_subset(n,a,cur+1); 10 a[cur]=0; print_subset(n,a,cur+1); 11 }
二进制法,利用移运算进行求解,适合数据较小时的情况。
1 void print_subset(int n, int s){ 2 for(int i=0;i<n;i++) 3 if(s&(1<<i)) printf("%d",i); 4 printf("\n"); 5 }
dfs+回溯
可以把这个算法理解为在递增的过程中进行检查(剪枝),从而减少没必要的枚举。
那个例题进行讲解(八皇后问题):
分析一下解答树,如果完全模拟子集的大小C864=4.425*109显然是一个不完美的算法,因此当我们放入不了的时候即剪枝。
1 void f(int x,int a[])
2 {
3 if(x==n+1)
4 if(ans<=3)
5 {
6 for(int ii=1;ii<=n;ii++) cout<<a[ii]<<" ";
7 cout<<"\n";
8 }
9 else{
10 for(int i=1;i<=n;i++)
11 {
12 int left,right;
13 left=x+i-1;
14 right=x+n-i;
15 if((!y[i])&&(!l[left])&&(!r[right]))
16 {
17 y[i]=l[left]=r[right]=1; a[x]=i;
18 f(x+1,a); y[i]=l[left]=r[right]=0;
19 }
20 }
21 }
22 }
这就是一个回溯的入门题,以下是典型的例题:
状态空间搜索
此算法经常和图论结合在一起,解法是确定搜索空间,确定搜索方式,确定排重方法。
以八数码问题为例子,首先确定搜索空间与方法我们以空格为移动点进行移动,这类大的搜索问题我们不尽量不用dfs来进行搜索,防止爆栈的情况。
1 int bfs()
2 {
3 init_lookup_table();
4 int front=1,rear=2;
5 while(front<rear){
6 state &s=st[front];
7 if(memcmp(goal,s,sizeof(s))==0) return front;
8 int z;
9 for(z=0;z<9;z++) if(!s[z]) break;
10 int x=z/3,y=z%3;
11 for(int d=0;d<4;d++){
12 int newx=x+dx[d];
13 int newy=y+dy[d];
14 int newz=newx*3+newy;
15 if(newx>=0&&newx<3&&newy>=0&&newy<3){
16 state &t=st[rear];
17 memcpy(&t,&s,sizeof(s));
18 t[newz]=s[z];
19 t[z]=s[newz];
20 dist[rear]=dist[front]+1;
21 if(try_to_insert(rear)) rear++;
22 }
23 }
24 front++;
25 }
26 return 0;
27 }
其次选择排重方式,再次介绍三种典型的排重方式:
STL
1 set<int> vis; 2 void init_lookup_table() {vis.clear();} 3 int try_to_insert(int s){ 4 int v=0; 5 for(int i=0;i<9;i++) v=v*10+st[s][i]; 6 if(vis.count(v)) return 0; 7 vis.insert(v); 8 return 1; 9 }
hash
1 const int hashsize=1000003; 2 int head[hashsize],next[maxstate]; 3 void init_lookup_table(){memset(head,0,sizeof(head));} 4 int hash(State&s){ 5 int v=0; 6 for(int i=0;i<9;i++) v=v*10+s[i]; 7 return v%hashsize; 8 } 9 int try_to_insert(int s){ 10 int h=hash(st[s]); 11 int u=head[h]; 12 while(u){ 13 if(memcmp(st[u],st[s],sizeof(st[s]))==0) return 0; 14 u=next[u]; 15 } 16 next[s]=head[h]; 17 head[h]=s; 18 return 1; 19 }
编解码
1 int vis[362880],fact[9]; 2 void init_lookup_table(){ 3 fact[0]=1; 4 for(int i=1;i<9;i++) fact[i]=fact[i-1]*i; 5 } 6 int try_to_insert(int s){ 7 int code=0; 8 for(int i=0;i<9;i++){ 9 int cnt=0; 10 for(int j=i+1;j<9;j++) if(st[s][j]<st[s][i]) cnt++; 11 code+=fact[8-i]*cnt; 12 } 13 if(vis[code]) return 0; 14 return vis[code]=1; 15 }
IDA*
这个算法一般比较少用,用在没有上界或者解答树非常恐怖的时候,我们利用预估函数和逐渐放大答案的方式进行搜索。
其中以埃及分数问题最为典型,我们把组成的分数作为上界进行扩展。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long LL;
4 const int maxn = 1e6+10;
5 LL maxd,a,b;
6 LL ans[maxn],v[maxn];
7 LL get_first(LL xa,LL xb) {return xb/xa+1;}
8 bool better(int d)
9 {
10 for(int i=d;i>=0;i--)
11 if(v[i]!=ans[i])
12 return ans[i]==-1||v[i]<ans[i];
13 return false;
14 }
15 bool dfs(int d,LL from,LL aa,LL bb)
16 {
17 if(d==maxd){
18 if(bb%aa) return false;
19 v[d]=bb/aa;
20 if(better(d)) memcpy(ans,v,sizeof(LL)*(d+1));
21 return true;
22 }
23 bool ok=false;
24 from=max(from,get_first(aa,bb));
25 for(int i=from;;i++){
26 if(bb*(maxd+1-d)<=i*aa) break;
27 v[d]=i;
28 LL b2=bb*i;
29 LL a2=aa*i-bb;
30 LL g=__gcd(a2,b2);
31 if(dfs(d+1,i+1,a2/g,b2/g)) ok=true;
32 }
33 return ok;
34 }
35 int main()
36 {
37 scanf("%lld%lld",&a,&b);
38 int ok=0;
39 for(maxd=1;;maxd++)
40 {
41 memset(ans,-1,sizeof(ans));
42 if(dfs(0,get_first(a,b),a,b)) {ok=1; break;}
43 }
44 printf("%lld/%lld=",a,b);
45 int first=1;
46 for(int i=0;i<=maxd;i++)
47 if(~ans[i]){
48 if(first) first=0;
49 else printf("+");
50 printf("1/%lld",ans[i]);
51 }
52 return 0;
53 }
典型例题:编辑书稿
从整体上来说这一章算法是一个比较暴力的算法但在剪枝优化上,代码考验上还是非常值得深究的。