第六章分支界限法.ppt

1、2020/7/12,计算机算法设计与分析,1,第六章分支限界法,2020/7/12,计算机算法设计与分析,2,分支限界法是最佳优先搜索法,分支限界法就是最佳优先(包括广度优先在内)的搜索法。 分支限界法将要搜索的结点按评价函数的优劣排序，让好的结点优先搜索，将坏的结点剪去。所以准确说，此方法应称为界限剪支法。 分支限界法中有两个要点：,(1)评价函数的构造； (2)搜索路径的构造。,2020/7/12,计算机算法设计与分析,3,评价函数的构造,评价函数要能够提供一个评定候选扩展结点的方法，以便确定哪个结点最有可能在通往目标的最佳路径上。 一个评价函数f(d)通常可以由两个部分构成：从开始结点到

2、结点d的已有耗损值g(d)，和再从结点d到达目标的期望耗损值h(d)。即：,f(d) = g(d) + h(d),通常g(d)的构造较易，h(d)的构造较难。,2020/7/12,计算机算法设计与分析,4,搜索路径的构造,在回溯法中，每次仅考察一条路径，因而只需要构造这一条路径即可：前进时记下相应结点，回溯时删去最末尾结点的记录。这比较容易实现。 在分支限界法中，是同时考察若干条路径，那么又该如何构造搜索的路径呢？,对每一个扩展的结点，建立三个信息：,(1)该结点的名称； (2)它的评价函数值； (3)指向其前驱的指针；,这样一旦找到目标，即可逆向构造其路径。 用一个表保存准备扩展的结点，称为

3、Open表。 用一个表保存已搜索过的结点，称为Closed表。,2020/7/12,计算机算法设计与分析,5,分支限界法的一般算法,计算初始结点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 | d Open； dOpen s, f(s), nil放入Open; while (Open ) 从Open中取出p, f(p), L; /L是路径已有结点 若f(

4、p)U，则抛弃该路径； 若p是目标，则考虑修改上界函数值；否则 将p, f(p), L放入Closed; 在该路径上扩展结点p；对每个后继d 计算f(d)； 若f(d)U, 则L = L p; 将d, f(d),L依序放入Open。 ,2020/7/12,计算机算法设计与分析,11,分支限界法求TSP举例,设有向图G = (V, E)的边的代价矩阵为C = cij。若不存在有向边E，则定义cij=且规定cii=。不失一般性，设周游路线均以顶点1为起点。左下为一个有向图G的代价矩阵C。, 25 40 31 27 5 17 30 25 19 15 6 1 9 50 24 6 22 8 7 10 ,

5、评价函数f(d)为1到d的代价减去已经过的边数。 初始时f(1) = 0; f(d) = f(p) + cpd 1，这里p是d的前驱。,2020/7/12,计算机算法设计与分析,12,分支限界法求TSP的搜索, 25 40 31 27 5 17 30 25 19 15 6 1 9 50 24 6 22 8 7 10 ,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，其长度为9

6、5。,这不是最短周游路线，需要修改上界后继续搜索。,2020/7/12,计算机算法设计与分析,13,归约矩阵以及约数,前面的搜索的效率不高，几乎要搜索全部的状态空间。其原因是评价函数以及上下界的估计太低。为了设计求解TSP问题的更好的评价函数，先定义其代价矩阵的归约矩阵和约数。,给定代价矩阵C，从C的任何行i(或列i)的各元素中减去此行(或此列)的最小元素的值r(i)(或r(i)，称为对i行(或i列)的归约。将C的各行和各列都归约后的矩阵称为C的归约矩阵。和数 r = in r(i) + in r(i) 称为C的约数。,2020/7/12,计算机算法设计与分析,14,例子中的归约矩阵和约数,计

7、算前面例子中的归约矩阵及其约数如下：, 25 40 31 27 5 17 30 25 19 15 6 1 9 50 24 6 22 8 7 10 ,先做行归约：,r(1)=25, 0 15 6 2,r(2)=5,0 12 25 20,r(3)=1,18 14 5 0,r(4)=6,3 44 21 0,r(5)=7,15 1 0 3 ,再做列归约：,r(1)=r(2)=r(3)=r(5)=0 r(4)=3,3 22 2 0,约数 r = 47。,2020/7/12,计算机算法设计与分析,15,约数是周游路线长度的下界,定理：设C是图G的代价矩阵，P是周游路线，则P的代价，即P cij = r +

8、 P cij ， 式中C = cij是C的归约矩阵，r为约数。,证明：由归约矩阵的构造可知： cij = cij r(i) r(j) 即cij = cij + r(i) + r(j)。,任何周游路线包含n条边并且对应在C中的每行每列有且仅有一条边。于是 P cij = P(cij + r(i) + r(j)。,r + P cij 。,2020/7/12,计算机算法设计与分析,16,定义期望函数h(d),对开始结点1，令g(1) = 0，h(1) = r，f(1) = r。 若从结点1选择了一条边，不妨设边，则令g(2) = f(1)+从1到2的距离l ，显然l应该是c12，而不应该再是c12了

9、。 那么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) =

10、f(p) + Cppd， h(d) = rd。,2020/7/12,计算机算法设计与分析,17,用新的评价函数求TSP,下面用新的评价函数求前面的例子，我们已经求得了它的归约矩阵C和约数r = 47。, 0 15 3 2 0 12 22 20 18 14 2 0 3 44 18 0 15 1 0 0 ,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, 0 15 3 2 0 12 22 20 18 14 2 0 3 44 18 0 15 1 0 0 ,g(3) = 47 + 1

11、5 = 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。, 0 12 22 18 14 2 3 44 18 0 0 0 ,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,

12、64,1,5,4,下面要扩展的结点 是f(2)= 62的结点2。 右边是其对应的归 约矩阵C2。,2, 0 10 8 15 2 0 0 18 0 12 0 0 ,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，

13、 g(5) = 62 + 0 = 62。, 15 2 0 0 0 12 0 ,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。,2020/7/12,计算机算法设计与分析,18,分支边与二叉树,在构造求TSP的搜索树时，还有另外一种算法稍有点不同，就是将搜索

14、树构造成二叉树。 给定一条最短周游路线P，对于任一条边只有两种情况，即P或者P。 这就可以表示成右边的二叉树：,k,m,n,_ ,其中,_ 表示P。,这样的边称为分支边。,2020/7/12,计算机算法设计与分析,19,用二叉树求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,2020/7/12,计算机算法设计与分析,20,分支限界法

15、的效率,从TSP问题的计算可看出，分支限界法搜索的状态空间为O(2n)。 对每个结点的计算时间为O(n2)。 因此在最坏情况下，分支限界法计算TSP的时间复杂性为O(n22n)。 显然，用分支限界法计算TSP的空间复杂性为O(n22n)。因为对每个结点需要n2的空间。,2020/7/12,计算机算法设计与分析,21,对评价函数的讨论,分支限界法总耗时为O(n22n)，它与回溯法、动态规划法等在时间复杂性上没有本质的区别。 然而，如果评价函数选择得好，采用分支限界法可能有一个小得多的常数因子。 好的评价函数应该有一个尽可能高的下界估计和一个尽可能低的上界估计，从而使得搜索空间能够得到有效的压缩，

16、从而提高效率。 在理论上可以证明好的评价函数所搜索的结点不会多于坏的评价函数所搜索的结点。,2020/7/12,计算机算法设计与分析,22,关系、传递闭包与搜索,定义在集合S上关系R是笛卡儿直积SS的一个子集，RSS。 关系R的传递闭包是包含R的最小的具有传递性质的关系。 若S是有限的，|S| = n，则R可表示为一个nn的关系矩阵M或n个结点的有向图G。 求关系R的传递闭包实际上也就是在有向图G上的搜索。而反过来，在有向图G上的搜索也就是求某种关系的传递闭包。,2020/7/12,计算机算法设计与分析,23,传递闭包的集合算法,给定关系R以及S中的元素a，求R*(a)。 初始化：U = A

17、= a; q = true; while (q) for (pA) U = U d | dS 且 pRd； if (U = A) q = false; else A = U 这个算法稍加修改即可变成求R*(a)中满足某性质的元素的算法。 不难看出此算法实际也就是分支限界法。,2020/7/12,计算机算法设计与分析,24,传递闭包的矩阵算法,若|S| = n，则R可表示为一个矩阵M。于是R的传递闭包R*的矩阵M*为：,i=n M* = Mi = M0M1 Mn i=0 其中M0为单位矩阵E，Mi为M的i次幂。,M* = E; for (i=1; i=n; i+) M* = M* M*M,不难看出此算法的时间复杂性为O(n4)。,2020/7/12,计算机算法设计与分析,25,传递闭包的Warshall算法,下面给出求传递闭包的Warshall算法： for (i = 1; i = n; i+) for (j = 1; j = n; j+) if (Mji =