第六章分支界限法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,计算机算法设计与分析,*,第六章,分支限界法,2024/10/3,1,计算机算法设计与分析,分支限界法是最佳优先搜索法,分支限界法就是最佳优先(包括广度优先在内)的搜索法。,分支限界法将要搜索的结点按评价函数的优劣排序，让好的结点优先搜索，将坏的结点剪去。所以准确说，此方法应称为界限剪支法。,分支限界法中有两个要点：,(1)评价函数的构造；,(2)搜索路径的构造。,2024/10/3,2,计算机算法设计与分析,评价函数的构造,评价函数要能够提供一个评定候选扩展结点的方法，以便确定哪个结点最有可能在通往目标的最佳路径上。,一个评价函数,f(d),通常可以由两个部分构成：从开始结点到结点,d,的已有耗损值,g(d)，,和再从结点,d,到达目标的期望耗损值,h(d)。,即：,f(d)=g(d)+h(d),通常,g(d),的构造较易，,h(d),的构造较难。,2024/10/3,3,计算机算法设计与分析,搜索路径的构造,在回溯法中，每次仅考察一条路径，因而只需要构造这一条路径即可：前进时记下相应结点，回溯时删去最末尾结点的记录。这比较容易实现。,在分支限界法中，是同时考察若干条路径，那么又该如何构造搜索的路径呢？,对每一个扩展的结点，建立三个信息：,(1)该结点的名称；,(2)它的评价函数值；,(3)指向其前驱的指针；,这样一旦找到目标，即可逆向构造其路径。,用一个表保存准备扩展的结点，称为,Open,表。,用一个表保存已搜索过的结点,，,称为,Closed,表。,2024/10/3,4,计算机算法设计与分析,分支限界法的一般算法,计算初始结点,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,有二种情况：,d,Closed,|,d,Open,；,d,Open&d,Closed。,若(,d,f(d),p,Closed|d,f(d),p,Open),&f(d),f(d),，则删去旧结点并将,d,f(d),p,重新插入到,Open,中,;,否则,将,d,f(d),p,插入到,Open,中。,2024/10/3,5,计算机算法设计与分析,分支限界法求单源最短路径,单源最短路径问题的评价函数的构造：,g(d),定义为从源,s,到结点,d,所走的路径长度：,g(d)=g(p)+Cpd,这里,p,为,d,的前驱结点，,Cpd,为,p,到,d,的距离。,h(d),定义为,0。,于是,f(d)=g(d)。,源,s,的评价函数,f(s)=0。,评价函数的下界为0；上界初始时为，以后不断用取得的更短路径的长度来替代。,2024/10/3,6,计算机算法设计与分析,分支限界法求最短路径举例,1,2,5,4,3,10,20,50,100,30,10,60,赋权图,G,初始时，将源1,0,0放入,Open，Closed,为空。,Open,表,1,0,0,Closed,表,取出1,0,0放入,Closed；,生成其后继2,10,1、4,30,1和5,100,1，并依序放入,Open。,1,0,0,5,100,1,4,30,1,2,10,1,取出2,10,1放入,Closed；,生成其后继3,60,2，并依序插入,Open。,2,10,1,3,60,2,4,30,1,取出4,30,1放入,Closed；,生成其后继3,50,4和5,90,4，修订,Open,中已有的两个结点并依序排列,。,4,30,1,5,90,4,3,50,4,取出3,50,4放入,Closed；,生成其后继2,100,3和5,60,3，前者因劣于,Closed,中的2,10,1而被抛弃，后者修订了,Open,中的5,90,4。,3,50,4,5,60,3,取出5,60,3，因其已经是目标结点，算法成功并终止。,依据逆向指针可得最短路径为1435。,2024/10/3,7,计算机算法设计与分析,界限(,Bounding),评价函数,f(d),关系着算法的效率乃至成败。,因为在大多数问题中,f(d),只是个估计值，所以单靠,f(d),是不够的。通常还要设计它的上下界函数,U(d),和,L(d)。L(d),f(d),U(d)。,所谓分支限界法就是通过评价函数及其上下界函数的计算，将状态空间中不可能产生最佳解的子树剪去，减少搜索的范围，提高效率。因而更准确的称呼应是“界限剪支法”,2024/10/3,8,计算机算法设计与分析,用分支限界法求,TSP,TSP,是求排列的问题，不是仅找一条路径而已。因而需要对分支限界法的一般算法作些修改：,(1)待扩展的结点如果在本路径上已经出现，则不再扩展，但若是在其他路径上出现过，则仍需要扩展。,(2)新结点，无论其优劣，既不影响其它路径上的结点，也不受其它路径上的结点的影响。,(3)依据上界函数决定结点是否可以剪去。,2024/10/3,9,计算机算法设计与分析,分支限界法求排列,计算初始结点,s,的,f(s);,s,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=L,p;,将,d,f(d),L,依序放入,Open。,2024/10/3,10,计算机算法设计与分析,分支限界法求,TSP,举例,设有向图,G=(V,E),的边的代价矩阵为,C=,c,ij,。若不存在有向边E，,则定义,c,ij,=,且规定,c,ii,=。,不失一般性，设周游路线均以顶点1为起点。左下为一个有向图,G,的代价矩阵,C。,25 40 31 27,5,17 30 25,19 15,6 1,9 50 24,6,22 8 7 10,评价函数,f(d),为1到,d,的代价减去已经过的边数。,初始时,f(1)=0;,f(d)=f(p)+,c,pd,1，,这里,p,是,d,的前驱。,2024/10/3,11,计算机算法设计与分析,分支限界法求,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，其长度为95。,这不是最短周游路线，需要修改上界后继续搜索。,2024/10/3,12,计算机算法设计与分析,归约矩阵以及约数,前面的搜索的效率不高，几乎要搜索全部的状态空间。其原因是评价函数以及上下界的估计太低。为了设计求解,TSP,问题的更好的评价函数，先定义其代价矩阵的归约矩阵和约数。,给定代价矩阵,C，,从,C,的任何行,i(,或列,i),的各元素中减去此行,(,或此列,),的最小元素的值,r(i)(,或,r(i)，,称为对,i,行,(,或,i,列,),的归约。将,C,的各行和各列都归约后的矩阵称为,C,的归约矩阵。和数,r=,in,r(i)+,in,r(i),称为,C,的约数。,2024/10/3,13,计算机算法设计与分析,例子中的归约矩阵和约数,计算前面例子中的归约矩阵及其约数如下：,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。,2024/10/3,14,计算机算法设计与分析,约数是周游路线长度的下界,定理：设,C,是图,G,的代价矩阵，,P,是周游路线，则,P,的代价，即,P,c,ij,=r+,P,c,ij,，,式中,C=,c,ij,是,C,的归约矩阵，,r,为约数。,证明：由归约矩阵的构造可知：,c,ij,=,c,ij,r(i)r(j),即,c,ij,=,c,ij,+r(i)+r(j)。,任何周游路线包含,n,条边并且对应在,C,中的每行每列有且仅有一条边。于是,P,c,ij,=,P,(c,ij,+r(i)+r(j)。,r+,P,c,ij,。,2024/10/3,15,计算机算法设计与分析,定义期望函数,h(d),对开始结点1，令,g(1)=0，h(1)=r，f(1)=r。,若从结点1选择了一条边，不妨设边，则令,g(2)=f(1)+,从1到2的距离,l,，,显然,l,应该是,c,12,，,而不应该再是,c,12,了。,那么,h(2)=？,自然可以想到,h(2),可以是从2开始的路线的下界,r,2,。,是否也可用类似求,r,一样去求新的约数,r,2,呢？,可以，但在此之前应将边,和所有边,和边,都删去，即置,c,12,、,c,1k,和,c,k2,为。,设,C,p,为某路线上结点,p,的归约矩阵。从,p,选择边,所得到结点,d,的归约矩阵,C,d,和约数,r,d,为：,(1)将,C,p,中的,c,pd,，,c,pk,和,c,kd,置为，1,kn；,(2)依照求归约矩阵,C,的方法对,C,p,进行行归约和列归约，便得到了,C,d,和,r,d,。,令,f(1)=,g(1)+,h(1)，,其中,g(1)=0，h(1)=r。,对任意路线上的结点,d，,设,p,是其前驱结点，则,f(d)=g(d)+h(d)，,其中，,g(d)=f(p)+C,p,pd，h(d)=r,d,。,2024/10/3,16,计算机算法设计与分析,用新的评价函数求,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+15=62,0,43,13,h(3)=1,f(3)=63,63,4,类似地可求出,f(4)=51。,51,5,类似地可求出,f(5)=50。,50,下面优先扩展的是结点5。,2,此时,C,2,是在,C,5,的基础上进行。右边就是,C,5,。,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,64,1,5,4,下面要扩展的结点,是,f(2)=62,的结点2。,右边是其对应的归,约矩阵,C,2,。,2,0 10 8,15 ,2 0,0 18,0,12 0 0,3,g(3)=62+0=62；,对,C,2,进行归约，,得,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,。