第5章-回溯法教案资料.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,算法设计与分析n)output(x);,else,for(int j=f(n,i);j0),if(f(n,i)=g(n,i),for(int j=f(n,i);jn)output(x);,else,for(int j=i;j25,30,6,4,35,40,11,26,14,24,55,60,21,36,19,29,算法设计,参考程序,Travle.cpp,例3：TSP问题,应用专题二,组合问题中的回溯法,子集树的算法框架,例1：,子集问题,例2：,01背包问题,例3：,符号三角形问题,子集树的算法框架,遍历子集树需O(2,n,)计算时间,void backtrack(int i),if(in)output(x);,else,for(int j=0;j n),for(int j=1;j=n;j+),bestxj=xj;,bestf=f;,else,for(int j=i;j f1)?f2i-1:f1)+Mxj2;,f+=f2i;,if(f bestf),Swap(xi,xj);,Backtrack(i+1);,Swap(xi,xj);,f1-=Mxj1;,f-=f2i;,例2：工作安排问题,问题描述,设有n项工作要安排给n个人去完成。让第i个人去完成第j项工作产生的效益为a,ij,。试设计一个算法，为每个人安排一件不同的工作，并使总效益最大。,例如：,例2：工作安排问题,分析：,思路：,每个人选择n项工作中的一项，在各种选择的组合中，找到效益最大的一种组合输出。,解向量,x,=(,x,1,x,2,x,n,),解空间：,排列树空间,参考程序,例3：整数的划分问题,问题提出：,将一个正整数n表示成形如下式的一系列正整数的和，称为n的一个划分。,nn,1,n,2,n,k,(n,i,1,i1,2,k,k1,且nn,1,n,2,n,k,1,例3：整数的划分问题,例如：,整数6的分划数有11种:,6；,5+1；,4+2，4+1+1；,3+3，3+2+1，3+1+1+1；,2+2+2，2+2+1+1，2+1+1+1+1；,1+1+1+1+1+1;,分析,解向量,x,=(,x,1,x,2,x,n,),约束条件,显约束：1,x,i,n,隐约束：,nx,1,x,2,x,k,(x,i,1,i1,2,k,k1),nx,1,x,2,x,k,1,问题的解空间,参考程序,例3：整数的划分问题,例4：棋盘覆盖问题,问题描述：,在一个nn个方格组成的棋盘中，要用图示的4种不同形态的L型骨牌覆盖给定的棋盘上的所有方格，且任何2个L型骨牌不得重叠覆盖。（必要时，需要挖掉1块）,例如：,5,5,4,4,5,3,3,4,2,3,1,1,2,2,1,12,11,11,10,9,9,12,12,11,10,10,9,8,7,7,6,5,5,8,8,7,6,6,5,4,3,3,2,1,1,4,4,3,2,2,1,例4：棋盘覆盖问题,例4：棋盘覆盖问题,考虑几个问题,L型骨牌的表示方式,约束条件,求解过程,参考程序：,例5：八数码难题,问题描述：,求解过程示意图：,程序实现：,(a),5,7,4,6,1,3,8,2,(b),5,6,7,4,8,3,2,1,例6：迷宫问题,问题描述,问题分析,过程演示,算法设计,例7：马踏棋盘问题,问题描述,在n x n棋盘（有n x n个格点的棋盘）的某个格点上有一个中国象棋马，马走日字。求一条周游棋盘的路径，使得马能够从起始位置起沿着该路径每个格点恰好走一次最后回到出发位置。,分析：,输入：n (棋盘规格),输出：周游路线,算法：回溯+贪心,例如：66,1,32,29,18,7,10,30,17,36,9,28,19,33,2,31,6,11,8,16,23,14,35,20,27,3,34,25,22,5,12,24,15,4,13,26,21,例如：1616,1,18,237,240,255,12,235,232,75,58,31,28,77,64,33,36,238,241,256,19,236,233,254,13,30,27,76,57,32,35,78,63,17,2,239,8,11,20,231,234,59,74,29,68,65,56,37,34,242,7,16,221,22,9,14,253,26,69,60,47,54,67,62,79,3,222,219,10,15,228,21,230,73,46,49,66,61,40,55,38,6,243,4,247,220,23,252,227,70,25,72,85,48,53,80,41,223,248,245,218,225,250,229,24,45,84,87,50,43,82,39,52,244,5,224,249,246,217,226,251,88,71,44,83,86,51,42,81,191,174,211,208,193,180,213,216,133,116,89,150,135,122,91,94,210,207,192,173,212,215,194,179,152,149,134,115,90,93,136,121,175,190,209,184,181,172,153,214,117,132,151,126,123,114,95,92,206,185,176,163,170,183,178,195,148,127,118,105,112,125,120,137,189,162,165,182,177,156,171,154,131,104,107,124,119,98,113,96,186,205,188,201,164,169,196,157,128,147,130,143,106,111,138,99,161,200,203,166,159,198,155,168,103,142,145,108,101,140,97,110,204,187,160,199,202,167,158,197,146,129,102,141,144,109,100,139,5.3 回溯法效率分析,影响回溯法效率的几个因素：,生成结点所花费的时间；,计算约束条件所花费的时间；,计算目标函数的界所花费的时间；,所生成的结点个数。,解向量中分量排列顺序的影响,重排原理,解向量中分量的取值范围不同时，在解向量中的不同排列顺序，其对应的状态空间树的结构也不同。,在其他条件相当的前提下，让可取值最少的,x,i,。,例如：,从下图中关于同一问题的,2,棵不同解空间树，可以体会到这种策略的潜力。,5.3 回溯法效率分析,解空间,：,(,x,1,x,2,x,3,)|,x,i,s,i,i=1,2,3,|s,1,|=3,|s,2,|=4,|s,3,|=2,解空间树1：,对应于,(,x,1,x,2,x,3,)|,的状态空间树如图 所示，第一层三棵子树各对应8个可能解，剪去其中一棵子树，只减少8个可能解。,5.3 回溯法效率分析,5.3 回溯法效率分析,解空间树2：,对应于,(,x,3,x,1,x,2,)|,的状态空间树如图 所示，第一层二棵子树各对应12个可能解，剪去其中一棵子树，只减少12个可能解。,本章小结,本章小结,回溯法的设计思想,解空间及解空间的搜索策略,回溯法求解的典型用例,此课件下载可自行编辑修改，仅供参考！感谢您的支持，我们努力做得更好！谢谢,