第三章回溯法

内科大ACM程序设计协会第三章回溯法1．算法思想回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(boundingfunction)来处死那些实际上不可能产生所需解的结点，以减少问题的计算量。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先根据限界函数判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。具有限界函数的深度优先生成法称为回溯法。有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。例3.1全排列从n个不同元素中任取m（m≤n）个元素，按照一定的顺序排列起来，叫做从n个不同元素中取出m个元素的一个排列。当m＝n时所有的排列情况叫全排列。如123三个元素的全排列为：123132213231312321程序代码如下：算法1#includestdio.h#defineMAX100//最多可排列100个数字inta[MAX];//记录要排列的数字intb[MAX];//记录当前排列好的数字intused[MAX];//每个数字是否被用过，0表示没有排过，1表示排过（标记）intn;//数字个数voidoutput(){inti;for(i=0;in;i++)printf(%d,b[i]);printf(\n);}voidarrange(intk)//当前排第k个数字{inti;for(i=0;in;i++)//搜索解空间树（即将数组a中的数依次取出来排列）{if(!used[i])//限界函数（即如果这个数字没被排过）{b[k]=a[i];//就将它排入数列used[i]=1;//标记此数字已被排过if(k==n-1)//如果所有的数字都被排列了output();//则输出这个数组elsearrange(k+1);//否则排下一个//回溯部分b[k]=-1;//重新排列第k个数字used[i]=0;//记录第i个数字待排。}}}voidmain(){inti;scanf(%d,&n);for(i=0;in;i++)//初始化{a[i]=i+1;b[i]=-1;//-1表示此位置没有排入数字used[i]=0;}arrange(0);//从第一个数字开始排列}运行结果：输入3输出123132213231312321算法2算法思路先控制一个不动，让剩余的排列好，然后再移动第一个，再排列好剩余的。#includestdio.h#defineMAX100inta[MAX];//最多可排列100个数字intn;//要排列的数字个数voidoutput(){inti;for(i=0;in;i++)printf(%d,a[i]);printf(\n);}intswap(intt1,intt2)//交换数组元素{inttemp;temp=a[t1];a[t1]=a[t2];a[t2]=temp;return1;}intarrange(intk){inti;if(k==n)output();elsefor(i=k;in;i++)////搜索解空间树{swap(k,i);//交换arrange(k+1);//进行下两个数的交换swap(k,i);//回溯（即再换回来）}return1;}intmain(){inti;scanf(%d,&n);for(i=0;in;i++)//初始化数组a[i]=i+1;arrange(0);printf(\n);return0;}运行结果：输入3输出123132213231321312（注意这两个程序输出的全排列顺序不同。）扩展：如果在算法1中去掉限界函数，那么这个程序输出的就是当前状况下的解空间树。程序代码如下（以1，2，3三个数为例）：#includestdio.hintn=3;inta[3];voidsearch(intm){if(m==n)printf(%d%d%d\n,a[0],a[1],a[2]);else{for(inti=1;i=3;i++){a[m]=i;search(m+1);}}}voidmain(){search(0);}运行结果111112113121122123…331332333有重复的全排列设R={r1，r2，…，rn}是要进行排列的n个元素，其中的元素r1，r2，…，rn可能相同。列出R的所有不同排列。例如：{1，1，2，2}的不同排列如下：112212121221211221212211程序代码如下：#includestdio.h#defineMAX100inta[MAX];//最多可排列100个数字intn;//要排列的数字个数voidoutput(){inti;for(i=0;in;i++)printf(%d,a[i]);printf(\n);}intswap(intt1,intt2)//交换数组元素{inttemp;temp=a[t1];a[t1]=a[t2];a[t2]=temp;return1;}intOK(intk,inti)//限界函数{intt;if(ik)for(t=k;ti;t++)if(a[t]==a[i])return0;return1;}intarrange(intk){inti;if(k==n)output();elsefor(i=k;in;i++)////搜索解空间树{if(OK(k,i))//去掉有重复的排列{swap(k,i);//交换arrange(k+1);//进行下两个数的交换swap(k,i);//回溯（即再换回来）}}return1;}intmain(){inti;scanf(%d,&n);for(i=0;in;i++)//初始化数组scanf(%d,&a[i]);arrange(0);printf(\n);return0;}圆的排列问题（有重复的全排列）给定n个大小不等的圆c1,c2,…,cn，现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。例如，当n=3，且所给的3个圆的半径分别为1，1，2时，这3个圆的最小长度的圆排列如图所示。其最小长度为7.656854。程序代码如下：#includestdio.h#includemath.h#defineMAX100//最多可排列100个数字inta[MAX];//最多可排列100个数字intn;//要排列的数字个数doublex;//当前最优解doublebestx;//最优解voidInputData(){inti;scanf(%d,&n);for(i=0;in;i++)//初始化scanf(%d,&a[i]);//输入当前圆的半径x=0;bestx=100000;}intSwap(intt1,intt2)//交换数组元素{inttemp;temp=a[t1];a[t1]=a[t2];a[t2]=temp;return1;}intOK(intk,inti)//限界函数{intt;if(ik)for(t=k;ti;t++)if(a[t]==a[i])return0;return1;}intArrange(intk){inti,j;if(k==n){for(j=0;jn-1;j++)x=x+sqrt((a[j]+a[j+1])*(a[j]+a[j+1])-abs(a[j]-a[j+1])*abs(a[j]-a[j+1]));x=x+a[n-1]+a[0];if(bestxx){//for(j=0;jn;j++)//printf(%d,b[j]);//printf(\n);//printf(%f\n,x);bestx=x;}x=0;}elsefor(i=k;in;i++)////搜索解空间树{if(OK(k,i))//去掉有重复的排列{Swap(k,i);//交换Arrange(k+1);//进行下两个数的交换Swap(k,i);//回溯（即再换回来）}}return1;}intmain(){inti;InputData();Arrange(0);printf(%f\n,bestx);return0;}旅行售货员问题设某旅行售货员要到多个城市推销商品，已知各城市之间的路程（旅费），为其设计一条售货路线，要求从某驻地出发经过每个城市一趟，最后回到驻地，使总的路费（旅费）最小。对问题的形式描述是：设G=（V，E）是一个带权图（用邻接矩阵表示），图中各条边的权（费用）为正整数，图中的每一条周游路线是包含V中所有顶点的一条回路，一条周游路线的费用是这条回路上所有边的权之和，所谓旅行售货员问题就是要在图G中找出一条有最小费用的周游路线。该问题的解空间树是一棵排列树。即对这些节点进行全排列，找出符合条件的路线。程序代码如下：#includestdio.hintn;//城市个数，即图的节点个数inta[20][20];//图的邻接矩阵,值表示费用intb[20];//初始化的数组intx[20];//当前排列的城市顺序intbestx[20];//最优城市排列intc;//费用intbextc;//最优费用intused[20];//排列标记,0表示没有排过，1表示已经排过。voidInputData(){inti,j;scanf(%d,&n);for(i=0;in;i++){for(j=i+1;jn;j++){scanf(%d,&a[i][j]);a[j][i]=a[i][j];}}for(i=0;in;i++){used[i]=0;b[i]=i;}c=0;bextc=100000;//伪无群大}voidArrange(intk){inti,j;if(k==n){//for(j=0;jn;j++)//printf(%d,x[j]);//printf(\n);for(j=0;jn-1;j++)c=c+a[x[j]][x[j+1]];c=c+a[x[n-1]][x[0]];if(bextcc){bextc=c;for(j=0;jn;j++)bestx[j]=x[j]+1;}c=0;}for(i=0;in;i++){if(!used[i]){x[k]=b[i];used[i]=1;Arrange(k+1);x[k]=-1;used[i]=0;}}}voidmain(){inti;InputData();Arrange(0);printf(%d\n,bextc);for(i=0;in;i++)printf(%d,bestx[i]);printf(\n);}n后问题在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。程序代码如下：例3.20-1背包问题给定n种物品和一背包。物品i的重量是Wi，其价值为Vi，背包的容量为c，问应如何选则物品，使得装入背包中物品的总价值最大？不能将物品i装入多次，也不能只装入部分的物品i。下图是3个物品的0-1背包问题的解空间树。下面这个程序是输出这个解空间树的所有解。程序代码如下：#includestdio.hintn=3;inttake[3];voidsearch(intk){if(k==n)printf(%d%d%d\n,take[0],take[1],take[2]);else{take[k]=0;//不选第m件物品search(k+1);//递归搜索下一件物品take[k]=1;//选第m件物品search(k+1);//递归搜索下一件物}}voidmain(){search(0);}再加上限制条件可以写出求解0-1背包问题