算法设计与分析详解优秀PPT.ppt

《算法设计与分析详解优秀PPT.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析详解优秀PPT.ppt（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/4/14计算机算法设计与分析1第六章分支限界法2023/4/14计算机算法设计与分析2树搜寻的一般形式SearchTree(Space T)ok=0;L=T.initial;while(!ok|L)a=L.first;if(a is goal)unfinish=false else Control-put-in(L,Sons(a);三种搜三种搜寻方法的不同就在方法的不同就在于存放待考察的于存放待考察的结点的表点的表L的限制方式不同：的限制方式不同：DFS(回溯法回溯法)是是栈；WFS是是队列；列；BFS是是队列中的元素排序。列中的元素排序。2023/4/14计算机算法设计与分析3分支

2、限界法基本思想分支限界法就是最佳优先(包括广度优先)的搜寻法。其基本思想是：将要待考察的结点按其优劣排序，优先搜寻好结点。于是便有了两个问题：(1)如何知道结点的优劣？(2)在回溯法中，表L中结点的层次分明，因而路径也分明。但是这里排序会打乱表L中结点的层次，那又如何找回解的路径呢？2023/4/14计算机算法设计与分析4分支限界法基本思想分支限界法就是最佳优先(包括广度优先)的搜寻法。其基本思想是：将要待考察的结点按其优劣排序，优先搜寻好结点。于是便有了两个要点：(1)须要构造评价结点优劣的评价函数。(2)须要能够重新构造解的路径，也就是搜寻的路径。2023/4/14计算机算法设计与分析5评

3、价函数的构造评价函数要能够供应一个评定候选扩展结点的方法，以便确定哪个结点最有可能在通往目标的最佳路径上。一个评价函数f(d)通常由两个部分构成：从起先结点到d的已有耗损值g(d)，和再从d到达目标的期望耗损值h(d)。即：f(d)=g(d)+h(d)。通常g(d)的构造较易，h(d)的构造较难。2023/4/14计算机算法设计与分析6搜寻路径的构造在回溯法中，每次仅考察一条路径，因而只须要构造这一条路径即可：前进时登记相应结点，回溯时删去最末尾结点的记录。这比较简洁实现。在分支限界法中，是同时考察若干条路径，那么又该如何构造搜寻的路径呢？往前看，前程多数！往回看，来路一条。每个结点只要记住其

4、前驱结点就行了！2023/4/14计算机算法设计与分析7搜寻路径的构造为此，只须要对每一个扩展的结点d，建立三个信息：(1)该结点的名称d；(2)它的评价函数值f(d)；(3)指向其前驱的指针p；即表示为d,f(d),p。这样一旦找到目标，即可以很便利地逆向构造出该路径。2023/4/14计算机算法设计与分析8Open表与Closed表搜寻中，表L用来保存准备扩展的结点，即下一步的结点。把表L称为Open表。此外，为了构造解的路径，还须要一个表来保存已经搜寻过的结点，即已经走过的结点。此表被称为Closed表。故随意结点d必是：dOpen&dClosed；dClosed|d Open。结点点d

5、尚未尚未被考察。被考察。结点点d已已经被考察。被考察。2023/4/14计算机算法设计与分析9分支限界法的一般算法初始化：计算起点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|d Open。若若结点点d尚未被考察，尚未被考察，则将将d,f(d),p插入到插入到Open中中。若若f(p)U，则剪剪去去该路径。路径。2023/4/14计算

6、机算法设计与分析10分支限界法的一般算法初始化：计算起点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|d Open。若若结点点d已被考察，已被考察，则说明明这次是通次是通过另一另一条路径到达到条路径到达到d。设d原来原来评价价为f(d)，将其，将其与新的与新的评价价f(d)比比较。若新。若新评价更好，价更好，则删去旧的，将新的插入到去

7、旧的，将新的插入到Open中；否中；否则丢弃弃。2023/4/14计算机算法设计与分析11分支限界法的一般算法初始化：计算起点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/4/14计算机算法设计与分析12分支限界法求单源最短

8、路径单源最短路径问题的评价函数的构造：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；上界初始时为，以后不断用取得的更短路径的长度来替代。2023/4/14计算机算法设计与分析13分支限界法求最短路径举例12543102050100301060赋权图G初始时，将源1,0,0放入Open，Closed为空。Open表1,0,0Closed表取出1,0,0放入Closed；生成其后继2,10,1、4,30,1和5,100,1，并依序放入Ope

9、n。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。2023/4/

10、14计算机算法设计与分析14界限(Bounding)评价函数f(d)关系着算法的效率乃至成败。因为在大多数问题中f(d)只是个估计值，所以单靠f(d)是不够的。通常还要设计它的上下界函数U(d)和L(d)。L(d)f(d)U(d)。所谓分支限界法就是通过评价函数及其上下界函数的计算，将状态空间中不行能产生最佳解的子树剪去，削减搜寻的范围，提高效率。因而更精确的称呼应是“界限剪支法”2023/4/14计算机算法设计与分析15用分支限界法求TSPTSP是求排列的问题，不是仅找一条路径而已。因而须要对分支限界法的一般算法作些修改：(1)待扩展结点若已在本路径上，则不再扩展，但若是在其他路径上出现过，

11、则仍须要扩展。为此，用一个表L来存储该路径出现的结点，即将d,f(d),p改为d,f(d),*L。该结点是否已点是否已经出出现过，可，可查Closed表或表或者者Open表。但是要表。但是要查它出它出现在哪条路径在哪条路径上，就上，就颇费周章了。周章了。这个个L该怎么做？怎么做？2023/4/14计算机算法设计与分析16用分支限界法求TSPTSP是求排列的问题，不是仅找一条路径而已。因而须要对分支限界法的一般算法作些修改：(1)待扩展结点若在本路径上已经出现，则不再扩展，但若是在其他路径上出现过，则仍须要扩展。为此，用一个表L来存储该路径出现的结点。(2)新结点，无论其优劣，既不影响其它路径上

12、的结点，也不受其它路径上的结点的影响。(3)若考察结点的评价值超过上界值，则可以剪去。这事实上是剪去了这一支。L可可设计为数数组Ln，初始，初始值都都为n；每加；每加入新入新结点点i，则Li=p，这里里p是是i的前的前驱结点。若点。若Li n，则i已在此路径中。已在此路径中。这样结点点i的插入的插入时间和判定和判定时间都都为常量。常量。2023/4/14计算机算法设计与分析17分支限界法的一般算法初始化：计算起点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(

13、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/4/14计算机算法设计与分析18分支限界法的一般算法Ini

14、tialization；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/4/14计算机算法设计与分析19分支限界法的一般算法Initialization；while(Open)从Open中取出p,f(p),*L(f(p)为最小);if(f(p)U)

15、将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/4/14计算机算法设计与分析20分支限界法的一般算法Initialization；while(Open)从Open中取出p,f(p),*L(f(p)为最小);if(f(p)

16、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/4/14计算机算法设计与分析21分支限界法的一般算法Initialization；while(Open)从Open中取出p,f(p),*L(f(p)为最小);if(f(p)U)if(p是目标)成功返回 e

17、lse 产生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中存放的是每个中存放的是每个结点的前点的前驱，故可用，故可用L0作作计数器。初始化数器。初始化时L0=1；之后每加入一；之后每加入一个个结点，点，L0+。当。当L0=n，则已达目已达目标。2023/4/14计算机算法设计与分析22分支限界法的一般算法Initialization；while(Open)从Open中取出p,f(p),*L(f(p)为最小);if(f(p)U)if(p是目标)

18、成功返回 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(L0=n)S=p,f(p),*Lp;U=f(p)else /这里里变量量S用于存放解。用于存放解。/2023/4/14计算机算法设计与分析23分支限界法的一般算法Initialization；while(Open)从Open中取出p,f(p),*L(f(p)为最小);if(f(p)U)if(L0=n)S=p,f(p),*Lp;U=f(p)els

19、e 产生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/4/14计算机算法设计与分析24扩展结点p扩展结点p须要做的事情有：对p的每个后继结点d

20、，若d不在L中，则计算f(d)；若f(d)U，则生成d,f(d),*Ld并将其按序放入Open表中。什么什么样的的结点是点是p的的后后继结点？点？令代价矩令代价矩阵为Cnn。若若Cpd ，则d是是p的后的后继结点。点。即：即：for(d=1,d n,d+)if(Cpd )。0是起点，无需考是起点，无需考虑。if(Ld=n)then把把这两个两个if 写在一起。写在一起。2023/4/14计算机算法设计与分析25扩展结点p扩展结点p须要做的事情有：对p的每个后继结点d，若d不在L中，则计算f(d)；若f(d)U，则生成d,f(d),*L并将其按序放入Open表中。for(d=1,d n,d+)i

21、f(L(d)=n&Cpd )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/4/14计算机算法设计与分析26扩展结点pDevelop(p,f(p),*L)for(d=1,d n,d+)if(L(d)=n&Cpd )then V=f(d);/调用评价函数计算f(d)/if(V

22、 U)生成Ld;Ld=L d;Put-ordered-in(Open,d,f(d),*Ld)2023/4/14计算机算法设计与分析27分支限界法的一般算法Branch-bounding-for-TSP(n,*C)Initialization；while(Open)从Open中取出p,f(p),*L(f(p)为最小);if(f(p)U)if(L0=n)S=p,f(p),*Lp;U=f(p)else Develop(p,f(p),*Lp;2023/4/14计算机算法设计与分析28分支限界法求TSP举例设有向图G=(V,E)的边的代价矩阵为C=cij。若没有有向边E，则定义cij=且规定cii=。不

23、失一般性，设周游路途均以顶点1为起点。左下为一个有向图G的代价矩阵C。25 40 31 27 5 17 30 2519 15 6 1 9 50 24 622 8 7 10 l评价函数f(d)为1到d的代价减去已经过的边数。l初始时f(1)=0;lf(d)=f(p)+cpd 1，这里p是d的前驱。2023/4/14计算机算法设计与分析29分支限界法求TSP的搜寻 25 40 31 27 5 17 30 2519 15 6 1 9 50 24 622 8 7 10 1022433943052623404535485233332435427935354532464372349462428435842

24、86找到了一条周游路途153421，其长度为95。这不是最短周游路途，须要修改上界后接着搜寻。装载问题问题描述有一批n个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为Wi，且装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。假如有，找出一种装载方案。简洁证明：假如一个给定装载问题有解，则接受下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上其次艘轮船。31队列式分支限界法在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。假如是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿

25、子结点确定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列确定不空。当取出的元素是-1时，再推断当前队列是否为空。假如队列非空，则将尾部标记-1加入活结点队列，算法起先处理下一层的活结点。32队列式分支限界法while(true)if(ew+wi=c)enQueue(ew+wi,i);/检查左儿子结点 enQueue(ew,i);/右儿子结点总是可行的 ew=(Integer)queue.remove().intValue();/取下一扩展结点 if(ew=-1)if

26、(queue.isEmpty()return bestw;queue.put(new Integer(-1);/同层结点尾部标记 ew=(Integer)queue.remove().intValue();/取下一扩展结点 i+;/进入下一层 33算法的改进节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+rbestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应当把此箱装上船。另外，为了确保右子树成功剪枝，应当在算法每一次进入左子树的时候更新bestw的值。34算法的改进/检查左儿

27、子结点 int wt=ew+wi;if(wt bestw)bestw=wt;/加入活结点队列 if(i bestw&i 0;j-)bestxj=(e.leftChild)?1:0;e=e.parent;37优先队列式分支限界法解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点x在优先队列中的优先级定义为从根结点到结点x的路径所相应的载重量再加上剩余集装箱的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。以结点x为根的子树中全部结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，

28、则可以断言该叶结点所相应的解即为最优解。此时可终止算法。380-1背包问题算法的思想 首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的点的优先先级由已装袋的物品价由已装袋的物品价值加上剩下的最大加上剩下的最大单位重量价位重量价值的物品装的物品装满剩余容量的价剩余容量的价值和。和。算法首先检查当前扩展结点的左儿子结点的可行性。假如该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点确定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。39上界函

29、数while(i=n&wi=cleft)/n表示物品总数，cleft为剩余空间 cleft-=wi;/wi表示i所占空间 b+=pi;/pi表示i的价值 i+;if(i=n)b+=pi/wi*cleft;/装填剩余容量装满背包return b;/b为上界函数400-1背包问题 while(i!=n+1)/非叶结点 double wt=cw+wi;if(wt bestp)bestp=cp+pi;addLiveNode(up,cp+pi,cw+wi,i+1,enode,true);up=bound(i+1);if(up=bestp)/检查右儿子节点 addLiveNode(up,cp,cw,i+1

30、,enode,false);/取下一个扩展节点（略）分支限界搜分支限界搜寻过程程41批处理作业问题问题的描述给定n个作业的集合J=J1,J2,Jn。每一个作业Ji都有2项任务要分别在2台机器上完成。每一个作业必需先由机器1处理，然后再由机器2处理。作业Ji须要机器j的处理时间为tji，i=1,2,n；j=1,2。对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。则全部作业在机器2上完成处理的时间和称为该作业调度的完成时间和。批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。42限界函数在结点E处相应子树中叶结点完成时间和的下界是：留意到假如

31、选择Pk，使t1pk在k=r+1时依非减序排列，S1则取得微小值。同理假如选择Pk使t2pk依非减序排列，则S2取得微小值。这可以作为优先队列式分支限界法中的限界函数。43算法描述算法的while循环完成对排列树内部结点的有序扩展。在while循环体内算法依次从活结点优先队列中取出具有最小bb值（完成时间和下界）的结点作为当前扩展结点，并加以扩展。首先考虑enode.s=n的情形，当前扩展结点enode是排列树中的叶结点。enode.sf2是相应于该叶结点的完成时间和。当enode.sf2 bestc时更新当前最优值bestc和相应的当前最优解bestx。当enode.sn时，算法依次产生当前

32、扩展结点enode的全部儿子结点。对于当前扩展结点的每一个儿子结点node，计算出其相应的完成时间和的下界bb。当bbbestc时，将该儿子结点插入到活结点优先队列中。而当bbbestc时，可将结点node舍去。44算法描述 do if(enode.s=n)/叶结点 if(enode.sf2 bestc)bestc=enode.sf2;for(int i=0;i n;i+)bestxi=enode.xi;当当enode.sf2bestc时，更新当前最更新当前最优值beste和和相相应的最的最优解解bestx45 else/产生当前扩展结点的儿子结点 for(int i=enode.s;i n;

33、i+)MyMath.swap(enode.x,enode.s,i);int f=new int 3;int bb=bound(enode,f);if(bb bestc HeapNode node=new HeapNode(enode,f,bb,n);heap.put(node);MyMath.swap(enode.x,enode.s,i);/完成结点扩展当当bbbestc时，将儿，将儿子子结点插入到活点插入到活结点点优先先队列中列中)2023/4/14计算机算法设计与分析46评价函数影响搜寻效率前面的搜寻的效率不高，几乎要搜寻全部的状态空间。其缘由是评价函数性能不好以及上下界的估计太低。要提高

34、搜寻效率，就必须要提高评价函数的性能，并精确上界的估计值。为了设计求解TSP问题的更好的评价函数，先定义其代价矩阵的归约矩阵和约数。2023/4/14计算机算法设计与分析47归约矩阵以及约数给定代价矩阵C，从C的任何行i(或列i)的各元素中减去此行(或此列)的最小元素的值r(i)(或r(i)，称为对i行(或i列)的归约。将C的各行和各列都归约后的矩阵称为C的归约矩阵。数r=in r(i)+in r(i)，即各行最小元素的值之和加上各列最小元素之和，称为C的约数。2023/4/14计算机算法设计与分析48例子中的归约矩阵和约数计算前面例子中的归约矩阵及其约数如下：25 40 31 27 5 17

35、 30 2519 15 6 1 9 50 24 622 8 7 10 先做行归约：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 2023/4/14计算机算法设计与分析49例子中的归约矩阵和约数计算前面例子中的归约矩阵及其约数如下：25 40 31 27 5 17 30 2519 15 6 1 9 50 24 622 8 7 10 再做列归约：25 40 31 27 5 17 30 2

36、519 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)=0r(4)=3322 047约数 r=47。归约矩矩阵这个个约数数r是什么呢？是什么呢？2023/4/14计算机算法设计与分析50约数是周游路途代价的下界定理：设C是图G的代价矩阵，P是周游路途，则P的代价，即P cij=r+P cij，式中C=cij是C的归约矩阵，r为约数。证明：由归约矩阵的构造可知：cij=cij r(i)r(j)，即

37、cij=cij+r(i)+r(j)。任何周游路途包含n条边并且对应在C中的每行每列有且仅有一条边。于是 Pcij=P(cij+r(i)+r(j)=r+Pcij。原来原来约数数r r是是图G G的任何一条周游路的任何一条周游路途的代价的下界途的代价的下界!2023/4/14计算机算法设计与分析51用约数定义期望函数h(d)既然约数是周游路途长度的下界，可以考虑用约数来定义期望函数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

38、)是从2起先的路途的下界r2。是否可用类似求r一样去求新的约数r2呢？2023/4/14计算机算法设计与分析52求新的约数r2可以。要先将边和全部边和边都删去，即置c12、c1k和ck2为。设Cp为路途上点p的归约矩阵。从p选择边所得点d的归约矩阵Cd和约数rd为：先将Cp中的cpd，cpk和ckd都置为，这里1kn，即删去这些边；依照求归约矩阵C的方法对Cp进行行归约和列归约，便得到了Cd和rd。因因为边已走已走过，所以不行，所以不行能再走能再走边和和边了。了。2023/4/14计算机算法设计与分析53新的评价函数f(d)不失一般性，将图G中结点标记为1n，并设0为起点。将图G的代价矩阵C的

39、约数r和归约矩阵C分别为起点0的约数r1和归约矩阵C1。对随意路途上结点d，定义其评价函数为：f(d)=g(d)+h(d)，其中：g(d)=f(p)+Cppd，这里p为d的前驱结点，并规定g(1)=0；h(d)=rd。两点在两点在p的的归约矩矩阵中的代价中的代价2023/4/14计算机算法设计与分析54用新的评价函数求TSP下面用新的评价函数求前面的例子，我们已经求得了它的归约矩阵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=47 0 10801512h(2)=12+3=15f(2)=47+15=62

40、623 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=50 01601503h(2)=17f(2)=67673类似地计算出f(3)=68684类似地计算出f(4)=8181下面扩展f(4)=51的结点4。并用同样方法计算它们的评价函数值。212136946415

41、4 下面要扩展的结点 是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)再进行扩

42、展。54g(4)=62+0=62，h(4)=0，f(4)=62。62结点4是目标结点，找到了第一条路途。4这条路途的长度为62，以其为上界。其余未扩展的结点的评价函数值均超过上界，因而不再须要扩展了。于是找到了一条最短的周游路途：123541。C1C2C1r3的的计计算仍旧要用算仍旧要用C1，故，故复原复原为为C1。下面与此相。下面与此相类类似，不再演示。似，不再演示。2023/4/14计算机算法设计与分析55评价函数的程序设计对随意路途上结点d，定义其评价函数为：f(d)=g(d)+h(d)，其中：g(d)=f(p)+Cppd，这里p为d的前驱结点，并规定g(1)=0；h(d)=rd。其中用

43、到了d的前驱结点p的归约矩阵Cp。因此，评价函数的计算中须要用到的参数有：p、f(p)、Cp和d，计算的结果有f(d)和Cd。留意到Cp是与路径有关的，因此在p,f(p),*L中应增加Cp，改为p,f(p),*L,*Cp。2023/4/14计算机算法设计与分析56评价函数的数据结构1、输入数据：考察的结点d：int d；前驱结点p：int p；前驱结点p的评价函数值：int fp；前驱结点p的归约矩阵：Cpnn；2、输出数据：结点d的评价函数值；前驱结点d的归约矩阵：Cdnn；2023/4/14计算机算法设计与分析57评价函数的计算过程评价函数的计算如下：1、g(d)=f(p)+Cppd；2、

44、依据Cp计算约数rd和归约矩阵Cdnn；3、f(d)=g(d)+rd。将Cd赋值为Cp；将Cd的第p行和第d列都置为；对Cd求归约数rd并进行归约。将求代价矩将求代价矩阵的的约数数和和归约矩矩阵的的计算算单独作独作为一个子程序。一个子程序。此此举是是为了初始化。了初始化。可融入可融入和和中中实现。2023/4/14计算机算法设计与分析58TSP分支限界法的再修改Branch-bounding-for-TSP(n,*C)须要做如下修改，以适应评价函数的计算：1、结点的数据结构中应增加其对应的归约矩阵，即改为p,f(p),*L,*Cp。2、初始化时要增加C的约数r和及其规约矩阵的计算。3、在扩展结

45、点p的工作中，应当在计算f(d)之前，为d生成其规约矩阵的空间。2023/4/14计算机算法设计与分析59分支限界法的效率从TSP问题的计算可看出，分支限界法搜寻的状态空间为O(2n)。对每个结点的计算时间为O(n2)。因此在最坏状况下，分支限界法计算TSP的时间困难性为O(n22n)。明显，用分支限界法计算TSP的空间困难性为O(n22n)。因为对每个结点须要n2的空间。2023/4/14计算机算法设计与分析60对评价函数的探讨分支限界法总耗时为O(n22n)，它与回溯法、动态规划法等在时间困难性上没有本质的区分。然而，假如评价函数选择得好，接受分支限界法可能有一个小得多的常数因子。好的评价函数应当有一个尽可能高的下界估计和一个尽可能低的上界估计，从而使得搜寻空间能够得到有效的压缩，从而提高效率。在理论上可以证明好的评价函数所搜寻的结点不会多于坏的评价函数所搜寻的结点。2023/4/14计算机算法设计与分析61分支限界法小结分支限界法是最佳优先(包括广度优先在内)的搜寻法，也是一种较为通用的算法。其搜寻的限制是接受有序的队列，即每次优先搜寻评价函数值最小的结点，从而希望较快地找到最佳的路径或排列。与其它算法相比，时间困难性无本质区分。但好的评价函数可有小的常数，提高了效率。评价函数应当能正确有效地压缩状态空间。