回溯算法设计-new

116.2回溯算法设计《计算机导论与程序设计基础》2一.回溯算法的含义二.用回溯算法解决问题的一般步骤三.回溯法解题思路－－应用递归函数求解提纲3一.回溯算法的含义以组合问题为例：找出从自然数1、2、……、n中任取r个数的所有组合(要求r个数从小到大排列)。例如n=5，r=3的所有组合为：（1）1，2，3（2）1，2，4（3）1，2，5(4）1，3，4（5）1，3，5（6）1，4，5（7）2，3，4（8）2，3，5（9）2，4，5(10）3，4，5一.回溯算法的含义4一.回溯算法的含义求n=5，r=3的所有组合•算法1：使用前面学的穷举算法–罗列出3个数字剔重之后的5×4×3＝60种候选解。–利用限制条件（r个数从小到大排列）来剔除不符合要求的解。–算法评价：计算量大，可能候选解中只有一小部分解是符合要求的解。5一.回溯算法的含义求n=5，r=3的所有组合•算法2：使用回溯算法回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：在搜索问题的解时，从一条路往前走，能进则进，不能进则退（回溯）回来，换一条路再试。迷宫x1x2x3①②③④⑤③④⑤6一.回溯算法的含义二.用回溯算法解决问题的一般步骤三.回溯法解题思路－－应用递归函数求解提纲7二.用回溯算法解决问题的一般步骤二.用回溯算法解决问题的一般步骤：1.针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。2.确定易于搜索的解空间结构,使得能用回溯法方便地搜索整个解空间。3.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。问题的解空间通常是在搜索问题解的过程中动态产生的，这是回溯算法的一个重要特性。8第1步.定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解。例：求n=5，r=3的所有组合二.用回溯算法解决问题的一般步骤解空间中共有5×4×3＝60种可能的解，其中符合要求的解为（列举法）：{(1,2,3)，(1,2,4)，(1,2,5)，(1,3,4)，(1,3,5)，(1,4,5)，(2,3,4)，(2,3,5)，(2,4,5)，(3,4,5)}符合要求的解为（描述法）：E={（x1，x2，x3）∣xi∈S，1≤i≤3，且x1x2x3}其中：S={1，2，3，4，5}9第1步.定义问题的解空间。可用回溯法求解的问题P，下述集合E中的n元组组成了问题P的解空间：E={（x1，x2，…，xn）∣xi∈Si，1≤i≤n}其中Si是xi的定义域，且Si中元素个数有限。问题P的解：E中所有满足约束集D的n元组（D是对x1～xn取值的全部约束条件）。二.用回溯算法解决问题的一般步骤•n元组或多元组是对象个数有限的序列。多元组被数学家们用来描述确定成分的数学对象。多元组区别于集合的主要性质在于：（1）它可以多次含有某个对象；（2）对象按照一定顺序出现。10二.用回溯算法解决问题的一般步骤第2步.确定易于搜索的解空间结构。通常可以将解空间组织成一棵树，使得能用回溯法方便地搜索整个解空间。问题的解：{(1,2,3)，(1,2,4)，(1,2,5)，(1,3,4)，(1,3,5)，(1,4,5)，(2,3,4)，(2,3,5)，(2,4,5)，(3,4,5)}x1x2x3①②③④⑤③④⑤②④⑤③④⑤④⑤③④⑤11二.用回溯算法解决问题的一般步骤•树的定义：树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点。①②③④⑤③④⑤④⑤根结点深度宽度12二.用回溯算法解决问题的一般步骤第3步.以深度优先的方式搜索解空间回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。13搜索问题解，建立解空间－1x1x2x3①②③④⑤③④⑤②④⑤③④⑤④⑤③④⑤⑤⑤深度14一.回溯算法的含义二.用回溯算法解决问题的一般步骤三.回溯法解题思路－－应用递归函数求解提纲15三.回溯法解题思路–就是求所有满足条件D的n元组(x1，x2，…,xn)–为求n元组(x1，x2，…,xn)，可以先求出x1，然后再求n-1元组(x2，…,xn）。这样，求(x1，x2，…,xn)的问题被转化为规模小一级但同性质的求(x2，…,xn)的问题。–同理，求(x2，…,xn)的问题可以转化为求(x3，…,xn)的问题，如此不断转化，问题规模不断减小。–当被转化为求一元组(xn)时，可以直接给出结果，而不需要继续转化。–这就是递归算法实现回溯法的思想。三.回溯法解题思路16例1.求n=5，r=3的所有组合。•问题分析：求组合其实就是求满足条件的3元组(x1,x2,x3)。可以设计递归函数求解元组(xi,…,xn)。•递归函数参数设计考虑：–i肯定是作为一个参数，那么n是作为参数还是其他采用方式（如全局变量、常量）？–xi的取值范围是递归函数必须要获得的。–求得的元组采用什么数据结构存放？采用全局变量还是使用形式参数？三.回溯法解题思路－应用递归函数求解17递归函数设计：求元组(xi，…,xn)voidtry(inti,intn,intmin,intmax,intresult[],intsize)参数说明：i和n：表示递归函数求元组(xi，…,xn)min和max：min≤xj≤maxresult[]：存放元组size：result的长度三.回溯法解题思路－应用递归函数求解18三.回溯法解题思路－应用递归函数求解for(xi=min;xi=max;xi++)确定xi:result[i]=xii==nNY输出n元组递归求元组（xi+1,...xn）：try(i+1,n,xi+1,max,result)求元组（xi,...xn）：组合问题voidtry(inti,intn,intmin,intmax,intresult[])清空xi:result[i]=019voidtry(inti,intn,intmin,intmax,intresult[],intsize){intxi,j;for(xi=min;xi=max;xi++){//依次试探xiresult[i]=xi;//确定xiif(i==n){//若本次是求一元组，则递归结束，输出结果for(j=1;j=size-1;j++)printf(%-5d,result[j]);printf(\n);}elsetry(i+1,n,xi+1,max,result,size);//继续求解(xi+1,…,xn)result[i]=0;//清空xi}组合问题递归函数20组合问题主函数#includestdio.h#defineN3main(){intresult[N+1]={0};/*记录一个N元组,a[i]记录xi*/try(1,3,1,5,result,N+1);/*调用递归函数求3元组*/system(pause);return0;}21例2.跳马问题有一块n*n的格子的棋盘，一位骑士放在初始坐标为X0,Y0的格子里,并按照象棋的移动规则移动。提出的问题是：是否可以找到可以走遍整个棋盘的方案。即经过一个n*n-1次移动的巡游，使得棋盘上每一个格子恰好被访问一次。输出各方案及总方案数。三.回溯法解题思路－应用递归函数求解22(x-2,y-1)(x-2,y+1)(x-1,y-2)(x-1,y+2)(x,y)(x+1,y-2)(x+1,y+2)(x+2,y-1)(x+2,y+1)从(x,y)出发，下一步可以走的八种选择：三.回溯法解题思路－应用递归函数求解23第1步：定义解空间•假设是5×5的棋盘,则本题实际就是求解由25元组组成的状态空间E。E={（x1，x2，…,x25）∣xi∈S，1≤i≤25}其中：S是棋盘上的25个坐标x,y组成的集合xi代表第i步的坐标约束集D为：x1~x25互不相等三.回溯法解题思路－应用递归函数求解24三.回溯法解题思路－应用递归函数求解第2步.采用一棵树描述解空间，树的深度为25。第3步.动态搜索并建立解空间。………………共25个结点……25解题思路：1）元组的存放（即旗盘路线）：用一个全局二维数组存储intboard[SIZE][SIZE];//SIZE表示棋盘的行和列数三.回溯法解题思路11621102520112415221721969127423143181385表示第22步走到此位置26三.回溯法解题思路2）递归函数设计：用于求元组(xi～xn)。由于必须在xi-1基础上根据移动规则确定xi，因此需要将xi的坐标x,y作为参数传入。voidtry(inti,intn,intx,inty)27三.回溯法解题思路for(dir=0;dir=7;dir++)根据行走方向确定下一步坐标u,v新坐标在棋盘上且这一步可以走YN递归求元组（xi+1,...xn）：try(i+1,n,u,v)求元组（xi,...xn）：跳马问题voidtry(inti,intn,intx,inty)占据位置u,v已走完25步YN输出结果释放位置u,v283）如何在xi-1坐标x,y基础上确定xi的各个可能坐标u,v：introw[8]={1,2,2,1,-1,-2,-2,-1};/*8个方向上的x增量*/intcol[8]={-2,-1,1,2,2,1,-1,-2};/*8个方向上的y增量*/for(dir=0;dir=7;dir++){/*依次试遍8个方向*/u=x+row[dir];/*得到的新坐标*/v=y+col[dir];}4）递归结束条件：第i步有位置可走且i等于25三.回溯法解题思路29s//函数功能：从step[i-1]出发，求(step[i]~step[SIZE*SIZE])。step[i-1]坐标为（x，y）voidtry(inti,intn,intx,inty){intdir,u,v;for(dir=0;dir=7;dir++){/*依次试遍8个方向*/u=x+row[dir];/*得到的新坐标*/v=y+col[dir];/*如果新坐标在棋盘上，并且这一格可以走*/if((u=0)&&(u=SIZE-1)&&(v=0)&&(v=SIZE-1)&&(board[u][v]==0)){board[u][v]=i;/*占据位置[u,v]*/if(i==n){//已经走完25步，则统计方案个数，打印方案，跳出递归num++;printSolution();//打印方案}elsetry(i+1,n,u,v);//从xi出发，递归求(xi+1,…,xn)board[u][v]=0;//清空位置。不可少！}//endofif}//endoffor}跳马问题递归函数30#includestdio.h#defineSIZE5introw[8]={1,2,2,1,-1,-2,-2,-1};/*8个方向上的x增量*/intcol[8]={-2,-1,1,2,2,1,-1,-2};/*8个方向上的y增量*/intboard[SIZE][SIZE]={0};/*记录走的路径*/intnum;/*记录方案总个数*/main(){introw,col;/*初始化*/num=0;board[0][0]=1;/*占据位置（0,0）*/try(2,SIZE*SIZE,0,0);/*从(0,0)出发，寻找后续位置*//*输出总方案数*/printf(总方案数为%d,