第7章--分支限界法NEW

,算法分析与复杂度理论2009,罗熊xiongluo.ise北京科技大学信息工程学院计算机系,分支限界法,2009.4,3,3,提纲,典型实例0-1背包问题分支限界法的基本思想典型算法例题分析,4,分支限界法首先确定一个合理的限界函数，并根据限界函数确定目标函数的界down,up。然后，按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的目标函数的可能取值，如果某孩子结点的目标函数可能取得的值超出目标函数的界，则将其丢弃，因为从这个结点生成的解不会比目前已经得到的解更好；否则，将其加入待处理结点序列中。依次从序列中选取使目标函数的值取得极值的结点成为当前扩展结点.重复上述过程，直到找到最优解。,1.典型实例0-1背包问题,5,例：0-1背包问题。假设有4个物品，其重量分别为(4,7,5,3)，价值分别为(40,42,25,12)，背包容量W=10。首先，将给定物品按单位重量价值从大到小排序，结果如下：,6,应用贪心法求得近似解为(1,0,0,0)，获得的价值为40，这可以作为0/1背包问题的下界。如何求得0/1背包问题的一个合理的上界呢？考虑最好情况，背包中装入的全部是第1个物品且可以将背包装满，则可以得到一个非常简单的上界的计算方法：ub=W(v1/w1)=1010=100。于是，得到了目标函数的界40,100。限界函数为：,7,分支限界法求解0/1背包问题,（1）在根结点1，没有将任何物品装入背包，因此，背包的重量和获得的价值均为0，根据限界函数计算结点1的目标函数值为1010=100；,（2）在结点2，将物品1装入背包，因此，背包的重量为4，获得的价值为40，目标函数值为40+(10-4)6=76，将结点2加入待处理结点表中；,（3）在结点3，没有将物品1装入背包，因此，背包的重量和获得的价值仍为0，目标函数值为10660，将结点3加入待处理表中；在表中选取目标函数值取得极大的结点2优先进行搜索；,（4）在结点4，将物品2装入背包，因此，背包的重量为11，不满足约束条件，将结点4丢弃；,（5）在结点5，没有将物品2装入背包，因此，背包的重量和获得的价值与结点2相同，目标函数值为40+(10-4)5=70，将结点5加入待处理表中；在表中选取目标函数值取得极大的结点5优先进行搜索；,（6）在结点6，将物品3装入背包，因此，背包的重量为9，获得的价值为65，目标函数值为65+(10-9)4=69，将结点6加入待处理表中；,（7）在结点7，没有将物品3装入背包，因此，背包的重量和获得的价值与结点5相同，目标函数值为40+(10-4)464，将结点6加入待处理表中；在表中选取目标函数值取得极大的结点6优先进行搜索；,（8）在结点8，将物品4装入背包，因此，背包的重量为12，不满足约束条件，将结点8丢弃；,（9）在结点9，没有将物品4装入背包，因此，背包的重量和获得的价值与结点6相同，目标函数值为65；由于结点9是叶子结点，同时结点9的目标函数值是待处理表中的极大值，所以，结点9对应的解即是问题的最优解，搜索结束。,8,另一个例子：神奇的9位数,找出一个9位数：这个数包括了19这9个数字，这个9位数的前n位都能被n整除，若这个数表示为adcdefghi，则ab可被2整除，abc可被3整除，adcdefghi可被9整除。,直接搜索：一个9重循环，遍历各种循环。,分支限界：例如在循环到b等于奇数时，由于ab必须被2整除，因此奇数不满足条件，就可以不用搜索b等于奇数的所有9位数，分支后的算法效率提高了。,9,分支限界法是最佳优先搜索法,分支限界法就是最佳优先(包括广度优先在内)的搜索法。分支限界法将要搜索的结点按评价函数的优劣排序，让好的结点优先搜索，将坏的结点剪去。所以准确说，此方法应称为界限剪支法。分支限界法中有两个要点：,(1)评价函数的构造；(2)搜索路径的构造。,2.分支限界法的基本思想,10,评价函数的构造,评价函数要能够提供一个评定候选扩展结点的方法，以便确定哪个结点最有可能在通往目标的最佳路径上。一个评价函数f(d)通常可以由两个部分构成：从开始结点到结点d的已有耗损值g(d)；再从结点d到达目标的期望耗损值h(d)。即：,f(d)=g(d)+h(d),通常g(d)的构造较易，h(d)的构造较难。,11,搜索路径的构造,在回溯法中，每次仅考察一条路径，因而只需要构造这一条路径即可：前进时记下相应结点，回溯时删去最末尾结点的记录。这比较容易实现。在分支限界法中，是同时考察若干条路径，那么又该如何构造搜索的路径呢？,对每一个扩展的结点，建立三个信息：,(1)该结点的名称；(2)它的评价函数值；(3)指向其前驱的指针；,这样一旦找到目标，即可逆向构造其路径。用一个表保存准备扩展的结点，称为Open表。用一个表保存已搜索过的结点，称为Closed表。,12,分支限界法的一般算法,计算初始结点s的f(s);s,f(s),nil放入Open;while(Open)从Open中取出p,f(p),x(f(p)为最小);将p,f(p),x放入Closed;若p是目标，则成功返回；否则产生p的后继d并计算f(d)；对每个后继d,有二种情况：,dClosed|dOpen；dOpens,f(s),nil放入Open;while(Open)从Open中取出p,f(p),L;/L是路径已有结点若f(p)U，则抛弃该路径；若p是目标，则考虑修改上界函数值；否则将p,f(p),L放入Closed;在该路径上扩展结点p；对每个后继d计算f(d)；若f(d)U,则L=Lp;将d,f(d),L依序放入Open。,19,分支限界法求TSP举例,设有向图G=(V,E)的边的代价矩阵为C=cij。若不存在有向边E，则定义cij=且规定cii=。不失一般性，设周游路线均以顶点1为起点。左下为一个有向图G的代价矩阵C。,254031275173025191561950246228710,评价函数f(d)为1到d的代价减去已经过的边数。初始时f(1)=0;f(d)=f(p)+cpd1，这里p是d的前驱。,20,分支限界法求TSP的搜索,254031275173025191561950246228710,1,0,2,24,3,39,4,30,5,26,2,3,40,4,53,5,48,5,2,33,3,32,4,35,4,2,79,3,53,5,45,3,2,46,4,37,2,3,49,4,62,4,2,84,3,58,4,2,86,找到了第一条周游路线153421，其长度为95。,这不是最短周游路线，需要修改上界后继续搜索。,21,归约矩阵以及约数,前面的搜索的效率不高，几乎要搜索全部的状态空间。其原因是评价函数以及上下界的估计太低。为了设计求解TSP问题的更好的评价函数，先定义其代价矩阵的归约矩阵和约数。,给定代价矩阵C，从C的任何行i(或列i)的各元素中减去此行(或此列)的最小元素的值r(i)(或r(i)，称为对i行(或i列)的归约。将C的各行和各列都归约后的矩阵称为C的归约矩阵。和数r=inr(i)+inr(i)称为C的约数。,22,例子中的归约矩阵和约数,计算前面例子中的归约矩阵及其约数如下：,254031275173025191561950246228710,先做行归约：,r(1)=25,01562,r(2)=5,0122520,r(3)=1,181450,r(4)=6,344210,r(5)=7,15103,再做列归约：,r(1)=r(2)=r(3)=r(5)=0r(4)=3,32220,约数r=47。,23,约数是周游路线长度的下界,定理：设C是图G的代价矩阵，P是周游路线，则P的代价，即Pcij=r+Pcij，式中C=cij是C的归约矩阵，r为约数。,证明：由归约矩阵的构造可知：cij=cijr(i)r(j)即cij=cij+r(i)+r(j)。,任何周游路线包含n条边并且对应在C中的每行每列有且仅有一条边。于是Pcij=P(cij+r(i)+r(j)。,r+Pcij。,24,定义期望函数h(d),对开始结点1，令g(1)=0，h(1)=r，f(1)=r。若从结点1选择了一条边，不妨设边，则令g(2)=f(1)+从1到2的距离l，显然l应该是c12，而不应该再是c12了。那么h(2)=？自然可以想到h(2)可以是从2开始的路线的下界r2。是否也可用类似求r一样去求新的约数r2呢？可以，但在此之前应将边和所有边和边都删去，即置c12、c1k和ck2为。,设Cp为某路线上结点p的归约矩阵。从p选择边所得到结点d的归约矩阵Cd和约数rd为：(1)将Cp中的cpd，cpk和ckd置为，1kn；(2)依照求归约矩阵C的方法对Cp进行行归约和列归约，便得到了Cd和rd。,令f(1)=g(1)+h(1)，其中g(1)=0，h(1)=r。对任意路线上的结点d，设p是其前驱结点，则f(d)=g(d)+h(d)，其中，g(d)=f(p)+Cppd，h(d)=rd。,25,用新的评价函数求TSP,下面用新的评价函数求前面的例子，我们已经求得了它的归约矩阵C和约数r=47。,01532012222018142034418015100,1,47,2,g(2)=47+0=47,0,10,8,0,15,12,h(2)=12+3=15,f(2)=47+15=62,62,3,01532012222018142034418015100,g(3)=47+15=62,0,43,13,h(3)=1,f(3)=63,63,4,类似地可求出f(4)=51。,51,5,类似地可求出f(5)=50。,50,下面优先扩展的是结点5。,2,此时C2是在C5的基础上进行。右边就是C5。,012221814234418000,g(2)=50+0=50,0,16,0,15,0,3,h(2)=17,f(2)=67,67,3,类似地计算出f(3)=68,68,4,类似地计算出f(4)=81,81,下面扩展f(4)=51的结点4。并用同样方法计算它们的评价函数值。,2,121,3,69,4,64,1,5,4,下面要扩展的结点是f(2)=62的结点2。右边是其对应的归约矩阵C2。,2,0108152001801200,3,g(3)=62+0=62；对C2进行归约，,得h(3)=0；于是f(3)=62。,62,对结点2的另外两个儿子进行同样的计算，得：f(4)=84，f(5)=72。,4,84,5,72,下面对f(3)=62的结点3进行扩展。它有两个后继结点。,3,4,5,对结点4，g(4)=62+2=64。,0,h(4)=12，于是f(4)=64+12=76,76,对结点5，g(5)=62+0=62。,152000120,h(5)=0，于是f(5)=62+0=62,62,对结点5(f(5)=62)再进行扩展。,5,4,g(4)=62+0=62，,h(4)=0，f(4)=62。,62,结点4是目标结点，找到了第一条路线。,4,这条路线的长度为62，以其为上界。,其余未扩展的结点的评价函数值均超过上界，因而不再需要扩展了。,于是找到了一条最短的周游路线：123541。,26,分支边与二叉树,在构造求TSP的搜索树时，还有另外一种算法稍有点不同，就是将搜索树构造成二叉树。给定一条最短周游路线P，对于任一条边只有两种情况，即P或者P。这就可以表示成右边的二叉树：,k,m,n,_,其中,_表示P。,这样的边称为分支边。,27,用二叉树求TSP,1,2,50,_,3,62,2,4,53,_,5,68,4,6,64,_,7,65,3,8,62,_,9,74,8,10,62,_,11,70,10,12,62,_,13,66,12,14,62,_,15,66,14,16,62,_,17,结点16给出了一条最短周游路线：123541,28,分支限界法的效率,从TSP问题的计算可看出，分支限界法搜索的状态空间为O(2n)。对每个结点的计算时间为O(n2)。因此在最坏情况下，分支限界法计算TSP的时间复杂性为O(n22n)。显然，用分支限界法计算TSP的空间复杂性为O(n22n)。因为对每个结点需要n2的空间。,29,对评价函数的讨论,分支限界法总耗时为O(n22n)，它与回溯法、动态规划法等在时间复杂性上没有本质的区别。然而，如果评价函数选择得好，采用分支限界法可能有一个小得多的常数因子。好的评价函数应该有一个尽可能高的下界估计和一个尽可能低的上界估计，从而使得搜索空间能够得到有效的压缩，从而提高效率。在理论上可以证明好的评价函数所搜索的结点不会多于坏的评价函数所搜索的结点。,30,关系、传递闭包与搜索,定义在集合S上关系R是笛卡儿直积SS的一个子集，RSS。关系R的传递闭包是包含R的最小的具有传递性质的关系。若S是有限的，|S|=n，则R可表示为一个nn的关系矩阵M或n个结点的有向图G。求关系R的传递闭包实际上也就是在有向图G上的搜索。而反过来，在有向图G上的搜索也就是求某种关系的传递闭包。,31,