计算机算法设计与分析第6章分支限界法课件.ppt

1、第六章第六章 分支限界法分支限界法第1页，共80页。理解分支限界法的剪枝搜索策略。理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架掌握分支限界法的算法框架队列式队列式(FIFO)分支限界法分支限界法优先队列式分支限界法优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。通过应用范例学习分支限界法的设计策略。单源最短路径问题单源最短路径问题装载问题；装载问题；布线问题布线问题0-1背包问题；背包问题；最大团问题；最大团问题；旅行售货员问题旅行售货员问题电路板排列问题电路板排列问题批处理作业调度问题批处理作业调度问题学习要点学习要点8/16/20222第2页，共80页。一、分支限界法

2、的基本思想一、分支限界法的基本思想二、单源最短路径问题二、单源最短路径问题三、装载问题三、装载问题四、四、0-1背包问题背包问题五、最大团问题五、最大团问题六、旅行售货员问题六、旅行售货员问题8/16/20223第3页，共80页。一、分支限界法的基本思想一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、0-1背包问题五、最大团问题六、旅行售货员问题8/16/20224第4页，共80页。分支限界法同回溯法类似，它也是在解空间中搜索问题的可行解分支限界法同回溯法类似，它也是在解空间中搜索问题的可行解或最优解，但搜索的方式不同。回溯法采用深度优先的方式，朝或最优解，但搜索的方式不同。回溯法

3、采用深度优先的方式，朝纵深方向搜索，直至达到问题的一个可行解，或经判断沿此路径纵深方向搜索，直至达到问题的一个可行解，或经判断沿此路径不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返不会达到问题的可行解或最优解时，停止向前搜索，并沿原路返回到该路径上最后一个还可扩展的结点。从该结点出发朝新的方回到该路径上最后一个还可扩展的结点。从该结点出发朝新的方向纵深搜索。分支定界法则采用宽度优先的方式搜索解空间树，向纵深搜索。分支定界法则采用宽度优先的方式搜索解空间树，它将活结点存放在一个特殊的表中。其策略是：在扩展结点处，它将活结点存放在一个特殊的表中。其策略是：在扩展结点处，先生成其所有的儿子

4、结点先生成其所有的儿子结点,将那些导致不可行解或导致非最优解的将那些导致不可行解或导致非最优解的儿子舍弃，其余儿子加入活结点表中。此后，从活结点表中取出儿子舍弃，其余儿子加入活结点表中。此后，从活结点表中取出一个结点作为当前扩展结点。并重复上述结点扩展过程。所以，一个结点作为当前扩展结点。并重复上述结点扩展过程。所以，分支限界法与回溯法的本质区别在于搜索方式的不同。回溯法更分支限界法与回溯法的本质区别在于搜索方式的不同。回溯法更适于处理那些求所有可行解的问题，而分支限界法更适于处理那适于处理那些求所有可行解的问题，而分支限界法更适于处理那些只确定一个可行解，特别是最优化问题。些只确定一个可行解

5、，特别是最优化问题。8/16/20225第5页，共80页。l分支限界法类似于回溯法，也是一种在问题的解空间树T中搜索问题解的算法。l分支限界法与回溯法的求解目标（适用范围）不同：n回溯法适用于找出满足约束条件的所有解的情况；n分支限界法发誓找出满足条件的一个解，或某种意义下的最优解。l搜索方式不同n回溯法：深度优先n分支限界法：广度优先8/16/20226第6页，共80页。l分支限界法常以广度优先或以最小耗费（最大效益）分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。优先的方式搜索问题的解空间树。l在分支限界法中，每一个活结点只有一次机会成为在分支限界法中，每一个活

6、结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，生其所有儿子结点。在这些儿子结点中，导致不可导致不可行解或导致非最优解的儿子结点被舍弃行解或导致非最优解的儿子结点被舍弃，其余儿子，其余儿子结点被加入活结点表中。结点被加入活结点表中。l此后，从活结点表中取下一结点成为当前扩展结此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止续到找到所需的解或活结点表为空时为止。8/16/20227第7页，

7、共80页。l从活结点表中选择下一扩展结点的不同方从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法：式导致不同的分支限界法：n队列式队列式(FIFO)分支限界法：将活结点表组织成一分支限界法：将活结点表组织成一个队列，按照队列先进先出（个队列，按照队列先进先出（FIFO）原则选取原则选取下一个节点为扩展节点。下一个节点为扩展节点。n优先队列式分支限界法：将活结点表组织成一个优先队列式分支限界法：将活结点表组织成一个优先队列，按照优先队列中规定的优先级选取优优先队列，按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。先级最高的节点成为当前扩展节点。u最大优先队列：使用最大堆

8、，体现最大效益优先最大优先队列：使用最大堆，体现最大效益优先u最小优先队列：使用最小堆，体现最小费用优先最小优先队列：使用最小堆，体现最小费用优先8/16/20228第8页，共80页。队列式分支限界法的搜索解空间树的方式类似于队列式分支限界法的搜索解空间树的方式类似于解空间树的宽度优先搜索，不同的是队列式分支限界解空间树的宽度优先搜索，不同的是队列式分支限界法不搜索以不可行结点（已经被判定不能导致可行解法不搜索以不可行结点（已经被判定不能导致可行解或不能导致最优解的结点）为根的子树。这是因为，或不能导致最优解的结点）为根的子树。这是因为，按照规则，这样的结点未被列入活结点表。按照规则，这样的结

9、点未被列入活结点表。8/16/20229第9页，共80页。优先队列式分支限界法的搜索方式是根据活结点的优先级确优先队列式分支限界法的搜索方式是根据活结点的优先级确定下一个扩展结点。结点的优先级常用一个与该结点有关的定下一个扩展结点。结点的优先级常用一个与该结点有关的数值数值p p 来表示。来表示。最大优先队列规定最大优先队列规定p p 值较大的结点点的优先级较高。在算法实现时通值较大的结点点的优先级较高。在算法实现时通常用一个最大堆来实现最大优先队列，用最大堆的常用一个最大堆来实现最大优先队列，用最大堆的Deletemax Deletemax 运算抽运算抽取堆中的下一个结点作为当前扩展结点，体

10、现最大效益优先的原则。取堆中的下一个结点作为当前扩展结点，体现最大效益优先的原则。类似地，最小优先队列规定类似地，最小优先队列规定p p 值较小的结点的优先级较高。在值较小的结点的优先级较高。在算法实现时，常用一个最小堆来实现，用最小堆的算法实现时，常用一个最小堆来实现，用最小堆的Deletemin Deletemin 运算抽取堆中下一个结点作为当前扩展结点，体现最小优先的运算抽取堆中下一个结点作为当前扩展结点，体现最小优先的原则。原则。8/16/202210第10页，共80页。采用优先队列式分支定界算法解决具体问题采用优先队列式分支定界算法解决具体问题时，应根据问题的特点选用最大优先或最小优

11、先时，应根据问题的特点选用最大优先或最小优先队列，确定各个结点的队列，确定各个结点的p p 值。值。8/16/202211第11页，共80页。n=3,c=30,w=16,15,15,p=45,25,258/16/202212第12页，共80页。n=3,c=30,w=16,15,15,p=45,25,25l队列式分支限界法：A B,C=B,CB,C D,E=EC,E F,G=F,GE,F,G J,K=K(45)1,0,0F,G L,M=L(50)0,1,1 M(25)G N,0=N(25),O(0)不搜索以不可行结点为根的子树不搜索以不可行结点为根的子树l优先队列式分支限界法：A B,C=B(4

12、5),C(0)B,C D,E=E(45)E,C J,K=K(45)1,0,0C F,G=F(25),G(0)F,G L,M=L(50),0,1,1 M(25)G N,O=N(25),O(0)l可用剪枝函数加速搜索可用剪枝函数加速搜索8/16/202213第13页，共80页。1234206305410ABCDEFGHIJKLMNOPQ1234344342322423问题描述：某售货员要问题描述：某售货员要到若干城市去推销商品，到若干城市去推销商品，一直各城市之间的路程，一直各城市之间的路程，他要选定一条从驻地出他要选定一条从驻地出发，经过每个城市一遍，发，经过每个城市一遍，最后回到住地的路线，最

13、后回到住地的路线，使总的路程最短。使总的路程最短。8/16/202214第14页，共80页。l队列式分支限界法：B C,D,EC,D,E F,GD,E,F,G H,IE,F,G,H,I J,KF,G,H,I,J,K L(59)1,2,3,4,1G,H,I,J,K M(66)H,I,J,K N(25)1,3,2,4,1I,J,K 1-3-4(26)J,K P(25)K Q(59)l优先队列式分支限界法：B C,D,E=C(30),D(6),E(4)E,D,C J,K=J(14),K(24)D,J,K,C H,I=H(11),I(26)H,J,K,I,C N=N(25)1,3,2,4,1J,K,I

14、,C P=P(25)K,I,C Q=Q(59)I,C I,C 被限界掉1234206305410ABCDEFGHIJKLMNOPQ12343443423224238/16/202215第15页，共80页。l如何确定合适的限界函数？l如何组织活结点表？l如何确定最优解中的各个分量？好的限界函数不仅计算简单，还要保证最优解在搜索空间中，更重要的是能好的限界函数不仅计算简单，还要保证最优解在搜索空间中，更重要的是能在搜索的早期对超出目标函数界的结点进行丢弃，减少搜索空间，从而尽快在搜索的早期对超出目标函数界的结点进行丢弃，减少搜索空间，从而尽快找到问题的最优解。找到问题的最优解。通常采用最大堆或最小

15、堆来实现优先队列式分支限界法求解问题。通常采用最大堆或最小堆来实现优先队列式分支限界法求解问题。可以用如下方法求得最优解中的分量：可以用如下方法求得最优解中的分量：1 1）对每个扩展结点保存该结点到）对每个扩展结点保存该结点到根结点的路径；根结点的路径；2 2）在搜索过程中构建搜索经过的树结构，在求得最优解）在搜索过程中构建搜索经过的树结构，在求得最优解时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。时，从叶子结点不断回溯到根结点，以确定最优解中的各个分量。8/16/202216第16页，共80页。一、分支限界法的基本思想二、单源最短路径问题二、单源最短路径问题三、装载问题四、0-1

16、背包问题五、最大团问题六、旅行售货员问题8/16/202217第17页，共80页。l在有向图G中，每一边都有一个非负边权。求图G的从源顶点s到目标顶点t之间的最短路径。8/16/202218第18页，共80页。l用优先队列式分支限界法解有向图用优先队列式分支限界法解有向图G的单源最短路径的单源最短路径问题问题产生产生的解空间树。其中，每一个结点旁边的数字表示的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。该结点所对应的当前路长。8/16/202219第19页，共80页。l用一最小堆来存储活结点表。其优先级是结点所对应的当前路优先级是结点所对应的当前路长长。l算法从图算法从图G

17、的源顶点的源顶点s和空优先队列开始。结点和空优先队列开始。结点s被扩展后，它的儿被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点顶点。如果从当前扩展结点i到顶点到顶点j有边可达，且从源出发，途有边可达，且从源出发，途经顶点经顶点i再到顶点再到顶点j的所相应的路径的长度小于当前最优路径长度，的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。

18、这个结点的扩展则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。过程一直继续到活结点优先队列为空时为止。8/16/202220第20页，共80页。l在算法扩展结点的过程中，一旦发现一个结点的下界在算法扩展结点的过程中，一旦发现一个结点的下界（即结点所对应的当前路长）不小于当前找到的最短（即结点所对应的当前路长）不小于当前找到的最短路长，则算法剪去以该结点为根的子树。路长，则算法剪去以该结点为根的子树。l在算法中，还可以利用结点间的控制关系进行剪枝。从源顶在算法中，还可以利用结点间的控制关系进行剪枝。从源顶点点s出发，出发，2条不同路径到达图条不同

19、路径到达图G的同一顶点。由于两条路的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对应的树中的径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。结点为根的子树剪去。l例如，从源点例如，从源点s s出发，经过边出发，经过边a,e,qa,e,q（路长为（路长为5 5）和经过边）和经过边c,hc,h（路长为（路长为6 6）的）的2 2条路径到达图条路径到达图G G的同一顶点。故可将后一条路的同一顶点。故可将后一条路径剪掉。径剪掉。8/16/202221第21页，共80页。剪枝策略 下图是用优先队列式分支限界法解有向图G的单源最短路径问题产生的解空间树的剪枝情况。BA优

20、于优于B，B可剪枝可剪枝经过不同经过不同的路径到的路径到达相同的达相同的顶点顶点A8/16/202222第22页，共80页。while(true)for(int j=1;j=n;j+)if(cE.ijinf)&(E.length+cE.ijdistj)/顶点顶点i到顶点到顶点j可达，且满足控制约束可达，且满足控制约束 distj=E.length+cE.ij;prevj=E.i;/加入活结点优先队列加入活结点优先队列 MinHeapNode N;N.i=j;N.length=distj;H.Insert(N);try H.DeleteMin(E);/取下一扩展结点取下一扩展结点 catch(O

21、utOfBounds)break;/优先队列空优先队列空 顶点顶点i i和和j j间有边，且此间有边，且此路径长小于原先从源点路径长小于原先从源点到到j j的路径长的路径长 8/16/202223第23页，共80页。计算从源顶点计算从源顶点1到其它顶点间最短路径到其它顶点间最短路径8/16/202224第24页，共80页。1230V2V0V1V4V33825420510计算从源顶点计算从源顶点V0 到其它顶点间最短路径到其它顶点间最短路径8/16/202225第25页，共80页。一、分支限界法的基本思想二、单源最短路径问题三、装载问题三、装载问题四、0-1背包问题五、最大团问题六、旅行售货员问

22、题8/16/202226第26页，共80页。l有一批共个集装箱要装上2艘载重量分别为C1和C2的轮船，其中集装箱i的重量为wi，且wiC1+C2l装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。l容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。(1)首先将第一艘轮船尽可能装满；(2)将剩余的集装箱装上第二艘轮船。8/16/202227第27页，共80页。解装载问题的队列式分支限界法只求出所要求的最优值，解装载问题的队列式分支限界法只求出所要求的最优值，稍后将进一步讨论求出最优解。函数稍后将进一步讨论求出最优解。函数MaxL

23、oading具体实施具体实施对解空间的分支限界搜索。其中队列对解空间的分支限界搜索。其中队列Q用于存放活结点表。用于存放活结点表。在队列在队列Q的元素值表示每个活结点所相应的当前载重量。的元素值表示每个活结点所相应的当前载重量。当其值为当其值为1时，表示队列已到达解空间树同一层结点的尾时，表示队列已到达解空间树同一层结点的尾部。部。8/16/202228第28页，共80页。函数函数EnQueue用于将活结点加入到活结点队用于将活结点加入到活结点队列中。该函数首先检查列中。该函数首先检查i是否等于是否等于n。如果。如果in，则表示当前活结点为一个叶结点。由于叶结点不则表示当前活结点为一个叶结点。

24、由于叶结点不会被进一步扩展，因此不必加入到活结点队列中。会被进一步扩展，因此不必加入到活结点队列中。此时只要检查该叶结点表示的可行解是否优于当此时只要检查该叶结点表示的可行解是否优于当前最优解，并适时更新当前最优解。当前最优解，并适时更新当前最优解。当in时，时，当前活结点是一个内部结点，应加入到活结点队当前活结点是一个内部结点，应加入到活结点队列中。列中。8/16/202229第29页，共80页。void EnQueue(&Q,Type wt,Type&bestw,int i,int n)/该函数负责加入活结点该函数负责加入活结点/如果不是叶结点，则将结点权值如果不是叶结点，则将结点权值wt

25、加入队列加入队列Qif(i=n)/可行可行 叶子结点叶子结点 if(wtbestw)bestw=wt;else Q.Add(wt);/不是叶子不是叶子8/16/202230第30页，共80页。函数函数MaxLoading在开始时将在开始时将i初始化为初始化为1，bestw初始化初始化为为0。此时活结点队列为空。将同层结点尾部标志。此时活结点队列为空。将同层结点尾部标志1加入加入到活结点队列中，表示此时位于第到活结点队列中，表示此时位于第1层结点的尾部。层结点的尾部。Ew存存储当前扩展结点所相应的重量。储当前扩展结点所相应的重量。8/16/202231第31页，共80页。在算法的在算法的whil

26、ewhile循环中，首先检测当前扩展结点的左儿子结点循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中其右儿子结点加入到活结点队列中(右儿子结点一定是可行结右儿子结点一定是可行结点点)。2 2个儿子结点都产生后，当前扩展结点被舍弃。个儿子结点都产生后，当前扩展结点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点，由于活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记队列中每一层结点之后都有一个尾部标记-1-1，故在取队首元素，故

27、在取队首元素时，活结点队列一定不空。当取出的元素是时，活结点队列一定不空。当取出的元素是-1-1时，再判断当前时，再判断当前队列是否为空。如果队列非空，则将尾部标记队列是否为空。如果队列非空，则将尾部标记-1-1加入活结点队加入活结点队列，算法开始处理下一层的活结点。列，算法开始处理下一层的活结点。8/16/202232第32页，共80页。while(true)/检查左儿子结点检查左儿子结点 if(Ew+wi=c)/xi=1 EnQueue(Q,Ew+wi,bestw,i,n);/右儿子结点总是可行的右儿子结点总是可行的 EnQueue(Q,Ew,bestw,i,n);/xi=0 Q.Dele

28、te(Ew);/取下一扩展结点取下一扩展结点 if(Ew=-1)/同层结点尾部同层结点尾部 if(Q.IsEmpty()return bestw;Q.Add(-1);/同层结点尾部标志同层结点尾部标志 Q.Delete(Ew);/取下一扩展结点取下一扩展结点 i+;/进入下一层进入下一层 8/16/202233第33页，共80页。节点的左子树表示将此集装箱装上船，右子树表示不节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设将此集装箱装上船。设bestwbestw是当前最优解；是当前最优解；ewew是当前扩是当前扩展结点所相应的重量；展结点所相应的重量；r r是剩余集装箱的重量

29、。则当是剩余集装箱的重量。则当ew+rew+r bestwbestw时，可将其右子树剪去。时，可将其右子树剪去。算法算法MaxLoadingMaxLoading初始时将初始时将bestwbestw置为置为0 0，直到搜索，直到搜索到第一个叶结点时才更新到第一个叶结点时才更新bestwbestw。因此在算法搜索到。因此在算法搜索到第一个叶结点之前，总有第一个叶结点之前，总有bestwbestw0 0，r r0 0，故，故EwEw十十r rbestwbestw总是成立。也就是说，此时右子树测试不起总是成立。也就是说，此时右子树测试不起作用。作用。另外，为了确保右子树成功剪枝，应该在算法每一次另外，

30、为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新进入左子树的时候更新bestwbestw的值。的值。8/16/202234第34页，共80页。算法的改进/检查左儿子结点 Type wt=Ew+wi;/左儿子结点的重量 if(wt bestw)bestw=wt;/加入活结点队列 if(i bestw&i n)Q.Add(Ew);/可能含最优解 Q.Delete(Ew);/取下一扩展结点右儿子剪枝右儿子剪枝 8/16/202235第35页，共80页。while(true)/检查左儿子结点检查左儿子结点 Type wt=Ew+wi;/左儿子结左儿子结点的重量点的重量 if(wt best

31、w)bestw=wt;/加入活结点队列加入活结点队列 if(i bestw&i 0;j-)bestxj=bestE-LChild;bestE=bestE-parent;找到最优值后，可以根据找到最优值后，可以根据parent回溯到根结回溯到根结点，找到最优解。点，找到最优解。8/16/202238第38页，共80页。l解装载问题的优先队列式分支限界法用最大优先队解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点列存储活结点表。活结点x在优先队列中的优先级定在优先队列中的优先级定义为从根结点到结点义为从根结点到结点x的路径所相应的载重量再加上的路径所相应的载重量再加上剩余集装箱的

32、重量之和。剩余集装箱的重量之和。l优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中优先级最大的活结点成为下一个扩展结点。以结点以结点x为根的子树中所有结点相应的路径的载重量为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。与其优先级相同。l在优先队列式分支限界法中，一旦有一个叶结点在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法的解即为最优解。此时可终止算法。8/16/202239第

33、39页，共80页。上述策略可以用两种不同的方式实现。第一种方式在结点优先队上述策略可以用两种不同的方式实现。第一种方式在结点优先队列的每一个活结点中保存从解空间树的根结点到该活结点的路径，列的每一个活结点中保存从解空间树的根结点到该活结点的路径，在算法确定了达到最优值的叶结点时，就在该叶结点处同时得到在算法确定了达到最优值的叶结点时，就在该叶结点处同时得到相应的最优解。第二种策略在算法的搜索进程中保存当前已构造相应的最优解。第二种策略在算法的搜索进程中保存当前已构造出的部分解空间树，这样在算法确定了达到最优值的叶结点时，出的部分解空间树，这样在算法确定了达到最优值的叶结点时，就可以在解空间树中

34、从该叶结点开始向根结点回溯，构造出相应就可以在解空间树中从该叶结点开始向根结点回溯，构造出相应的最优解。在下面的算法中，我们采用第二种策略。的最优解。在下面的算法中，我们采用第二种策略。8/16/202240第40页，共80页。第第i十十1层结点的剩余重量层结点的剩余重量ri定义为定义为ri 。变量变量E指向子集树中当前扩展结点指向子集树中当前扩展结点,Ew是相应的重量。算法开是相应的重量。算法开始时，始时，i1，Ew0，子集树的根结点是扩展结点。，子集树的根结点是扩展结点。/定义剩余重量数组定义剩余重量数组r int*r=(int*)malloc(sizeof(int)*(n+1);rn=0

35、;for(int j=n-1;j 0;j-)rj=rj+1+wj+1;8/16/202241第41页，共80页。int MaxLoading(int w,int c,int n)/优先队列式分支限界法，返回最优载重量，优先队列式分支限界法，返回最优载重量，bestx返回最优解返回最优解 /定义最大堆的容量为定义最大堆的容量为1000/MaxHeap HeapNode H(1000);head=(HeapNode*)malloc(sizeof(HeapNode);if(head=NULL)printf(没有足够的空间分配没有足够的空间分配n);return 1;head-level=0;head

36、-next=NULL;head-ptr=NULL;head-uweight=0;/定义剩余重量数组定义剩余重量数组r int*r=(int*)malloc(sizeof(int)*(n+1);rn=0;for(int j=n-1;j 0;j-)rj=rj+1+wj+1;/初始化初始化 int i=1;/当前扩展结点所处的层当前扩展结点所处的层 bbnode*E=0;/当前扩展结点当前扩展结点 int Ew=0;/扩展结点所相应的载重量扩展结点所相应的载重量 8/16/202242第42页，共80页。While循环体产生当前扩展结点的左右儿子结点。如果当前扩展循环体产生当前扩展结点的左右儿子结点

37、。如果当前扩展结点的左儿子结点是可行结点，即它所相应的重量末超过船载容结点的左儿子结点是可行结点，即它所相应的重量末超过船载容量，则将它加入到子集树的第量，则将它加入到子集树的第i十十1层上，并插入最大堆。扩展结层上，并插入最大堆。扩展结点的右儿子结点总是可行的，故直接插入子集树的最大堆中。接点的右儿子结点总是可行的，故直接插入子集树的最大堆中。接着算法从最大堆中取出最大元素作为下一个扩展结点。如果此时着算法从最大堆中取出最大元素作为下一个扩展结点。如果此时不存在下一个扩展结点，则相应的问题无可行解。如果下一个扩不存在下一个扩展结点，则相应的问题无可行解。如果下一个扩展结点是一个叶结点，即子集

38、树中第展结点是一个叶结点，即子集树中第n十十1层结点，则它相应的可层结点，则它相应的可行解为最优解。该最优解所相应的路径可由子集树中从该叶结点行解为最优解。该最优解所相应的路径可由子集树中从该叶结点开始沿结点父指针逐步构造出来。具体算法可描述如下：开始沿结点父指针逐步构造出来。具体算法可描述如下：8/16/202243第43页，共80页。while(i!=n+1)/非叶结点非叶结点 /检查当前扩展结点的儿子结点检查当前扩展结点的儿子结点 if(Ew+w i level;E=N-ptr;Ew=N-uweight-ri-1;/优先权优先权uweight=Ew+r i-1;8/16/202244第4

39、4页，共80页。for(j=n;j 0;j-)/构造当前最优解构造当前最优解 bestxj=E-LChild;E=E-parent;return Ew;构造当前最优解构造当前最优解8/16/202245第45页，共80页。一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、四、0-1背包问题背包问题五、最大团问题六、旅行售货员问题8/16/202246第46页，共80页。l给定n种物品和一个背包，物品i的重量是wi，价值pi,背包容量为C，问如何选择装入背包的物品，使装入背包中的物品的总价值最大？l对于每种物品只能选择完全装入或不装入，一个物品至多装入一次。8/16/202247第47

40、页，共80页。l首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。l在优先队列分支限界法中，节点的优先级由已装入背包的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。l算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时即为问题的最优值。8/16/202248第48页，共80页。templateTypep Knap:Bound(int i)/计算结点所相应价值的上界计算结点所相应价值

41、的上界 Typew cleft=c-cw;/剩余容量剩余容量 Typep b=cp;/价值上界价值上界 /以物品单位重量价值递减序装满剩余背包容量以物品单位重量价值递减序装满剩余背包容量 while(i=n&wi=cleft)cleft-=wi;b+=pi;i+;/装填剩余容量至装满背包装填剩余容量至装满背包 if(i=n)b+=pi/wi*cleft;return b;8/16/202249第49页，共80页。while(i!=n+1)/非叶结点非叶结点 /检查当前扩展结点的左儿子结点检查当前扩展结点的左儿子结点 Typew wt=cw+wi;if(wt bestp)bestp=cp+pi;

42、AddLiveNode(up,cp+pi,cw+wi,true,i+1);up=Bound(i+1);/检查当前扩展结点的右儿子结点检查当前扩展结点的右儿子结点 if(up=bestp)/右子树可能含最优解右子树可能含最优解 AddLiveNode(up,cp,cw,false,i+1);/取下一个扩展节点（略）取下一个扩展节点（略）分支限界搜索过程分支限界搜索过程8/16/202250第50页，共80页。一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、0-1背包问题五、最大团问题五、最大团问题六、旅行售货员问题8/16/202251第51页，共80页。l给定无向图G=(V，E)。

43、如果UV，且对任意u，vU有(u，v)E，则称U是G的完全子图。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。l下图G中，子集1，2是G的大小为2的完全子图。这个完全子图不是团，因为它被G的更大的完全子图1，2，5包含。1，2，5是G的最大团。1，4，5和2，3，5也是G的最大团。8/16/202252第52页，共80页。子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0。算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。当顶

44、点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。接着继续考察当前扩展结点的右儿子结点。当右儿子结点满足上界函数（upperSizebestn）时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。8/16/202253第53页，共80页。l用变量cliqueSize表示与该结点相应的团的顶点数；level表示结点在子集空间树中所处的层次；用cliqueSize+n-level+1作为顶点数上界upperSize的值。l在此优先队列式分支限界法中，upperSize实际上也是优先队列中元

45、素的优先级。算法总是从活结点优先队列中抽取具有最大upperSize值的元素作为下一个扩展元素。8/16/202254第54页，共80页。l具体算法略（见课本）。算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。对于子集树中的叶结点，有upperSizecliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。8/16/202255第55页，共80页。一、分支限界法的基本思想二、单源最短路径问题三、装载问题四、0-1背包问题五、最大团问

46、题六、旅行售货员问题六、旅行售货员问题8/16/202256第56页，共80页。l某售货员要到若干城市去推销商品，已知各城市之间的路程(或旅费)。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程(或总旅费)最小。l路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括V中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。l旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图G中找出费用最小的周游路线。8/16/202257第57页，共80页。l算法开始时创建一个最小堆，用于表

47、示活结点优先队列。堆中每个结点的子树费用的下界lcost值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出边并用minout记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的minout作算法初始化。l算法的while循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分2种情况进行处理：8/16/202258第58页，共80页。1、首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。2、当sn-2时

48、，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是x0:s，其可行儿子结点是从剩余顶点xs+1:n-1中选取的顶点xi，且(xs，xi)是所给有向图G中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀(x0:s，xi)的费用cc和相应的下界lcost。当lcostbestc时，将这个可行儿子结点插入到活结点优先队列中。8/16/202259第59页，共80页。l算法中while循环的终止条件是排列树的一个叶结点成为当前扩展结点。当s=n-1时，已找到的回路前缀是x0:n-1，它已包含图G的所有n个顶点。因此，当s=n-1时，相应的扩展结点表示一个叶结点。此时该

49、叶结点所相应的回路的费用等于cc和lcost的值。剩余的活结点的lcost值不小于已找到的回路的费用。它们都不可能导致费用更小的回路。因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可以结束。l算法结束时返回找到的最小费用，相应的最优解由数组v给出。8/16/202260第60页，共80页。8/16/202261第61页，共80页。8/16/202262第62页，共80页。8/16/202263第63页，共80页。8/16/202264第64页，共80页。8/16/202265第65页，共80页。算法中算法中while循环的终止条件是排列树的一个叶结点成为当前扩展循环的终止条件

50、是排列树的一个叶结点成为当前扩展结点。当结点。当sn1时，已找到的回路前缀是时，已找到的回路前缀是x0：n1，它已包含图，它已包含图G的所有的所有n个顶点。因此，当个顶点。因此，当sn1时，相应的扩展结点表示一个时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于叶结点。此时该叶结点所相应的回路的费用等于cc和和lcost的值。剩的值。剩余的活结点的余的活结点的1cost值不小于己找到的回路的费用。它们都不可能导值不小于己找到的回路的费用。它们都不可能导致费用更小的回路。因此已找到的叶结点所相应的回路是一个最小致费用更小的回路。因此已找到的叶结点所相应的回路是一个最小费用旅行售