05 回溯法.ppt

《05 回溯法.ppt》由会员分享，可在线阅读，更多相关《05 回溯法.ppt（64页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、段旭良四川农业大学本章主要内容n5.1 回溯法算法框架n5.2 装载问题n5.3 批处理作业调度n5.4 符号三角形问题n5.5 n后问题n5.6 0-1背包问题n5.8 图的m着色问题n5.9 旅行售货员问题段旭良四川农业大学引言n理论上n寻找问题的解的一种可靠的方法是首先列出所有候选解，然后依次检查每一个，在检查完所有或部分候选解后，即可找到所需要的解。n但是n当候选解数量有限并且通过检查所有或部分候选解能够得到所需解时，上述方法是可行的。n若候选解的数量非常大（指数级，大数阶乘），即便采用最快的计算机也只能解决规模很小的问题。段旭良四川农业大学引言n于是n回溯和分枝定界法是比较常用的对候

2、选解进行系统检查两种方法。n按照这两种方法对候选解进行系统检查通常会使问题的求解时间大大减少（无论对于最坏情形还是对于一般情形）。n可以避免对很大的候选解集合进行检查，同时能够保证算法运行结束时可以找到所需要的解。n通常能够用来求解规模很大的问题。段旭良四川农业大学引言n回溯法n基本做法是搜索，或是一种组织得井井有条的、能避免不必要搜索的穷举式搜索法。n回溯法在问题的解空间树中，按深度优先深度优先策略，从根结点出发搜索解空间树。n算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解n如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；n否则，进入该子树，继续按深度优先

3、策略搜索。段旭良四川农业大学5.1回溯法的算法框架n5.1.1 问题的解空间n问题的解向量n回溯法希望一个问题的解能够表示成一个n元式(x1,x2,xn)的形式。n显约束n对分量xi的取值限定。n隐约束n为满足问题的解而对不同分量之间施加的约束。段旭良四川农业大学5.1回溯法的算法框架n解空间（Solution Space）n对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。n回溯法解问题时，首先应明确定义问题的解空间。解空间应至少包含问题的一个（最优）解。n同一问题可有多种表示，有些表示更简单，所需状态空间更小（存储量少，搜索方法简单）。段旭良四川农业大学5.

4、1回溯法的算法框架n例如n对于有n种可选物品的0-1背包问题，其解空间由2n个长度为n的0-1向量组成。nn=3时，解空间为(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)n用完全二叉树表示的解空间n边上的数字给出了向量x中第i个分量的值xi；n根节点A到叶节点H的路径定义了解 x=1,1,1。n根据w和c的值，从根到叶的路径中的部分或全部解可能是不可行的。段旭良四川农业大学5.1回溯法的算法框架段旭良四川农业大学5.1回溯法的算法框架n5.1.2 回溯法的基本思想n回溯法的基本步骤n(1)针对所给问题，定义问题的解

5、空间；n(2)确定易于搜索的解空间结构；n(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。n常用剪枝函数n用约束函数在扩展结点处剪去不满足约束的子树；n用限界函数剪去得不到最优解的子树。段旭良四川农业大学5.1回溯法的算法框架n复杂性n用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。在任何时刻，算法只保存从根结点到当前扩展结点的路径。n如果解空间树中从根结点到叶结点的最长路径的长度为h(n)，则回溯法所需的计算空间通常为O(h(n)。n显式地存储整个解空间则需要O(2h(n)或O(h(n)!)内存空间。段旭良四川农业大学5.1回溯法的算法框架n生成问题状态的

6、基本方法n扩展结点（E-结点,ExpansionNode）n一个正在产生儿子的结点称为扩展结点n活结点（L-结点,LiveNode）n一个自身已生成但其儿子还没有全部生成的节点称做活结点n死结点（D-结点,DeadNode）n一个所有儿子已经产生的结点称做死结点段旭良四川农业大学5.1回溯法的算法框架n深度优先的问题状态生成法n如果对一个扩展结点R，一旦产生了它的一个儿子C，就把C当做新的扩展结点。n在完成对子树C（以C为根的子树）的穷尽搜索之后，将R重新变成扩展结点，继续生成R的下一个儿子（如果存在）。n宽度优先的问题状态生成法n一个扩展结点变成死结点之前，它一直是扩展结点。段旭良四川农业大

7、学5.1回溯法的算法框架n回溯法n为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(Bounding Function)来处死那些实际上不可能产生所需解的活结点，以减少问题的计算量。n具有限界函数的深度优先生成法称为回溯法。段旭良四川农业大学5.1回溯法的算法框架n0-1背包问题nn=3,C=30,w=16,15,15,v=45,25,25n开始时，nCr=C=30，V=0nC为容量，Cr为剩余空间，V为价值。nA为唯一活结点，也是当前扩展结点。段旭良四川农业大学5.1回溯法的算法框架nn=3,C=30,w=16,15,15,v=45,25,25ACr=C=30,V=0Bw1=

8、16,v1=45Cr=14,V=45扩展A，先到达B结点Cr=Cr-w1=14，V=V+v1=45此时A、B为活结点B成为当前扩展结点扩展B，先到达DCrw2D导致一个不可行解回溯到BDCrw2不可行解不可行解HI段旭良四川农业大学5.1回溯法的算法框架nn=3,C=30,w=16,15,15,v=45,25,25ACr=C=30,V=0Bw1=16,v1=45Cr=14,V=45DCrw2不可行解不可行解JCrw3不可行解不可行解KCr=14V=45x=(1,0,0)HIECr=14V=45再扩展B到达EE可行，此时A,B,E是活结点E成为新的扩展结点扩展E，先到达JCrw3，J不可行解回溯

9、到E扩展E到达KK是叶结点，得到一个可行解x=(1,0,0)，V=45K不可扩展，死结点，返回到EE成为死结点，返回到BB成为死结点，返回到A段旭良四川农业大学5.1回溯法的算法框架nn=3,C=30,w=16,15,15,v=45,25,25ACr=C=30,V=0Bw1=16,v1=45Cr=14,V=45CCr=30,V=0DCrw2不可行解不可行解JCr45x=(0,1,1)Fw2=15,v2=25Cr=15,V=25A再次成为扩展结点扩展A到达CCr=30，V=0，活结点为A、CC为当前扩展结点扩展C，先到达FCr=Cr-w2=15V=V+v2=25此时活结点为A,C,FF成为当前扩

10、展结点扩展F，先到达LCr=Cr-w3=0V=V+v3=50L是叶结点，且5045得到一个可行解x=(0,1,1)，V=50L不可扩展，死结点返回F段旭良四川农业大学5.1回溯法的算法框架nn=3,C=30,w=16,15,15,v=45,25,25ACr=C=30,V=0Bw1=16,v1=45Cr=14,V=45CCr=30,V=0DCrw2不可行解不可行解JCr45x=(0,1,1)Fw2=15,v2=25Cr=15,V=25再扩展F到达MM是叶结点，且2550不是最优解M不可扩展，成为死结点返回到F，F没有可扩展结点，成为死结点返回到C，再扩展C到达GM2550不是最不是最优解优解G段

11、旭良四川农业大学5.1回溯法的算法框架n扩展到G以后nCr=30，V=0，活结点为A、C、G，G为当前扩展结点n扩展G，先到达N，N是叶结点，且2550，不是最优解，又N不可扩展，返回到Gn再扩展G到达O，O是叶结点，且0n)output(x);elsefor(inti=f(n,t);i0)if(f(n,t)=g(n,t)for(inti=f(n,t);ic1，则以O为根的子树不能产生一个可行解答。可将这个测试作为限界函数。n当且仅当一个节点的cw值大于c1 时，定义它是不可行的。段旭良四川农业大学5.2装载问题n假定n=4，w=8,6,2,3，c1=12。n解空间树为ABCDEFGNOLMH

12、IJKZBXYWVTURSPQDEAC11110000X=0,0,0,0cw=0c1X=1,0,0,0cw=8c1X=1,0,0,0cw=8c1X=1,0,1,0cw=10c1X=1,0,1,0cw=10c1X=1,0,0,0cw=8c1段旭良四川农业大学5.2装载问题n假定n=4，w=8,6,2,3，c1=12。n解空间树为ABCDEFGNOLMHIJKZBXYWVTURSPQDEAC11110000X=0,0,0,0cw=0c1X=1,0,0,0cw=8c1X=1,0,0,0cw=8c1X=1,0,1,0cw=10c113X=1,0,0,1cw=11c1X=1,0,0,0cw=8c1108

13、段旭良四川农业大学5.2装载问题n假定n=4，w=8,6,2,3，c1=12。n解空间树为ABCDEFGNOLMHIJKZBXYWVTURSPQDEAC11110000X=0,0,0,0cw=0c11310118X=0,0,0,0cw=0c1X=0,1,0,0cw=6c1X=0,1,1,0cw=8c1X=0,1,1,1cw=11half)|(t*(t-1)/2-counthalf)return;if(tn)sum+;elsefor(inti=0;i2;i+)p1t=i;count+=i;for(intj=2;j=t;j+)pjt-j+1=pj-1t-j+1pj-1t-j+2;count+=pj

14、t-j+1;Backtrack(t+1);for(intj=2;j=t;j+)count-=pjt-j+1;count-=i;段旭良四川农业大学5.5n后问题n5.5.1 问题描述n在nn棋盘上放彼此不受攻击的n个皇后。n按国际象棋规则，皇后可攻击同行、同列、同一斜线的棋子。n等价于在nn格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。1Q2Q3Q4Q5Q6Q7Q8Q12345678段旭良四川农业大学5.5n后问题n5.5.2 问题分析n解向量n解向量：(x1,x2,xn)nxi表示皇后i放在第i行的xi列nX=(4,6,8,2,7,1,3,5)n显约束nxi=1,2,n

15、n隐约束n不同列：xixjn不处于同一正、反对角线：|i-j|xi-xj|1Q2Q3Q4Q5Q6Q7Q8Q12345678段旭良四川农业大学5.5n后问题n例：4后问题的解空间树12111241231471323413458610242313 44342932344314431516331341241232 41 41 22313124342434243421Q2Q3Q4Q1234段旭良四川农业大学5.5n后问题n5.5.3 算法描述boolQueen:Place(intk)for(intj=1;jn)sum+;elsefor(inti=1;i=n;i+)xt=i;if(Place(t)Bac

16、ktrack(t+1);段旭良四川农业大学5.60-1背包问题n解空间n子集树n可行性约束函数nwixiCn上界函数nBound()Bound(inti)/计算上界计算上界intcleft=c-cw;/剩余容量剩余容量intb=cp;/以物品单位重量价值递减序装入以物品单位重量价值递减序装入while(i=n&wi=cleft)cleft-=wi;b+=pi;i+;/装满背包装满背包if(in)sum+;for(inti=1;i=n;i+)coutxi;coutendl;elsefor(inti=1;i=m;i+)xt=i;if(Ok(t)Backtrack(t+1);boolColor:Ok

17、(intk)/检查颜色可用性检查颜色可用性for(intj=1;j=n;j+)if(akj=1)&(xj=xk)returnfalse;returntrue;段旭良四川农业大学5.8图的m着色问题n5.8.4 复杂性分析n图m可着色问题的解空间树中内结点个数：nmi(0in-1)。n对于每一个内结点，在最坏情况下，检查当前扩展结点的每一个儿子所相应的颜色可用性需耗时O(mn)。n因此，回溯法总的时间耗费是nmi(mn)=nm(mn-1)/(m-1)=O(nmn)(0in-1)段旭良四川农业大学5.9旅行售货员问题n曾记否？前面已经说过了。n解空间n排列树n复杂度分析n算法backtrack在最

18、坏情况下可能需要更新当前最优解O(n-1)!)次，每次更新bestx需计算时间O(n)。n整个算法的计算时间复杂性为O(n!)。段旭良四川农业大学5.10圆排列问题n5.10.1 问题描述n给定n个大小不等的圆c1,c2,cn，要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。n圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。n例如，当n=3，且所给的3个圆的半径分别为1,1,2时，这3个圆的最小长度的圆排列如图所示。其最小长度为2+42。段旭良四川农业大学回溯法效率分析n回溯算法效率在很大程度上依赖于以下因素n(1)产生xk的时间；n(2)满足显约束的xk值的个数；n(3

19、)计算约束函数constraint的时间；n(4)计算上界函数bound的时间；n(5)满足约束函数和上界函数的所有xk的个数。n约束n好的约束函数能显著地减少所生成的结点数，但往往计算量较大。因此，在选择约束函数时通常存在生成结点数与约束函数计算量之间的折衷。段旭良四川农业大学回溯法效率分析n重排原理n对于许多问题而言，在搜索试探时选取xi的值顺序是任意的。在其他条件相当的前提下，让可取值最少的xi优先。n从图中关于同一问题的2棵不同解空间树，可以体会到这种策略的潜力。段旭良四川农业大学回溯法效率分析n从第1层剪去1棵子树，则从所有应当考虑的3元组中一次消去12个3元组。n从第1层剪去1棵子树，却只消去8个3元组。n前者的效果明显比后者好。段旭良四川农业大学没有了