第六章分支界限法PPT讲稿.ppt

第六章分支界限法2023/1/25计算机算法设计与分析1第1页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析2分支限界法是最佳优先搜索法n分支限界法就是最佳优先(包括广度优先在内)的搜索法。n分支限界法将要搜索的结点按评价函数的优劣排序，让好的结点优先搜索，将坏的结点剪去。所以准确说，此方法应称为界限剪支法。n分支限界法中有两个要点：n(1)评价函数的构造；评价函数的构造；n(2)搜索路径的构造。搜索路径的构造。第2页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析3评价函数的构造n评价函数要能够提供一个评定候选扩展结点的方法，以便确定哪个结点最有可能在通往目标的最佳路径上。n一个评价函数f(d)通常可以由两个部分构成：从开始结点到结点d的已有耗损值g(d)，和再从结点d到达目标的期望耗损值h(d)。即：f(d)=g(d)+h(d)n通常g(d)的构造较易，h(d)的构造较难。第3页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析4搜索路径的构造n在回溯法中，每次仅考察一条路径，因而只需要构造这一条路径即可：前进时记下相应结点，回溯时删去最末尾结点的记录。这比较容易实现。n在分支限界法中，是同时考察若干条路径，那么又该如何构造搜索的路径呢？n对每一个扩展的结点，建立三个信息：n(1)该结点的名称；n(2)它的评价函数值；n(3)指向其前驱的指针；n这样一旦找到目标，即可逆向构造其路径。n用一个表保存准备扩展的结点，称为Open表。n用一个表保存已搜索过的结点，称为Closed表。第4页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析5分支限界法的一般算法n计算初始结点s的f(s);s,f(s),nil放入Open;nwhile(Open)n 从Open中取出p,f(p),x(f(p)为最小);n 将p,f(p),x放入Closed;n 若p是目标，则成功返回；否则n 产生p的后继d并计算f(d)；对每个后继d有二种情况：dClosed|d Open；dOpen&dClosed。n 若(d,f(d),pClosed|d,f(d),pOpen)&f(d)f(d)，则删去旧结点并将d,f(d),p 重新插入到Open中;否则n 将d,f(d),p 插入到Open中。第5页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析6分支限界法求单源最短路径n单源最短路径问题的评价函数的构造：ng(d)定义为从源s到结点d所走的路径长度：g(d)=g(p)+Cpd这里p为d的前驱结点，Cpd为p到d的距离。nh(d)定义为0。于是f(d)=g(d)。n源s的评价函数f(s)=0。n评价函数的下界为0；上界初始时为，以后不断用取得的更短路径的长度来替代。第6页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析7分支限界法求最短路径举例12543102050100301060赋权图G初始时，将源1,0,0放入Open，Closed为空。Open表1,0,0Closed表取出1,0,0放入Closed；生成其后继2,10,1、4,30,1和5,100,1，并依序放入Open。1,0,05,100,14,30,12,10,1取出2,10,1放入Closed；生成其后继3,60,2，并依序插入Open。2,10,13,60,24,30,1取出4,30,1放入Closed；生成其后继3,50,4和5,90,4，修订Open中已有的两个结点并依序排列。4,30,15,90,43,50,4取出3,50,4放入Closed；生成其后继2,100,3和5,60,3，前者因劣于Closed中的2,10,1而被抛弃，后者修订了Open中的5,90,4。3,50,45,60,3取出5,60,3，因其已经是目标结点，算法成功并终止。依据逆向指针可得最短路径为1435。第7页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析8界限(Bounding)n评价函数f(d)关系着算法的效率乃至成败。n因为在大多数问题中f(d)只是个估计值，所以单靠f(d)是不够的。通常还要设计它的上下界函数U(d)和L(d)。L(d)f(d)U(d)。n所谓分支限界法就是通过评价函数及其上下界函数的计算，将状态空间中不可能产生最佳解的子树剪去，减少搜索的范围，提高效率。因而更准确的称呼应是“界限剪支法”第8页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析9用分支限界法求TSPnTSP是求排列的问题，不是仅找一条路径而已。因而需要对分支限界法的一般算法作些修改：n(1)待扩展的结点如果在本路径上已经出现，则不再扩展，但若是在其他路径上出现过，则仍需要扩展。n(2)新结点，无论其优劣，既不影响其它路径上的结点，也不受其它路径上的结点的影响。n(3)依据上界函数决定结点是否可以剪去。第9页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析10分支限界法求排列n计算初始结点s的f(s);s,f(s),nil放入Open;nwhile(Open)n 从Open中取出p,f(p),L;/L是路径已有结点n 若f(p)U，则抛弃该路径；n 若p是目标，则考虑修改上界函数值；否则n 将p,f(p),L放入Closed;n 在该路径上扩展结点p；对每个后继dn 计算f(d)；n 若f(d)U,则L=L p;n 将d,f(d),L依序放入Open。n 第10页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析11分支限界法求TSP举例n设有向图G=(V,E)的边的代价矩阵为C=cij。若不存在有向边E，则定义cij=且规定cii=。不失一般性，设周游路线均以顶点1为起点。左下为一个有向图G的代价矩阵C。25 40 31 27 5 17 30 2519 15 6 1 9 50 24 622 8 7 10 n评价函数f(d)为1到d的代价减去已经过的边数。n初始时f(1)=0;nf(d)=f(p)+cpd 1，这里p是d的前驱。第11页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析12分支限界法求TSP的搜索 25 40 31 27 5 17 30 2519 15 6 1 9 50 24 622 8 7 10 102243394305262340453548523333243542793535453246437234946242843584286找到了第一条周游路线153421，其长度为95。这不是最短周游路线，需要修改上界后继续搜索。第12页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析13归约矩阵以及约数n前面的搜索的效率不高，几乎要搜索全部的状态空间。其原因是评价函数以及上下界的估计太低。为了设计求解TSP问题的更好的评价函数，先定义其代价矩阵的归约矩阵和约数。n给定代价矩阵C，从C的任何行i(或列i)的各元素中减去此行(或此列)的最小元素的值r(i)(或r(i)，称为对i行(或i列)的归约。将C的各行和各列都归约后的矩阵称为C的归约矩阵。和数r=in r(i)+in r(i)称为C的约数。第13页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析14例子中的归约矩阵和约数n计算前面例子中的归约矩阵及其约数如下：25 40 31 27 5 17 30 2519 15 6 1 9 50 24 622 8 7 10 先做行归约：r(1)=25 0 15 6 2r(2)=5 0 12 25 20r(3)=118 14 5 0r(4)=6 3 44 21 0r(5)=715 1 0 3 再做列归约：r(1)=r(2)=r(3)=r(5)=0 r(4)=33222 0n约数 r=47。第14页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析15约数是周游路线长度的下界n定理：设C是图G的代价矩阵，P是周游路线，则P的代价，即P cij=r+P cij，式中C=cij是C的归约矩阵，r为约数。n证明：由归约矩阵的构造可知：cij=cij r(i)r(j)即cij=cij+r(i)+r(j)。n 任何周游路线包含n条边并且对应在C中的每行每列有且仅有一条边。于是P cij=P(cij+r(i)+r(j)。r+P cij。第15页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析16定义期望函数h(d)n对开始结点1，令g(1)=0，h(1)=r，f(1)=r。n若从结点1选择了一条边，不妨设边，则令g(2)=f(1)+从1到2的距离l，显然l应该是c12，而不应该再是c12了。n那么h(2)=？n自然可以想到h(2)可以是从2开始的路线的下界r2。是否也可用类似求r一样去求新的约数r2呢？n可以，但在此之前应将边和所有边和边都删去，即置c12、c1k和ck2为。n设Cp为某路线上结点p的归约矩阵。从p选择边所得到结点d的归约矩阵Cd和约数rd为：n(1)将Cp中的cpd，cpk和ckd置为，1kn；n(2)依照求归约矩阵C的方法对Cp进行行归约和列归约，便得到了Cd和rd。n令f(1)=g(1)+h(1)，其中g(1)=0，h(1)=r。n对任意路线上的结点d，设p是其前驱结点，则f(d)=g(d)+h(d)，其中，g(d)=f(p)+Cppd，h(d)=rd。第16页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析17用新的评价函数求TSPn下面用新的评价函数求前面的例子，我们已经求得了它的归约矩阵C和约数r=47。0 15 3 2 0 12 22 2018 14 2 0 3 44 18 015 1 0 0 1472g(2)=47+0=470 10801512h(2)=12+3=15f(2)=47+15=62623 0 15 3 2 0 12 22 2018 14 2 0 3 44 18 015 1 0 0 g(3)=47+15=62 04313h(3)=1f(3)=63634类似地可求出 f(4)=51。515类似地可求出 f(5)=50。50下面优先扩展的是结点5。2此时C2是在C5的基础上进行。右边就是C5。0 12 22 18 14 2 3 44 18 0 0 0 g(2)=50+0=5001601503h(2)=17f(2)=67673类似地计算出f(3)=68684类似地计算出f(4)=8181下面扩展f(4)=51的结点4。并用同样方法计算它们的评价函数值。2121369464154 下面要扩展的结点 是f(2)=62的结点2。右边是其对应的归 约矩阵C2。2 0 10 815 2 0 0 18 012 0 0 3g(3)=62+0=62；对C2进行归约，得h(3)=0；于是f(3)=62。62对结点2的另外两个儿子进行同样的计算，得：f(4)=84，f(5)=72。484572下面对f(3)=62的结点3进行扩展。它有两个后继结点。345对结点4，g(4)=62+2=64。0h(4)=12，于是f(4)=64+12=7676对结点5，g(5)=62+0=62。15 2 0 0 012 0 h(5)=0，于是f(5)=62+0=6262对结点5(f(5)=62)再进行扩展。54g(4)=62+0=62，h(4)=0，f(4)=62。62结点4是目标结点，找到了第一条路线。4这条路线的长度为62，以其为上界。其余未扩展的结点的评价函数值均超过上界，因而不再需要扩展了。于是找到了一条最短的周游路线：123541。第17页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析18分支边与二叉树n在构造求TSP的搜索树时，还有另外一种算法稍有点不同，就是将搜索树构造成二叉树。n给定一条最短周游路线P，对于任一条边只有两种情况，即P或者P。n这就可以表示成右边的二叉树：kmn_n其中_表示P。n这样的边称为分支边。第18页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析19用二叉树求TSP1250 _3622453 _5684664 _7653862 _9748 1062 _ 117010 1262 _ 136612 1462 _ 156614 1662 _ 17结点16给出了一条最短周游路线：123541第19页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析20分支限界法的效率n从TSP问题的计算可看出，分支限界法搜索的状态空间为O(2n)。n对每个结点的计算时间为O(n2)。n因此在最坏情况下，分支限界法计算TSP的时间复杂性为O(n22n)。n显然，用分支限界法计算TSP的空间复杂性为O(n22n)。因为对每个结点需要n2的空间。第20页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析21对评价函数的讨论n分支限界法总耗时为O(n22n)，它与回溯法、动态规划法等在时间复杂性上没有本质的区别。n然而，如果评价函数选择得好，采用分支限界法可能有一个小得多的常数因子。n好的评价函数应该有一个尽可能高的下界估计和一个尽可能低的上界估计，从而使得搜索空间能够得到有效的压缩，从而提高效率。n在理论上可以证明好的评价函数所搜索的结点不会多于坏的评价函数所搜索的结点。第21页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析22关系、传递闭包与搜索n定义在集合S上关系R是笛卡儿直积SS的一个子集，RSS。n关系R的传递闭包是包含R的最小的具有传递性质的关系。n若S是有限的，|S|=n，则R可表示为一个nn的关系矩阵M或n个结点的有向图G。n求关系R的传递闭包实际上也就是在有向图G上的搜索。而反过来，在有向图G上的搜索也就是求某种关系的传递闭包。第22页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析23传递闭包的集合算法n给定关系R以及S中的元素a，求R*(a)。初始化：U=A=a;q=true;while(q)for(pA)U=U d|dS 且 pRd；if(U=A)q=false;else A=U n这个算法稍加修改即可变成求R*(a)中满足某性质的元素的算法。n不难看出此算法实际也就是分支限界法。第23页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析24传递闭包的矩阵算法n若|S|=n，则R可表示为一个矩阵M。于是R的传递闭包R*的矩阵M*为：i=nM*=Mi=M0M1 Mn i=0其中M0为单位矩阵E，Mi为M的i次幂。nM*=E;for(i=1;i=n;i+)M*=M*M*M n不难看出此算法的时间复杂性为O(n4)。第24页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析25传递闭包的Warshall算法n下面给出求传递闭包的Warshall算法：nfor(i=1;i=n;i+)for(j=1;j=n;j+)if(Mji=1)for(k=1;k=n;k+)Mjk=Mjk+Mikn 此算法含三重循环，时间复杂性显然为O(n3)。n算法的正确性可用归纳法证明，请同学们自己去证明一下。第25页，共26页，编辑于2022年，星期三2023/1/25计算机算法设计与分析26分支限界法小结n分支限界法是最佳优先(包括广度优先在内)的搜索法，也是一种较为通用的算法。n其搜索的控制是采用有序的队列，即每次优先搜索评价函数值最小的结点，从而希望较快地找到最佳的路径或排列。n与其它算法相比，时间复杂性无本质区别。但好的评价函数可有小的常数，提高了效率。n评价函数应该能正确有效地压缩状态空间。第26页，共26页，编辑于2022年，星期三