本文在写作过程中参考了大量资料,不能一一列举,还请见谅。
回溯算法的定义:回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。
解题的一般步骤是:
1.定义一个解空间,它包含问题的解;
2.利用适于搜索的方法组织解空间;
3.利用深度优先法搜索解空间;
4.利用限界函数避免移动到不可能产生解的子空间。
问题的解空间通常是在搜索问题的解的过程中动态产生的,这是回溯算法的一个重要特性。
话不多说,我们来看几个具体的例子慢慢理解它:
1.八皇后问题
该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 下面的解法参考了《算法竞赛入门经典》。如果我们逐行放置皇后则肯定没有任意两个皇后位于同一行,只需要判断列和对角线即可。使用一个二维数组vis[3][],其中vis[0][i]表示列,vis[1][i]和vis[2][i]表示对角线。因为(x,y)的y-x值标识了主对角线,x+y值标识了副对角线。由于y-x可能为负,所以存取时要加上n。
#include<cstring> #include<iostream> using namespace std; int vis[3][15],tot; void search(int cur) { int i,j; if(cur==8) tot++; else { for(i=0;i<8;i++) { if(!vis[0][i]&&!vis[1][cur-i+8]&&!vis[2][cur+i]) { vis[0][i]=1; vis[1][cur-i+8]=1; vis[2][cur+i]=1; search(cur+1); //改回辅助的全局变量 vis[0][i]=0; vis[1][cur-i+8]=0; vis[2][cur+i]=0; } } } } int main() { search(0); cout<<tot<<endl; }
给定图和颜色的数目求出着色方法的数目,可以使用回溯法。
#define N 100 #include<iostream> using namespace std; int v,e,c,graph[N][N],color[N]; //顶点数,边数,颜色数 int sum; bool ok(int k) { for(int j=1;j<=v;j++) { if(graph[k][j]&&(color[j]==color[k])) return false; } return true; } void backtrack(int t) { if(t>v) sum++; else { for(int i=1;i<=c;i++) { color[t]=i; if(ok(t)) backtrack(t+1); //改回辅助的全局变量 color[t]=0; } } } int main() { int i,j; cin>>v>>e>>c; for(i=1;i<=v;i++) { for(j=1;j<=v;j++) { graph[i][j]=0; } } for(int k=1;k<=e;k++) { cin>>i>>j; graph[i][j]=1; graph[j][i]=1; } for(i=0;i<=v;i++) color[i]=0; backtrack(1); cout<<sum<<endl; }
3.装载问题
有一批共n个集装箱要装上2艘载重量分别为c1和c2的船,其中集装箱i的重量为wi,且。装载问题要求确定是否有一个合理的装载方案可将这些集装箱装上这2艘船。如果有,找出一种装载方案。例如当n=3,c1=c2=50且w=[10,40,40]时,则可以将集装箱1和2装到第一艘轮船上,而将集装箱3装到第二艘轮船上;如果w=[20,40,40],则无法将这3个集装箱都装上轮船。容易证明,如果一个给定装载问题有解,则首先将第一艘船尽可能装满再将剩余的集装箱装上第二艘船可得到最优装载方案。将第一艘船尽可能装满等价于选取全体集装箱的一个子集,使该子集中集装箱重量之和最接近c1。用回溯法解装载问题, 时间复杂度O(2^n),在某些情况下优于动态规划算法。剪枝方案是如果当前已经选择的全部物品载重量cw+剩余集装箱的重量r<=当前已知的最优载重量bestw,则删去该分支。
#include<iostream> using namespace std; int n;//集装箱数 int w[40];//集装箱重量 int c1,c2;//两艘船的载重量 int ans;//当前载重量 int bestans;//当前最优载重量 int r;//剩余集装箱重量 void backtrack(int i) { if(i>n) { if(ans>bestans) bestans=ans; return; } r-=w[i]; if(ans+w[i]<=c1) { ans+=w[i]; backtrack(i+1); //改回辅助的全局变量 ans-=w[i]; } if(ans+r>bestans) backtrack(i+1); //改回辅助的全局变量 r+=w[i]; } int maxloading() { ans=0; bestans=0; backtrack(1); return bestans; } int main() { cin>>n>>c1>>c2; int i=1; int sum=0; //集装箱总重量 while(i<=n) { cin>>w[i]; r+=w[i]; sum+=w[i]; i++; } maxloading(); if(bestans>0&&((sum-bestans)<=c2)) cout<<bestans<<endl; else if(sum<=c2) cout<<bestans<<endl; else cout<<"No"<<endl; }
tji | 机器1 | 机器2 |
作业1 | 2 | 1 |
作业2 | 3 | 1 |
作业3 | 2 | 3 |
例如,对于这张表格所示的情况,3个作业有3!=6种可能调度方案,很显然最坏复杂度即为O(n!)。如果按照2,3,1的顺序,则作业2的完成时间为4,作业3的完成时间为8,作业1的完成时间为9,完成时间和为21。最优的作业调度顺序为最佳调度方案是1,3,2,其完成时间和为18。
#define MAX 200 #include<iostream> using namespace std; int* x1;//作业Ji在机器1上的工作时间 int* x2;//作业Ji在机器2上的工作时间 int number=0;//作业的数目 int* xorder;//作业顺序 int* bestorder;//最优的作业顺序 int bestvalue=MAX;//最优的时间 int xvalue=0;//当前完成用的时间 int f1=0;//机器1完成的时间 int* f2;//机器2完成的时间 void backtrack(int k) { if(k>number) { for(int i=1;i<=number;i++) bestorder[i]=xorder[i]; bestvalue=xvalue; } else { for(int i=k;i<=number;i++) { f1+=x1[xorder[i]]; f2[k]=(f2[k-1]>f1?f2[k-1]:f1)+x2[xorder[i]]; xvalue+=f2[k]; swap(xorder[i],xorder[k]); if(xvalue<bestvalue) backtrack(k+1); swap(xorder[i],xorder[k]); xvalue-=f2[k]; f1-=x1[xorder[i]]; } } } int main() { cout<<"请输入作业数目:"; cin>>number; x1=new int[number+1]; x2=new int[number+1]; xorder=new int[number+1]; bestorder=new int[number+1]; f2=new int[number+1]; x1[0]=0; x2[0]=0; xorder[0]=0; bestorder[0]=0; f2[0]=0; cout<<"请输入每个作业在机器1上所用的时间:"<<endl; int i; for(i=1;i<=number;i++) { cout<<"第"<<i<<"个作业="; cin>>x1[i]; } cout<<"请输入每个作业在机器2上所用的时间:"<<endl; for(i=1;i<=number;i++) { cout<<"第"<<i<<"个作业="; cin>>x2[i]; } for(i=1;i<=number;i++) xorder[i]=i; backtrack(1); cout<<"最节省的时间为:"<<bestvalue<<endl; cout<<"对应的方案为:"; for(i=1;i<=number;i++) cout<<bestorder[i]<<" "; cout<<endl; }
5.再再论背包问题
在 从零开始学动态规划和 从零开始学贪心算法中我们已经讨论过了背包问题,这里我们再次用回溯法求解经典的零一背包问题。
#include<iostream> using namespace std; int n,c,bestp;//物品个数,背包容量,最大价值 int p[10000],w[10000],x[10000],bestx[10000];//物品的价值,物品的重量,物品的选中情况 void backtrack(int i,int cp,int cw) { if(i>n) { if(cp>bestp) { bestp=cp; for(i=1;i<=n;i++) bestx[i]=x[i]; } } else { for(int j=0;j<=1;j++) { x[i]=j; if(cw+x[i]*w[i]<=c) { cw+=w[i]*x[i]; cp+=p[i]*x[i]; backtrack(i+1,cp,cw); cw-=w[i]*x[i]; cp-=p[i]*x[i]; } } } } int main() { bestp=0; cin>>c>>n; for(int i=1;i<=n;i++) cin>>w[i]; for(int i=1;i<=n;i++) cin>>p[i]; backtrack(1,0,0); cout<<bestp<<endl; }
最大团问题可以用回溯法在O(n2^n)的时间内解决。首先设最大团为一个空团,往其中加入一个顶点,然后依次考虑每个顶点,查看该顶点加入团之后仍然构成一个团。程序中采用了一个比较简单的剪枝策略,即如果剩余未考虑的顶点数加上团中顶点数不大于当前解的顶点数,可停止回溯。用邻接矩阵表示图G,n为G的顶点数,cn存储当前团的顶点数,bestn存储最大团的顶点数。当cn+n-i<bestn时,不能找到更大的团,利用剪枝函数剪去。
#include<iostream> using namespace std; const int maxnum=101; bool graph[maxnum][maxnum]; bool use[maxnum],bestuse[maxnum]; int cn,bestn,v,e; void backtrack(int i) { if(i>v) { if(cn>bestn) { bestn=cn; for(int j=1;j<=v;j++) bestuse[j]=use[j]; return; } } bool flag=true; for(int j=1;j<i;j++) { if(use[j]&&!graph[j][i]) { flag=false; break; } } if(flag) { cn++; use[i]=true; backtrack(i+1); use[i]=false; cn--; } if(cn+v-i>bestn) { use[i]=false; backtrack(i+1); } } int main() { cin>>v>>e; for(int i=1;i<=e;i++) { int p1,p2; cin>>p1>>p2; graph[p1][p2]=true; graph[p2][p1]=true; } backtrack(1); cout<<bestn<<endl; for(int i=1;i<=v;i++) { if(bestuse[i]) cout<<i<<" "; } cout<<endl; }
7.圆排列问题
给定n个大小不等的圆c1,c2,…,cn,现要将这n个圆排进一个矩形框中,且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如,当n=3,且所给的3个圆的半径分别为1,1,2时,这3个圆的最小长度的圆排列如图所示。其最小长度为。
注意,下面代码中圆排列的圆心横坐标以第一个圆的圆心为原点。所以,总长度为第一个圆的半径+最后一个圆的半径+最后一个圆的横坐标。
#include<cmath> #include<iostream> #include<algorithm> using namespace std; float minlen=10000,x[4],r[4];//当前最优值,当前圆排列圆心横坐标,当前圆排列 int n;//圆排列中圆的个数 //计算当前所选择圆的圆心横坐标 float center(int t) { float temp=0; for(int j=1;j<t;j++) { //由x^2=sqrt((r1+r2)^2-(r1-r2)^2)推导而来 float valuex=x[j]+2.0*sqrt(r[t]*r[j]); if(valuex>temp) temp=valuex; } return temp; } //计算当前圆排列的长度 void compute() { float low=0,high=0; for(int i=1;i<=n;i++) { if(x[i]-r[i]<low) low=x[i]-r[i]; if(x[i]+r[i]>high) high=x[i]+r[i]; } if(high-low<minlen) minlen=high-low; } void backtrack(int t) { if(t>n) compute(); else { for(int j=t;j<=n;j++) { swap(r[t],r[j]); float centerx=center(t); if(centerx+r[t]+r[1]<minlen) { x[t]=centerx; backtrack(t+1); } swap(r[t],r[j]); } } } int main() { n=3; r[1]=1,r[2]=1,r[3]=2; cout<<"各圆的半径分别为:"<<endl; for(int i=1;i<=3;i++) cout<<r[i]<<" "; cout<<endl; cout<<"最小圆排列长度为:"; backtrack(1); cout<<minlen<<endl; }
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #define MAXN 200 using namespace std; int h,k,ans[MAXN],stampval[MAXN],maxval[MAXN],maxstampval; bool vis[MAXN]; //标记每种取到的钱数 void mark(int n,int m,int sum) { if(m>h) return; vis[sum]=true; for(int i=1;i<=n;++i) mark(n,m+1,sum+stampval[i]); } void backtrack(int cur) { if(cur>k) { if(maxval[cur-1]>maxstampval) { maxstampval=maxval[cur-1]; memcpy(ans,stampval,sizeof(stampval)); } return; } for(int i=stampval[cur-1]+1;i<=maxval[cur-1]+1;++i) { memset(vis,0,sizeof(vis)); stampval[cur]=i; mark(cur,0,0); int num=0,j=1; while(vis[j++]) ++num; maxval[cur]=num; backtrack(cur+1); } } int main() { while(scanf("%d %d",&h,&k),h+k) { maxval[1]=h; stampval[1]=1; maxstampval=-1; backtrack(2); for(int i=1;i<=k;++i) printf("%3d",ans[i]); printf("->%3d\n",maxstampval); } }
#include<iostream> using namespace std; int n,half,counts,p[100][100],sum; //第一行的符号个数,n*(n+1)/4,当前"+"号个数,符号三角矩阵,已找到的符号三角形数 void backtrack(int t) { if((counts>half)||(t*(t-1)/2-counts>half)) return; if(t>n) sum++; else { for(int i=0;i<2;i++) { p[1][t]=i;//第一行符号 counts+=i;//当前"+"号个数 for(int j=2;j<=t;j++) { p[j][t-j+1]=p[j-1][t-j+1]^p[j-1][t-j+2]; counts+=p[j][t-j+1]; } backtrack(t+1); for(int j=2;j<=t;j++) { counts-=p[j][t-j+1]; } counts-=i; } } } int main() { cin>>n; half=n*(n+1)/2; if(half%2==1) { cout<<"共有0个不同的符号三角形。"<<endl; return 0; } half=half/2; backtrack(1); cout<<"共有"<<sum<<"个不同的符号三角形。"<<endl; }
#include<iostream> using namespace std; int graph[25][25]; int set[25]; int ans,n; void backtrack(int x,int sum) { int temp; if(x>n) { if(sum>ans) ans=sum; return; } //不选 set[x]=0; temp=0; for(int i=1;i<=x;i++) { if(!set[i]) continue; temp+=graph[i][x]; } backtrack(x+1,sum+temp); //选 set[x]=1; temp=0; for(int i=1;i<=x;i++) { if(set[i]) continue; temp+=graph[i][x]; } backtrack(x+1,sum+temp); } int main() { cin>>n; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>graph[i][j]; } } backtrack(1,0); cout<<ans<<endl; }
关于回溯算法的基础知识就简要介绍到这里,希望能作为大家继续深入学习的基础。
发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/232997.html原文链接:https://javaforall.net