算法设计与分析分支限界法第六章

算法设计与分析分支限界法第六章第一页，共四十五页，编辑于2023年，星期三2023/6/121计算机算法设计与分析树搜索的一般形式SearchTree(SpaceT){ok=0;L=T.initial;while(!ok||L≠){a=L.first;if(aisgoal)unfinish=falseelseControl-put-in(L,Sons(a));}三种搜索方法的不同就在于存放待考察的结点的表L的控制方式不同：DFS(回溯法)是栈；WFS是队列；BFS是队列中的元素排序。第二页，共四十五页，编辑于2023年，星期三2023/6/122计算机算法设计与分析分支限界法基本思想分支限界法就是最佳优先(包括广度优先)的搜索法。其基本思想是：将要待考察的结点按其优劣排序，优先搜索好结点。于是便有了两个问题：(1)如何知道结点的优劣？(2)在回溯法中，表L中结点的层次分明，因而路径也分明。但是这里排序会打乱表L中结点的层次，那又如何找回解的路径呢？第三页，共四十五页，编辑于2023年，星期三2023/6/123计算机算法设计与分析分支限界法基本思想分支限界法就是最佳优先(包括广度优先)的搜索法。其基本思想是：将要待考察的结点按其优劣排序，优先搜索好结点。于是便有了两个要点：(1)需要构造评价结点优劣的评价函数。(2)需要能够重新构造解的路径，也就是搜索的路径。第四页，共四十五页，编辑于2023年，星期三2023/6/124计算机算法设计与分析评价函数的构造评价函数要能够提供一个评定候选扩展结点的方法，以便确定哪个结点最有可能在通往目标的最佳路径上。一个评价函数f(d)通常由两个部分构成：⑴从开始结点到d的已有耗损值g(d)，和⑵再从d到达目标的期望耗损值h(d)。即：f(d)=g(d)+h(d)。通常g(d)的构造较易，h(d)的构造较难。第五页，共四十五页，编辑于2023年，星期三2023/6/125计算机算法设计与分析搜索路径的构造在回溯法中，每次仅考察一条路径，因而只需要构造这一条路径即可：前进时记下相应结点，回溯时删去最末尾结点的记录。这比较容易实现。在分支限界法中，是同时考察若干条路径，那么又该如何构造搜索的路径呢？往前看，前程无数！往回看，来路一条。每个结点只要记住其前驱结点就行了！第六页，共四十五页，编辑于2023年，星期三2023/6/126计算机算法设计与分析搜索路径的构造为此，只需要对每一个扩展的结点d，建立三个信息：(1)该结点的名称d；(2)它的评价函数值f(d)；(3)指向其前驱的指针p；即表示为[d,f(d),p]。这样一旦找到目标，即可以很方便地逆向构造出该路径。第七页，共四十五页，编辑于2023年，星期三2023/6/127计算机算法设计与分析Open表与Closed表搜索中，表L用来保存准备扩展的结点，即下一步的结点。把表L称为Open表。此外，为了构造解的路径，还需要一个表来保存已经搜索过的结点，即已经走过的结点。此表被称为Closed表。故任意结点d必是：①dOpen&&dClosed；②dClosed||dOpen。结点d尚未被考察。结点d已经被考察。第八页，共四十五页，编辑于2023年，星期三2023/6/128计算机算法设计与分析分支限界法的一般算法⑴初始化：计算起点s的f(s);[s,f(s),nil]放入Open;⑵while(Open≠){⑶从Open中取出[p,f(p),x](f(p)为最小);⑷if(f(p)<U){将[p,f(p),x]放入Closed;⑸if(p是目标){成功返回}else⑹{产生p的后继d并计算f(d)；对每个后继d有二种情况：①dOpen&&dClosed；②dClosed||dOpen。若结点d尚未被考察，则将[d,f(d),p]插入到Open中。若f(p)≥U，则剪去该路径。第九页，共四十五页，编辑于2023年，星期三2023/6/129计算机算法设计与分析分支限界法的一般算法⑴初始化：计算起点s的f(s);[s,f(s),nil]放入Open;⑵while(Open≠){⑶从Open中取出[p,f(p),x](f(p)为最小);⑷if(f(p)<U){将[p,f(p),x]放入Closed;⑸if(p是目标){成功返回}else⑹{产生p的后继d并计算f(d)；对每个后继d有二种情况：①dOpen&&dClosed；②dClosed||dOpen。若结点d已被考察，则说明这次是通过另一条路径到达到d。设d原来评价为f(d)’，将其与新的评价f(d)比较。若新评价更好，则删去旧的，将新的插入到Open中；否则丢弃。第十页，共四十五页，编辑于2023年，星期三2023/6/1210计算机算法设计与分析分支限界法的一般算法⑴初始化：计算起点s的f(s);[s,f(s),nil]放入Open;⑵while(Open≠){⑶从Open中取出[p,f(p),x](f(p)为最小);⑷if(f(p)<U){将[p,f(p),x]放入Closed;⑸if(p是目标){成功返回}else⑹{产生p的后继d并计算f(d)；对每个后继d⑺{if(dClosed&&dOpen){将[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){删去旧结点并将[d,f(d),p]重新插入到Open中。}}}第十一页，共四十五页，编辑于2023年，星期三2023/6/1211计算机算法设计与分析分支限界法求单源最短路径单源最短路径问题的评价函数的构造：g(d)定义为从源s到结点d所走的路径长度：g(d)=g(p)+C[p][d]，这里p为d的前驱结点，C[p][d]为p到d的距离。h(d)定义为0。于是f(d)=g(d)。源s的评价函数f(s)=0。评价函数的下界为0；上界初始时为∞，以后不断用取得的更短路径的长度来替代。第十二页，共四十五页，编辑于2023年，星期三2023/6/1212计算机算法设计与分析分支限界法求最短路径举例12543102050100301060赋权图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]，因其已经是目标结点，算法成功并终止。依据逆向指针可得最短路径为1→4→3→5。第十三页，共四十五页，编辑于2023年，星期三2023/6/1213计算机算法设计与分析界限(Bounding)评价函数f(d)关系着算法的效率乃至成败。因为在大多数问题中f(d)只是个估计值，所以单靠f(d)是不够的。通常还要设计它的上下界函数U(d)和L(d)。L(d)≤f(d)≤U(d)。所谓分支限界法就是通过评价函数及其上下界函数的计算，将状态空间中不可能产生最佳解的子树剪去，减少搜索的范围，提高效率。因而更准确的称呼应是“界限剪支法”第十四页，共四十五页，编辑于2023年，星期三2023/6/1214计算机算法设计与分析用分支限界法求TSPTSP是求排列的问题，不是仅找一条路径而已。因而需要对分支限界法的一般算法作些修改：(1)待扩展结点若已在本路径上，则不再扩展，但若是在其他路径上出现过，则仍需要扩展。为此，用一个表L来存储该路径出现的结点，即将[d,f(d),p]改为[d,f(d),*L]。该结点是否已经出现过，可查Closed表或者Open表。但是要查它出现在哪条路径上，就颇费周章了。这个L该怎么做？第十五页，共四十五页，编辑于2023年，星期三2023/6/1215计算机算法设计与分析用分支限界法求TSPTSP是求排列的问题，不是仅找一条路径而已。因而需要对分支限界法的一般算法作些修改：(1)待扩展结点若在本路径上已经出现，则不再扩展，但若是在其他路径上出现过，则仍需要扩展。为此，用一个表L来存储该路径出现的结点。(2)新结点，无论其优劣，既不影响其它路径上的结点，也不受其它路径上的结点的影响。(3)若考察结点的评价值超过上界值，则可以剪去。这实际上是剪去了这一支。L可设计为数组L[n]，初始值都为n；每加入新结点i，则L[i]

=p，这里p是i的前驱结点。若L[i]

≠n，则i已在此路径中。这样结点i的插入时间和判定时间都为常量。第十六页，共四十五页，编辑于2023年，星期三2023/6/1216计算机算法设计与分析分支限界法的一般算法⑴初始化：计算起点s的f(s);[s,f(s),nil]放入Open;⑵while(Open≠){⑶从Open中取出[p,f(p),x](f(p)为最小);⑷if(f(p)<U){将[p,f(p),x]放入Closed;⑸if(p是目标){成功返回}else⑹{产生p的后继d并计算f(d)；对每个后继d⑺{if(dClosed&&dOpen){将[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){删去旧结点并将[d,f(d),p]重新插入到Open中。}}}不失一般性，令0为起点，U为上界值：

Initialization：{

U=∞;Open=Closed=;计算f(0)；产生空表L；//L0=[0,n,……,n]Put-ordered-in(Open,[0,f(0),*L]);//把[0,f(0),*L)按序放入Open表中。//}第十七页，共四十五页，编辑于2023年，星期三2023/6/1217计算机算法设计与分析分支限界法的一般算法⑴Initialization；⑵while(Open≠){⑶从Open中取出[p,f(p),x](f(p)为最小);⑷if(f(p)<U){将[p,f(p),x]放入Closed;⑸if(p是目标){成功返回}else⑹{产生p的后继d并计算f(d)；对每个后继d⑺{if(dClosed&&dOpen){将[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){删去旧结点并将[d,f(d),p]重新插入到Open中。}}}*L此处改为表L。第十八页，共四十五页，编辑于2023年，星期三2023/6/1218计算机算法设计与分析分支限界法的一般算法⑴Initialization；⑵while(Open≠){⑶从Open中取出[p,f(p),*L](f(p)为最小);⑷if(f(p)<U){将[p,f(p),x]放入Closed;⑸if(p是目标){成功返回}else⑹{产生p的后继d并计算f(d)；对每个后继d⑺{if(dClosed&&dOpen){将[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){删去旧结点并将[d,f(d),p]重新插入到Open中。}}}此句可以不要了。因为每条通路上考察过的结点放在表L中了。Closed表L不再需要了。第十九页，共四十五页，编辑于2023年，星期三2023/6/1219计算机算法设计与分析分支限界法的一般算法⑴Initialization；⑵while(Open≠){⑶从Open中取出[p,f(p),*L](f(p)为最小);⑷if(f(p)<U){⑸if(p是目标){成功返回}else⑹{产生p的后继d并计算f(d)；对每个后继d⑺{if(dClosed&&dOpen){将[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){删去旧结点并将[d,f(d),p]重新插入到Open中。}}}如何知道p是目标？如果L中已有n个结点了，则p是目标。那又如何知道L中已有n个结点了？第二十页，共四十五页，编辑于2023年，星期三2023/6/1220计算机算法设计与分析分支限界法的一般算法⑴Initialization；⑵while(Open≠){⑶从Open中取出[p,f(p),*L](f(p)为最小);⑷if(f(p)<U){⑸if(p是目标){成功返回}else⑹{产生p的后继d并计算f(d)；对每个后继d⑺{if(dClosed&&dOpen){将[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){删去旧结点并将[d,f(d),p]重新插入到Open中。}}}L中存放的是每个结点的前驱，故可用L[0]作计数器。初始化时L[0]=1；之后每加入一个结点，L[0]++。当L[0]=n，则已达目标。第二十一页，共四十五页，编辑于2023年，星期三2023/6/1221计算机算法设计与分析分支限界法的一般算法⑴Initialization；⑵while(Open≠){⑶从Open中取出[p,f(p),*L](f(p)为最小);⑷if(f(p)<U){⑸if(p是目标){成功返回}else⑹{产生p的后继d并计算f(d)；对每个后继d⑺{if(dClosed&&dOpen){将[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){删去旧结点并将[d,f(d),p]重新插入到Open中。}}}所以，这里应改为：

if(L[0]==n){S=[p,f(p),*Lp];U=f(p)]}else//这里变量S用于存放解。//第二十二页，共四十五页，编辑于2023年，星期三2023/6/1222计算机算法设计与分析分支限界法的一般算法⑴Initialization；⑵while(Open≠){⑶从Open中取出[p,f(p),*L](f(p)为最小);⑷if(f(p)<U){⑸if(L[0]==n){S=[p,f(p),*Lp];U=f(p)]}else⑹{产生p的后继d并计算f(d)；对每个后继d⑺{if(dClosed&&dOpen){将[d,f(d),p]插入到Open中}else{if(f(d)＜f(d)’){删去旧结点并将[d,f(d),p]重新插入到Open中。}}}因为TSP要考察每一条通路，只要这条通路没走完，就要继续考察。⑹

{扩展结点p：对p的每个后继结点d，若d不在L中，则{计算f(d);若f(d)<U,则生成[d,f(d),*Ld]并将其按序放入Open表中;}}}第二十三页，共四十五页，编辑于2023年，星期三2023/6/1223计算机算法设计与分析扩展结点p扩展结点p需要做的事情有：对p的每个后继结点d，若d不在L中，则{计算f(d)；若f(d)<U，则生成[d,f(d),*Ld]并将其按序放入Open表中。什么样的结点是p的后继结点？令代价矩阵为C[n][n]。若C[p][d]<∞，则d是p的后继结点。即：for(d=1,d<n,d++){if(C[p][d]<∞)…。0是起点，无需考虑。if(L[d]=n)then把这两个if写在一起。第二十四页，共四十五页，编辑于2023年，星期三2023/6/1224计算机算法设计与分析扩展结点p扩展结点p需要做的事情有：对p的每个后继结点d，若d不在L中，则{计算f(d)；若f(d)<U，则生成[d,f(d),*L]并将其按序放入Open表中。for(d=1,d<n,d++){if(L(d)=n&&C[p][d]<∞)then{

V=f(d);//调用评价函数计算f(d)//

if(V<U){生成Ld;

Ld=L∪d;

Put-ordered-in(Open,[d,f(d),*Ld])}}需要为d生成一个其自有的路径表Ld。将p的路径表L插入p的后继结点d之后再赋值给Ld。最后将新扩展结点d按序放入Open表中。第二十五页，共四十五页，编辑于2023年，星期三2023/6/1225计算机算法设计与分析扩展结点pDevelop([p,f(p),*L]){for(d=1,d<n,d++){if(L(d)=n&&C[p][d]<∞)then{V=f(d);//调用评价函数计算f(d)//if(V<U){

生成Ld;Ld=L∪d;

Put-ordered-in(Open,[d,f(d),*Ld])}}第二十六页，共四十五页，编辑于2023年，星期三2023/6/1226计算机算法设计与分析分支限界法的一般算法Branch-bounding-for-TSP(n,*C[][]){⑴Initialization；⑵while(Open≠){⑶从Open中取出[p,f(p),*L](f(p)为最小);⑷if(f(p)<U){⑸if(L[0]==n){S=[p,f(p),*Lp];U=f(p)]}else⑹Develop([p,f(p),*Lp];}}}第二十七页，共四十五页，编辑于2023年，星期三2023/6/1227计算机算法设计与分析分支限界法求TSP举例设有向图G=(V,E)的边的代价矩阵为C=[cij]。若没有有向边<i,j>∈E，则定义cij=∞且规定cii=∞。不失一般性，设周游路线均以顶点1为起点。左下为一个有向图G的代价矩阵C。∞254031275∞1730251915∞6195024∞6228710∞评价函数f(d)为1到d的代价减去已经过的边数。初始时f(1)=0;f(d)=f(p)+cpd–1，这里p是d的前驱。第二十八页，共四十五页，编辑于2023年，星期三2023/6/1228计算机算法设计与分析分支限界法求TSP的搜索∞254031275∞1730251915∞6195024∞6228710∞102243394305262340453548523333243542793535453246437234946242843584286找到了一条周游路线1→5→3→4→2→1，其长度为95。这不是最短周游路线，需要修改上界后继续搜索。第二十九页，共四十五页，编辑于2023年，星期三2023/6/1229计算机算法设计与分析评价函数影响搜索效率前面的搜索的效率不高，几乎要搜索全部的状态空间。其原因是评价函数性能不好以及上下界的估计太低。要提高搜索效率，就必须要提高评价函数的性能，并精确上界的估计值。为了设计求解TSP问题的更好的评价函数，先定义其代价矩阵的归约矩阵和约数。第三十页，共四十五页，编辑于2023年，星期三2023/6/1230计算机算法设计与分析归约矩阵以及约数给定代价矩阵C，从C的任何行i(或列i)的各元素中减去此行(或此列)的最小元素的值r(i)(或r’(i))，称为对i行(或i列)的归约。将C的各行和各列都归约后的矩阵称为C的归约矩阵。数r=∑i≤nr(i)+∑i≤nr’(i)，即各行最小元素的值之和加上各列最小元素之和，称为C的约数。第三十一页，共四十五页，编辑于2023年，星期三2023/6/1231计算机算法设计与分析例子中的归约矩阵和约数计算前面例子中的归约矩阵及其约数如下：∞254031275∞1730251915∞6195024∞6228710∞先做行归约：∞254031275∞1730251915∞6195024∞6228710∞r(1)=25∞01562r(2)=5

0∞122520r(3)=11814∞50r(4)=6

34421∞0r(5)=715103∞第三十二页，共四十五页，编辑于2023年，星期三2023/6/1232计算机算法设计与分析例子中的归约矩阵和约数计算前面例子中的归约矩阵及其约数如下：∞254031275∞1730251915∞6195024∞6228710∞再做列归约：∞254031275∞1730251915∞6195024∞6228710∞r(1)=25∞01562r(2)=5

0∞122520r(3)=11814∞50r(4)=6

34421∞0r(5)=715103∞r’(1)=r’(2)=r’(3)=r’(5)=0r’(4)=

3322∞047约数r=47。归约矩阵这个约数r是什么呢？第三十三页，共四十五页，编辑于2023年，星期三2023/6/1233计算机算法设计与分析约数是周游路线代价的下界定理：设C是图G的代价矩阵，P是周游路线，则P的代价，即∑<i,j>∈Pcij=r+∑<i,j>∈Pcij’，式中C’=[cij’]是C的归约矩阵，r为约数。证明：由归约矩阵的构造可知：cij’=cij–r(i)–r’(j)，即cij=cij’+r(i)+r’(j)。任何周游路线包含n条边并且对应在C中的每行每列有且仅有一条边。于是∑<i,j>∈Pcij=∑<i,j>∈P(cij’+r(i)+r’(j))=r+∑<i,j>∈Pcij’。原来约数r是图G的任何一条周游路线的代价的下界!第三十四页，共四十五页，编辑于2023年，星期三2023/6/1234计算机算法设计与分析用约数定义期望函数h(d)既然约数是周游路线长度的下界，可以考虑用约数来定义期望函数h(d)：对开始结点1，令g(1)=0，h(1)=r，f(1)=r。若从结点1选择了一条边，不妨设边<1,2>，则令g(2)=f(1)+从1到2的距离l

，显然l应该是c’12，而不应该再是c12了。那么h(2)=？自然可以想到h(2)是从2开始的路线的下界r2。是否可用类似求r一样去求新的约数r2呢？第三十五页，共四十五页，编辑于2023年，星期三2023/6/1235计算机算法设计与分析求新的约数r2可以。要先将边<1,2>和所有边<1,k>和边<k,2>都删去，即置c12’、c1k’和ck2’为∞。设Cp’为路线上点p的归约矩阵。从p选择边<p,d>所得点d的归约矩阵Cd’和约数rd为：⑴先将Cp’中的cpd’，cpk’和ckd’都置为∞，这里1≤k≤n，即删去这些边；⑵依照求归约矩阵C’的方法对C’p进行行归约和列归约，便得到了Cd’和rd。因为边<1,2>已走过，所以不可能再走边<1,k>和边<k,2>了。第三十六页，共四十五页，编辑于2023年，星期三2023/6/1236计算机算法设计与分析新的评价函数f(d)不失一般性，将图G中结点标记为1~n，并设0为起点。将图G的代价矩阵C的约数r和归约矩阵C’分别为起点0的约数r1和归约矩阵C1’。对任意路线上结点d，定义其评价函数为：f(d)=g(d)+h(d)，其中：⑴g(d)=f(p)+Cp’[p][d]，这里p为d的前驱结点，并规定g(1)=0；⑵h(d)=rd。两点在p的归约矩阵中的代价第三十七页，共四十五页，编辑于2023年，星期三2023/6/1237计算机算法设计与分析用新的评价函数求TSP下面用新的评价函数求前面的例子，我们已经求得了它的归约矩阵C’和约数r=47。∞015320∞1222201814∞2034418∞015100∞1472g(2)=47+0=47∞∞∞∞∞∞∞∞010801512h(2)=12+3=15f(2)=47+15=62623∞015320∞1222201814∞2034418∞015100∞g(3)=47+15=62

∞∞∞∞∞∞∞∞04313h(3)=1f(3)=63634类似地可求出f(4)=51。515类似地可求出f(5)=50。50下面优先扩展的是结点5。2此时C’2是在C’5的基础上进行。右边就是C’5。∞∞∞∞∞0∞1222∞1814∞2∞34418∞∞

∞000∞g(2)=50+0=50∞∞∞∞∞01601503h(2)=17f(2)=67673类似地计算出f(3)=68684类似地计算出f(4)=8181下面扩展f(4)=51的结点4。并用同样方法计算它们的评价函数值。2121369464154下面要扩展的结点是f(2)=62的结点2。右边是其对应的归约矩阵C’2。2∞∞∞∞∞∞∞010815∞∞200∞18∞012∞00∞3g(3)=62+0=62；对C’2进行归约，∞∞∞∞∞得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∞∞200∞∞∞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，以其为上界。其余未扩展的结点的评价函数值均超过上界，因而不再需要扩展了。××××××××××于是找到了一条最短的周游路线：1→2→3→5→4→1。C1’C2’C1’r3的计算仍然要用C1’，故恢复为C1’。下面与此相类似，不再演示。

第三十八页，共四十五页，编辑于2023年，星期三2023/6/1238计算机算法设计与分析评价函数的程序设计对任意路线上结点d，定义其评价函数为：f(d)=g(d)+h(d)，其中：⑴g(d)=f(p)+Cp’[p][d]，这里p为d的前驱结点，并规定g(1)=0；⑵h(d)=rd。其中用到了d的前驱结点p的归约矩阵Cp’。因此，评