第5章-回溯法-New剖析(1).ppt

第5章回溯法,引入问题,回溯是重要的算法之一要求找到一组解，或要求找到一个满足某些限制的最优解。-通过彻底的搜索方法来解决。*彻底搜索的运算量很大，有时大到计算机承受不了的程度。*彻底的搜索，以进行大量的比较、舍弃、运算时间为代价。因此，用穷举法解某些实际问题是不现实的.-使用回溯法可以大大减少实际的搜索。例如，迷宫问题，八皇后问题，骑士周游世界问题。,引入问题,关键：找到回溯的条件。算法思想：通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索往前试探，若试探成功，就得到解，若试探失败，就逐步往回退，换别的路线再往前试探。实际上是广度与深度搜索结合的搜索，深度搜索过程中碰到条件不满足，则退回上一层，在每一层上也进行全面的搜索。,回溯法的基本思想,回溯法是带优化的穷举法。回溯法的基本思想：在一棵含有问题全部可能解的状态空间树上进行深度优先搜索，解为叶子结点。搜索过程中，每到达一个结点时，则判断该结点为根的子树是否含有问题的解，如果可以确定该子树中不含有问题的解，则放弃对该子树的搜索，退回到上层父结点，继续下一步深度优先搜索过程。在回溯法中，并不是先构造出整棵状态空间树，再进行搜索，而是在搜索过程中逐步构造出状态空间树，即边搜索，边构造。,回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。（1）如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。（2）否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,1,1,1,0,0,0,1,1,1,1,0,0,0,0,例如，对于有n种可选物品的0-1背包问题，其解空间由长度为n的0-1向量组成。以3件物品实例,扩展结点：一个正在产生儿子的结点称为扩展结点活结点：一个自身已生成但其儿子还没有全部生成的结点称做活结点死结点：一个所有儿子已经产生的结点称做死结点,从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点-活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。,深度优先的问题状态生成法：如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）宽度优先的问题状态生成法：在一个扩展结点变成死结点之前，它一直是扩展结点回溯法：为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(boundingfunction)来剔除那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。,示例10-1背包问题n=3,C=30,w=16,15,15,v=45,25,25,A,Cr=C=30，V=0,L,N,M,示例10-1背包问题,开始时，Cr=C=30，V=0，A为唯一活结点，也是当前扩展结点扩展A，先到达B结点Cr=Cr-w1=14，V=V+v1=45；此时A、B为活结点，B成为当前扩展结点；扩展B，先到达CCrw2，C导致一个不可行解，回溯到B再扩展B到达DD可行，此时A、B、D是活结点，D成为新的扩展结点；扩展D，先到达ECr45，皆得到一个可行解x=(0,1,1)，V=50I不可扩展，成为死结点，返回到H再扩展H到达JJ是叶结点，且2550，不是最优解J不可扩展，成为死结点，返回到HH没有可扩展结点，成为死结点，返回到G再扩展G到达LCr=30，V=0，活结点为A、G、L，L为当前扩展结点扩展L，先到达M，M是叶结点，且2550，不是最优解，又M不可扩展，返回到L再扩展L到达N，N是叶结点，且0n)output(x);/当搜索到叶结点，输出可行解elsefor(inti=f(n,t);in)output(x);elsefor(inti=0;in)output(x);elsefor(inti=t;i=n;i+)swap(xt,xi);if(legal(t)backtrack(t+1);swap(xt,xi);,八皇后问题,是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出。在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。,N皇后问题,问题描述在*的棋盘上，放置个皇后，要求每一横行，每一列，每一对角线上均只能放置一个皇后，求可能的方案及方案数。问题的状态即棋盘的布局状态，状态空间树的根为空棋盘，每个布局的下一步可能布局为该布局结点的子结点；任意两个王后不放在同一行或同一列或同一斜线。因此为了简化状态空间树，采用逐行布局的方式，即每个布局有n个子结点；,N皇后问题,一、回溯过程分析：1、从空棋盘起，逐行放置棋子。2、每在一个布局中放下一个棋子，即推演到一个新的布局。3、如果当前行上没有可合法放置棋子的位置，则回溯到上一行，重新布放上一行的棋子。,N皇后问题,N皇后问题,二、存储结构(1)二维数组ANN存储皇后位置若第i行第j列放有皇后,则Aij为非0值,否则值为0。(2)一维数组Mk、Lk、Rk分别表示竖列、左斜线、右斜线是否放有棋子,有则值为1,否则值为0。,k值和皇后位置坐标i，j的关联？,k=i+jk=02*(N-1),k值和皇后位置坐标i，j的关联？,k=i-jk会出现负值,k=i-j+Nk=12*(N+1),右,右,Mk（k=j）Lk（k=i+j）Rk（k=i-j+N）,三、算法描述初始化for(某一行的每个位置)if(安全)放皇后;if(已到最后一行)输出;else试探下一行;去皇后;,N皇后问题,安全算法：!Mj,#defineN4/*N为皇后个数*/intcount=0;intMN=0,L2*N=0,R2*N=0;intANN=0;/*皇后位置*/voidprint(intANN);intmytry(inti,intMN,intL2*N,intR2*N,intANN);voidmain()intn=mytry(0,M,L,R,A);/代表从0行开始试探cout“ncount=”n;/n可行解数目,/*试探每一行皇后的位置*/intmytry(inti,intMN,intL2*N,intR2*N,intANN)for(intj=0;jN;j+)/放置在i行j列if(!Mj,voidprint(intANN)/*输出*/inti,j;for(i=0;iN;i+)for(j=0;jN;j+)coutAij;coutendl;,图的m着色问题,给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。这个问题是图的m可着色判定问题。若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数m为该图的色数。求一个图的色数m的问题称为图的m可着色优化问题。,把n个板块抽象为一个图的n个顶点,图的着色问题是由地图的着色问题引申而来的，用m种颜色为地图着色，使得地图上的每一个区域着一种颜色，且相邻区域颜色不同。,一、产生背景,二、问题描述,给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。是否有一种着色法使G中每条边的2个顶点着不同颜色。如果有则称这个图是m可着色，否则称这个图不是m可着色。若一个图最少需要k种颜色才能使图中每条边连接的2个顶点着不同颜色，则称这个数k为该图的色数。,三、算法设计,输入：颜色种类m输出：如果这个图不是m可着色，给出否定回答；如果这个图是m可着色的，找出所有不同的着色法。,1,4,2,3,可以用以下邻接矩阵来表示,1111011111111101111101011,邻接矩阵中通常用二维数组来存放边之间的关系，用一维数组来存放顶点的信息。所以在接下来的求解问题中我们将用到二维数组a来存放两边是否相邻，用一维数组x来存放每个顶点的颜色;xi=j表示第i个节点图第j中颜色。,5,我们可以把问题简化为3个点来分析，现给定如下图，怎样求解呢？,1,2,3,该图的色数是多少？怎样用解空间树来表示呢？,由图可知，对于每一个顶点可选的颜色可以有3种不同的选择，所以每一个节点有3个儿子节点，有4层。,判断条件是什么？,新加入的节点t取某一种颜色i时，依次和上层的每一个节点j(jt)比较。如果atj=1并且xt=xj=i,那么它是不可着色的。,intOK(intt)intj;for(j=1;jt;j+)if(atj=1,模拟演示,t=1,t=2,t=3,t=4,voidBacktrace(intt，intm),当前节点,颜色的种类,当搜索的当前节点tN），即可输出一种方案,for(i=1;iN)sum+;printf(第%d种方案：n,sum);for(i=1;i=N;i+)printf(%d,xi);,四、程序代码,#include#include#defineN3/图中节点的个数intaN+1N+1=0,0,0,0,0,1,1,1,0,1,1,1,0,1,1,1,;/邻接矩阵intxN+1;/记录颜色intsum=0;/保存可以着色的方案数intOK(intt,inti)/判断函数intj;for(j=1;jN)/算法搜索至叶子节点sum+;printf(第%d种方案：n,sum);for(i=1;i=N;i+)printf(%d,xi);printf(n);elsefor(i=1;in)/*n:顶点数*/sum+;输出xi；elsefor(inti=1;i=m;i+)xt=i;/*设置颜色*/if(ok(t)backtrack(t+1);intColor:ok(intk)/*检查颜色可用性*/for(intj=1;j=n;j+)if(akj=1),图的m着色问题,复杂度分析图m可着色问题的解空间树中内结点个数是对于每一个内结点，在最坏情况下，用ok检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。因此，回溯法总的时间耗费是,考场安排图的着色原理之运用,【问题描述】设学校共有n门课，需要进行期末考试，因为不少学生不止选修一门课程，所以不能把同一个学生选修的两门课程安排在同一场次进行考试，问学期的期末考试最少需多少场次考完？【问题分析】本问题可转换成是对一平面图的顶点着色问题判定，采用回溯法求解。将所选的每门课程变成一个结点，若一个同学选了m(1mn)门课程时，则这m门课程所对应的结点互相用一条边连接起来。则相邻边的顶点不能着同一种颜色，既不能安排在同一场次考试。但本题又不同于m-着色问题，而是要求最少场次考完，故本问题是求min-着色问题，既所有的顶点最少可用多少种颜色来着色，则本问题可解。,【数据结构】图的邻接矩阵testMAXMAX来表示一个图G，其中若（i，j）是G的一条边，则testij=testji=1，否则testij=testji=0，因为本问题只关心一条边是否存在，所以用邻接矩阵。颜色总数用总课程数目N表示。生成解则用数组valueMAX来记录，其中valuei是结点i的颜色，即课程i可安排在第valuei场考试，resultMAX用来记录最优解。程序中N表示课程总数，minSum表示最少的考试场次。,【主要算法】testArrange()/找一个图的考试方案if(k=N)if(jminSum)/记录最少的考试场数minSum=j;for(t=1;t=N;t+)resultt=valuet;/记录最优解elsetestArrange(k+1);/递归调用,回溯法求解0-1背包问题,解空间：子集树可行性约束函数：,解题的基本指导思想:按贪心法的思路，优先装入价值/重量比大的物品。当剩余容量装不下最后考虑的物品时，再用回溯法修改先前的装入方案，直到得到全局最优解为止。,/*数据结构*/#defineN5/物品数目intv=6,3,6,5,4,w=2,2,4,6,5;intC=10;/背包容量intcp;/当前价值intbestp=0;/最优价值intxN;/当前解intbestxN;/*当前最优解*/,voidmain()/按物品价值重量比排降序/输出物品初始价值、重量（略）knap(0);cout最优价值:bestpt;cout此时放入背包物品:;for(j=0;jN;j+)if(bestxj=1)coutj+1;cout=N)if(bestpcp)bestp=cp;/保存最优解for(intj=0;jN;j+)bestxj=xj;putout();elseif(wt=C)/搜索左枝xt=1;cp+=vt;C-=wt;knap(t+1);/继续向下深度搜索xt=0;C+=wt;cp-=vt;/回退xt=0;/搜索右枝knap(t+1);,/*输出*/voidputout()cout物品放入背包状态为：;for(inti=0;iN;i+)coutsetw(5)xi;cout获得的价值=cp;coutendl;,实际搜索解空间树策略:只要其左儿子结点是一个可行结点，搜索就进入其左子树。约束函数当右子树有可能包含最优解时才进入右子树搜索，否则将右子树剪去。限界函数,前面算法完全搜索解空间树:即用约束条件确定是否搜索其左子树；对右子树没有任何判断，一定进入右子树搜索。-耗时,剪枝方法：r:当前剩余物品价值总和；cv:当前获得价值；bestp:当前最优价值。当cv+r=bestp时，可剪去右子树。计算右子树上界方法:将剩余物品依其单位重量价值排序，然后依次装入物品，直至装不下时，再装入该物品的一部分而装满背包。由此得到的价值是右子树中解的上界。,intBound(inti)/计算当前结点处上界intleft=C-cw;/剩余容量intb=cv;/cv当前价值while(wiN)/*到叶结点*/for(j=1;jbestv)/*搜索右子树*/xi=0;Backtrack(i+1);,voidputout()cout放入背包的物品是:;cw=0;for(inti=1;i=N;i+)if(bestxi=1)coutit;cw+=wi;coutendl放入背包物品总重为：cwt;cout最大价值和为:bestvn)for(intj=1;jf1)?f2i-1:f1)+Mxj2;f+=f2i;if(fbestf)Swap(xi,xj);Backtrack(i+1);Swap(xi,xj);f1-=Mxj1;f-=f2i;,int*M,/各作业所需的处理时间*x,/当前作业调度*bestx,/当前最优作业调度*f2,/机器2完成处理时间f1,/机器1完成处理时间f,/完成时间和bestf,/当前最优值n;/作业数,连续邮资问题,【问题描述】假设国家发行了N种不同面值的邮票，并且规定每张信封上最多只允许贴M张邮票。连续邮资问题要求对于给定的N和M的值，给出邮票面值的最佳设计，在1张信封上可贴出从邮资1开始，增量为1的最大连续邮资区间。,例如，当N=5和M=4时，面值为(1,3,11,15,32)的5种邮票可以贴出邮资的最大连续邮资区间是1到70。,x1：N：表示N种不同的邮票面值，并约定它们从小到大排列。x1=1是惟一的选择。（1）在未确定剩余其它N1种邮票面值的情况下，只用x1一种邮票面值，所能得到的最大连续邮资区间是1：M。（2）确定x2的取值范围x2的值最小可以取到2，最大可以取到M+1。（3）一般的情况下，若已选定x1到xi-1，最大连续邮资区间是1：r时，接下来xi的可取值范围是xi-1+1：r+1。,连续邮资问题,若x1到xi-1，最大连续邮资区间是1：r时，接下来xi的可取值范围是xi-1+1：r+1。例如，当N=3和M=2时,【解决方案及基本思想】,（1）基本思路：搜索所有可行解，当i=N时，当前结点Z是解空间中的内部结点。在该结点处x1:i-1能贴出最大连续区间为r。因此，在结点Z