算法设计与分析07分支限界法课件.pptx

1、n理解分支限界法的剪枝搜索策略。理解分支限界法的剪枝搜索策略。n掌握分支限界法的算法框架掌握分支限界法的算法框架1.队列式队列式(FIFO)分支限界法分支限界法2.优先队列式分支限界法优先队列式分支限界法 n通过应用范例学习分支限界法的设计策略。通过应用范例学习分支限界法的设计策略。1.单源最短路径问题单源最短路径问题2.装载问题；装载问题；3.布线问题布线问题4.0-1背包问题；背包问题；5.最大团问题；最大团问题；6.旅行售货员问题旅行售货员问题7.电路板排列问题电路板排列问题8.批处理作业调度问题批处理作业调度问题1.分支限界法与回溯法的不同分支限界法与回溯法的不同（1）求解目标：）求解

2、目标：回溯法的求解目标是找出解空间树中回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。的解中找出在某种意义下的最优解。（2）搜索方式的不同：）搜索方式的不同：回溯法以深度优先的方式搜索回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。优先的方式搜索解空间树。2.分支限界法基本思想分支限界法基本思想 分支限界

3、法常以广度优先或以最小耗费（最大效益）优分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。先的方式搜索问题的解空间树。在分支限界法中，每一个活结点只有一次机会成为扩展在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并此后，从活结

4、点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止需的解或活结点表为空时为止。3.常见的两种分支限界法常见的两种分支限界法（1 1）队列式）队列式(FIFO)(FIFO)分支限界法分支限界法 按照队列先进先出（按照队列先进先出（FIFOFIFO）原则选取下一个节点为扩）原则选取下一个节点为扩展节点。展节点。（2 2）优先队列式分支限界法）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。成为当前扩展节点。1.问

5、题描述问题描述 下面以一个例子来说明单源最短路径问题：下面以一个例子来说明单源最短路径问题：在下图所在下图所给的有向图给的有向图G G中，每一边都有一个非负边权。要求图中，每一边都有一个非负边权。要求图G G的的从源顶点从源顶点s s到目标顶点到目标顶点t t之间的最短路径。之间的最短路径。下图是用优先队列式分支限界法解有向图下图是用优先队列式分支限界法解有向图G G的单源最的单源最短路径问题产生的解空间树。其中，每一个结点旁边的数短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。字表示该结点所对应的当前路长。2.算法思想算法思想 解单源最短路径问题的优先队列式分

6、支限界法用一极解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的当前路长。小堆来存储活结点表。其优先级是结点所对应的当前路长。算法从图算法从图G G的源顶点的源顶点s s和空优先队列开始。结点和空优先队列开始。结点s s被扩展被扩展后，它的儿子结点被依次插入堆中。此后，算法从堆中取出后，它的儿子结点被依次插入堆中。此后，算法从堆中取出具有最小当前路长的结点作为当前扩展结点，并依次检查与具有最小当前路长的结点作为当前扩展结点，并依次检查与当前扩展结点相邻的所有顶点。如果从当前扩展结点当前扩展结点相邻的所有顶点。如果从当前扩展结点i i到顶到顶点点j j有边可

7、达，且从源出发，途经顶点有边可达，且从源出发，途经顶点i i再到顶点再到顶点j j的所相应的所相应的路径的长度小于当前最优路径长度，则将该顶点作为活结的路径的长度小于当前最优路径长度，则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。到活结点优先队列为空时为止。3.剪枝策略剪枝策略 在算法扩展结点的过程中，一旦发现一个结点的在算法扩展结点的过程中，一旦发现一个结点的下界不小于当前找到的最短路长，则算法剪去以该结下界不小于当前找到的最短路长，则算法剪去以该结点为根的子树。点为根的子树。在算法中，利

8、用结点间的控制关系进行剪枝。从在算法中，利用结点间的控制关系进行剪枝。从源顶点源顶点s s出发，出发，2 2条不同路径到达图条不同路径到达图G G的同一顶点。由于的同一顶点。由于两条路径的路长不同，因此可以将路长长的路径所对两条路径的路长不同，因此可以将路长长的路径所对应的树中的结点为根的子树剪去。应的树中的结点为根的子树剪去。while(true)/搜索问题的解空间搜索问题的解空间 for(int j=1;j=n;j+)if(aenode.ij Float.MAX_VALUE&enode.length+aenode.ij distj)/顶点顶点i到顶点到顶点j可达，且满足控制约束可达，且满足

9、控制约束 distj=enode.length+aenode.ij;pj=enode.i;HeapNode node=new HeapNode(j,distj);heap.put(node);/加入活结点优先队列加入活结点优先队列 if(heap.isEmpty()break;else enode=(HeapNode)heap.removeMin();顶点顶点I I和和j j间有边，且此间有边，且此路径长小于原先从原点路径长小于原先从原点到到j j的路径长的路径长 1.问题的描述问题的描述 在多段图中求从在多段图中求从s到到t的一条最小成本的路径，可的一条最小成本的路径，可以看作是在以看作是在

10、k-2个段作出某种决策的结果。个段作出某种决策的结果。第第i次决策决定次决策决定Vi+1中的哪个结点在这条路径上，中的哪个结点在这条路径上，这里这里 1ik-2ik-2；最优性原理对多段图问题成立最优性原理对多段图问题成立2.向前处理策略求解向前处理策略求解 设设 P(i,j)是一条从是一条从Vi中的结点中的结点j到汇点到汇点t的最小成本路径，的最小成本路径，COST(i,j)是这条路径的成本。是这条路径的成本。1)向前递推式向前递推式 2)递推过程递推过程 第第k-1k-1段段 c(j,t)EE COST(k-1,j)=),1(),(min),(),(1liCOSTljcjiCOSTEljv

11、liEtj,l1l2.lpi+1tjViVi+112345678910111297324227111181456356425V1V2V3V4V55段图段图各递推结果各递推结果第第4段段 COST(4,9)=c(9,12)=4 COST(4,10)=c(10,12)=2 COST(4,11)=c(11,12)=5第第3段段 COST(3,6)=min6+COST(4,9),5+COST(4,10)=7 COST(3,7)=min4+COST(4,9),3+COST(4,10)=5 COST(3,8)=min5+COST(4,10),6+COST(4,11)=7第第2段段 COST(2,2)=mi

12、n4+COST(3,6),2+COST(3,7),1+COST(3,8)=7 COST(2,3)=9 COST(2,4)=18 COST(2,5)=15第第1段段 COST(1,1)=min9+COST(2,2),7+COST(2,3),3+COST(2,4),2+COST(2,5)=16S到到t的最小成本路径的成本的最小成本路径的成本 16 最小成本路径的求取最小成本路径的求取 记记 D(i,j)D(i,j)每一每一COST(i,j)COST(i,j)的决策的决策 即，使即，使c(j,l)+COST(i+1,l)c(j,l)+COST(i+1,l)取得取得最小值最小值的的l l值。值。例：例

13、：D(3,6)=10,D(3,7)=10 D(3,8)=10D(3,6)=10,D(3,7)=10 D(3,8)=10 D(2,2)=7,D(2,3)=6,D(2,4)=8,D(2,5)=8 D(2,2)=7,D(2,3)=6,D(2,4)=8,D(2,5)=8 D(1,1)=2 D(1,1)=2 根据根据D(1,1)D(1,1)的决策值的决策值向后向后递推求取最小成本路径：递推求取最小成本路径：v v2 2=D(1,1)=2=D(1,1)=2 v v3 3=D(2,D(1,1)=7=D(2,D(1,1)=7 v v4 4=D(3,D(2,D(1,1)=D(3,7)=10 =D(3,D(2,D

14、(1,1)=D(3,7)=10 故由故由s s到到t t的的最小成本路径最小成本路径是：是：12710121271012 3)算法描述算法描述 结点的编号规则结点的编号规则 源点源点s s编号为编号为1 1,然后依次对然后依次对V V2 2、V V3 3VVk-1k-1中的结点编号，汇点中的结点编号，汇点t t编号为编号为n n。目的：使对目的：使对COSTCOST和和D D的计算仅按的计算仅按n-1,n-2,1n-1,n-2,1的次序计算即可，的次序计算即可，无需考虑无需考虑标示结点所在标示结点所在段段的第一个下标。的第一个下标。算法描述算法描述算法算法4.1 多段图的向前处理算法多段图的向

15、前处理算法 procedure FGRAPH(E,k,n,P)/输入是按段的顺序给结点输入是按段的顺序给结点编号编号的，有的，有n个结点的个结点的k段图。段图。E是边是边 集，集，c(i,j)是边是边的成本。的成本。P(1:k)带出最小成本路径带出最小成本路径/real COST(n);integer D(n-1),P(k),r,j,k,n COST(n)0 for jn-1 to 1 by-1 do/计算计算COST(j)/设设r是具有性质：是具有性质：E且使且使c(j,r)+COST(r)取最小值的结点取最小值的结点 COST(j)c(j,r)+COST(r)D(j)r /记录决策值记录决

16、策值/repeat P(1)1;P(k)n for j2 to k-1 do /找路径上的第找路径上的第j个结点个结点/P(j)D(P(j-1)/回溯求出该路径回溯求出该路径/repeat end FGRAPH算法的时间复杂度算法的时间复杂度 若若G采用邻接表表示，总计算时间为：采用邻接表表示，总计算时间为：)(en3.向后处理策略求解向后处理策略求解 设设 BP(i,j)是一条从源点是一条从源点s到到Vi中的结点中的结点j的最小成本路径，的最小成本路径，BCOST(i,j)是这条路径的成本。是这条路径的成本。1)向后递推式向后递推式 2)递推过程递推过程 第第2 2段段 c(1,j)EE C

17、OST(2,j)=),(),1(min),(),(1jlcliCOSTjiBCOSTEjlvliEj ,112345678910111297324227111181456356425V1V2V3V4V55段图段图各递推结果各递推结果第第2段段 BCOST(2,2)=9 BCOST(2,3)=7 BCOST(2,4)=3 BCOST(2,5)=2第第3段段 BCOST(3,6)=minBCOST(2,2)+4,BCOST(2,3)+2=9 BCOST(3,7)=minBCOST(2,2)+2,BCOST(2,3)+7,BCOST(2,5)+11=11 BCOST(3,8)=minBCOST(2,

18、4)+11,BCOST(2,5)+8=10第第4段段 BCOST(4,9)=minBCOST(3,6)+6,BCOST(3,7)+4=15 BCOST(4,10)=minBCOST(3,6)+5,BCOST(3,7)+3,BCOST(3,8)+5=14 BCOST(4,11)=minBCOST(3,8)+6=16第第5段段 BCOST(5,12)=minBCOST(4,9)+4,BCOST(4,10)+2,BCOST(4,11)+5 =16S到到t的最小成本路径的成本的最小成本路径的成本 16 最小成本路径的求取最小成本路径的求取 记记 BD(i,j)BD(i,j)每一每一COST(i,j)C

19、OST(i,j)的决策的决策 即，使即，使COST(i-1,l)+c(l,j)COST(i-1,l)+c(l,j)取得取得最小值最小值的的l l值。值。例：例：BD(3,6)=3,BD(3,7)=2,BD(3,8)=5BD(3,6)=3,BD(3,7)=2,BD(3,8)=5 BD(4,9)=6,BD(4,10)=7,BD(4,11)=8 BD(4,9)=6,BD(4,10)=7,BD(4,11)=8 BD(5,12)=10 BD(5,12)=10 根据根据D(5,12)D(5,12)的决策值的决策值向前向前递推求取最小成本路径：递推求取最小成本路径：v v4 4=BD(5,12)=10=BD

20、(5,12)=10 v v3 3=BD(4,BD(5,12)=7=BD(4,BD(5,12)=7 v v2 2=BD(3,BD(4,BD(5,12)=BD(3,7)=2 =BD(3,BD(4,BD(5,12)=BD(3,7)=2 故由故由s s到到t t的的最小成本路径最小成本路径是：是：12710121271012 算法算法4.2 多段图的向后处理算法多段图的向后处理算法 procedure BGRAPH(E,k,n,P)/输入是按段的顺序给结点输入是按段的顺序给结点编号编号的，有的，有n个结点的个结点的k段图。段图。E是边是边 集，集，c(i,j)是边是边的成本。的成本。P(1:k)带出最

21、小成本路径带出最小成本路径/real BCOST(n);integer BD(n-1),P(k),r,j,k,n BCOST(1)0 for j2 to n do/计算计算BCOST(j)/设设r是具有是具有E且使且使BCOST(r)+c(r,j)取最小值性质的结点取最小值性质的结点 BCOST(j)BCOST(r)+c(r,j)BD(j)r /记录决策值记录决策值/repeat P(1)1;P(k)n for jk-1 to 2 by-1 do /找路径上的第找路径上的第j个结点个结点/P(j)D(P(j+1)/回溯求出该路径回溯求出该路径/repeat end BGRAPH4.多段图问题的

22、应用实例资源的分配问题多段图问题的应用实例资源的分配问题 将将n个资源分配给个资源分配给r个项目的问题：如果把个项目的问题：如果把j个资源，个资源，0jnjn，分配给项目，分配给项目i i，可以获得，可以获得N(i,j)N(i,j)的净利。的净利。问题：如何将这问题：如何将这n个资源分配给个资源分配给r个项目才能使各项目获个项目才能使各项目获得的净利之和达到最大。得的净利之和达到最大。转换成一个多段图问题求解。转换成一个多段图问题求解。用用r1段图段图描述该问题：描述该问题：段段：1到到r之间的每个段之间的每个段i表示项目表示项目i。结点结点：i=1时，只有一个结点时，只有一个结点源点源点s=

23、V(1,0)V(1,0)当当2irir时，每段有时，每段有n+1n+1个结点，每个结点具有形式个结点，每个结点具有形式 V(i,j)V(i,j)：表示到项目表示到项目i i之前为止，共把之前为止，共把j j个资源分配给了个资源分配给了 前前i-1i-1个项目，个项目，j=0,1,nj=0,1,n。汇点汇点t t=V(r+1,n)=V(r+1,n)边的一般形式边的一般形式：,jl,1irjl,1ir 成本：成本：当当jljl且且1ir1ir时，边时，边赋予成本赋予成本 N(i,l-j),N(i,l-j),表示给项目表示给项目i i分配分配l-jl-j个资源所可能获得的净利。个资源所可能获得的净利

24、。当当jnjn且且i=ri=r时，此时的边为：时，此时的边为：,该边赋该边赋 予成本：予成本：),(max0prNjnp指向汇点的边指向汇点的边注，并不是分给注，并不是分给的资源越多，得的资源越多，得到的净利就越大到的净利就越大实例：将实例：将4个资源分配给个资源分配给3个项目。构成一个个项目。构成一个4段图。段图。问题的解：资源的最优分配方案由一条问题的解：资源的最优分配方案由一条s到到t的的最大成本最大成本路路径给出径给出改变边成本的改变边成本的符号符号，从而将问题转换成为求取最小，从而将问题转换成为求取最小成本路径问题。成本路径问题。1.问题描述问题描述有一批共个集装箱要装上有一批共个集

25、装箱要装上2 2艘载重量分别为艘载重量分别为C1C1和和C2C2的轮船，的轮船，其中集装箱其中集装箱i i的重量为的重量为WiWi，且，且211ccwnii装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有，找出一种装载方案。容易证明：如果一个给定装载问题有解，则采用下面的容易证明：如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案。策略可得到最优装载方案。(1)(1)首先将第一艘轮船尽可能装满；首先将第一艘轮船尽可能装满；(2)(2)将剩余的集装箱装上第二艘轮船。将剩余的集装箱装上第二艘轮船。2.队列式分支限界法队列式分支限界法 在算法的在算法的while

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

27、元素时，活结点队列一定不空。当取出的元素是首元素时，活结点队列一定不空。当取出的元素是-1-1时，时，再判断当前队列是否为空。如果队列非空，则将尾部标记再判断当前队列是否为空。如果队列非空，则将尾部标记-1-1加入活结点队列，算法开始处理下一层的活结点。加入活结点队列，算法开始处理下一层的活结点。2.队列式分支限界法while(true)if(ew+wi=c)enQueue(ew+wi,i);/检查左儿子结点检查左儿子结点 enQueue(ew,i);/右儿子结点总是可行的右儿子结点总是可行的 ew=(Integer)queue.remove().intValue();/取下一扩展结点取下一扩

28、展结点 if(ew=-1)if(queue.isEmpty()return bestw;queue.put(new Integer(-1);/同层结点尾部标志同层结点尾部标志 ew=(Integer)queue.remove().intValue();/取下一扩展结点取下一扩展结点 i+;/进入下一层进入下一层 3.算法的改进算法的改进 节点的左子树表示将此集装箱装上船，右子树表示不节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设将此集装箱装上船。设bestwbestw是当前最优解；是当前最优解；ewew是当前扩是当前扩展结点所相应的重量；展结点所相应的重量；r r是剩余集装

29、箱的重量。则当是剩余集装箱的重量。则当ew+rew+r bestwbestw时，可将其右子树剪去，因为此时若要船装最时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。多集装箱，就应该把此箱装上船。另外，为了确保右子树成功剪枝，应该在算法每一次另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新进入左子树的时候更新bestwbestw的值。的值。3.算法的改进/检查左儿子结点检查左儿子结点 int wt=ew+wi;if(wt bestw)bestw=wt;/加入活结点队列加入活结点队列 if(i bestw&i 0;j-)bestxj=(e.leftChild

30、)?1:0;e=e.parent;5.优先队列式分支限界法优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点存储活结点表。活结点x x在优先队列中的优先级定义为从在优先队列中的优先级定义为从根结点到结点根结点到结点x x的路径所相应的载重量再加上剩余集装箱的路径所相应的载重量再加上剩余集装箱的重量之和。的重量之和。优先队列中优先级最大的活结点成为下一个扩展结点。优先队列中优先级最大的活结点成为下一个扩展结点。以结点以结点x x为根的子树中所有结点相应的路径的载重量不超为根的子树中所有结点相应的路径的载重量不超过

31、它的优先级。子集树中叶结点所相应的载重量与其优先过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。级相同。在优先队列式分支限界法中，一旦有一个叶结点成为在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。解。此时可终止算法。算法的思想算法的思想 解此问题的队列式分支限界法从起始位置解此问题的队列式分支限界法从起始位置a a开始将它开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将

32、这些方格成为可行结点被加入到活结点队列中，并且将这些方格标记为格标记为1 1，即从起始方格，即从起始方格a a到这些方格的距离为到这些方格的距离为1 1。接着，算法从活结点队列中取出队首结点作为下一接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为格标记为2 2，并存入活结点队列。这个过程一直继续到算，并存入活结点队列。这个过程一直继续到算法搜索到目标方格法搜索到目标方格b b或活结点队列为空时为止。即加入剪或活结点队列为空时为止。即加入剪枝的广度优先搜索。枝的广度优先搜索。Position of

33、fset=new Position 4;offset0=new Position(0,1);/右右offset1=new Position(1,0);/下下offset2=new Position(0,-1);/左左offset3=new Position(-1,0);/上上 定义移动方向的定义移动方向的相对位移相对位移 for(int i=0;i=size+1;i+)grid0i=gridsize+1i=1;/顶部和底部顶部和底部 gridi0=gridisize+1=1;/左翼和右翼左翼和右翼 设置边界的围墙设置边界的围墙for(int i=0;i numOfNbrs;i+)nbr.row

34、=here.row+offseti.row;nbr.col=here.col+offseti.col;if(gridnbr.rownbr.col=0)/该方格未标记该方格未标记 gridnbr.rownbr.col=gridhere.rowhere.col+1;if(nbr.row=finish.row)&(nbr.col=finish.col)break;q.put(new Position(nbr.row,nbr.col);找到目标位置后，可以通过回溯方法找到这条找到目标位置后，可以通过回溯方法找到这条最短路径。最短路径。n算法的思想算法的思想 首先，要对输入数据进行预处理，将各物品依其单

35、位重首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的优先级在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品装由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活结如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，点优先队列中。

36、当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。当扩展到叶节点时为问题的最优值。优先队列。当扩展到叶节点时为问题的最优值。上界函数上界函数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为上界函数为上界函数 while(i!=n+

37、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,enode,false);/取下一个扩展节点（略）取下一个扩展节点（略）分支限界搜索分支限界搜索过程过程1.问题描述问题描述 给定无向图给定无向图G=(VG=(V，E)E)。如果。如果U U V V，且对任意，且对任意u u，v v U U有有(u(u，v)v)E E，则称，

38、则称U U是是G G的完全子图。的完全子图。G G的完全子图的完全子图U U是是G G的的团当且仅当团当且仅当U U不包含在不包含在G G的更大的完全子图中。的更大的完全子图中。G G的最大团的最大团是指是指G G中所含顶点数最多的团。中所含顶点数最多的团。下图下图G G中，子集中，子集11，22是是G G的大小为的大小为2 2的完全子图。这个完的完全子图。这个完全子图不是团，因为它被全子图不是团，因为它被G G的更大的完全子图的更大的完全子图11，2 2，55包包含。含。11，2 2，55是是G G的最大团。的最大团。11，4 4，55和和22，3 3，55也是也是G G的最大团。的最大团。

39、2.上界函数上界函数 用变量用变量cliqueSizecliqueSize表示与该结点相应的团的顶点表示与该结点相应的团的顶点数；数；levellevel表示结点在子集空间树中所处的层次；用表示结点在子集空间树中所处的层次；用cliqueSize+n-level+1cliqueSize+n-level+1作为顶点数上界作为顶点数上界upperSizeupperSize的值。的值。在此优先队列式分支限界法中，在此优先队列式分支限界法中，upperSizeupperSize实际上实际上也是优先队列中元素的优先级。算法总是从活结点优先也是优先队列中元素的优先级。算法总是从活结点优先队列中抽取具有最大

40、队列中抽取具有最大upperSizeupperSize值的元素作为下一个扩值的元素作为下一个扩展元素。展元素。3.算法思想算法思想 子集树的根结点是初始扩展结点，对于这个特殊子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其的扩展结点，其cliqueSizecliqueSize的值为的值为0 0。算法在扩展内部结点时，首先考察其左儿子结点。算法在扩展内部结点时，首先考察其左儿子结点。在左儿子结点处，将顶点在左儿子结点处，将顶点i i加入到当前团中，并检查该加入到当前团中，并检查该顶点与当前团中其他顶点之间是否有边相连。当顶点顶点与当前团中其他顶点之间是否有边相连。当顶点i i与当前团中所

41、有顶点之间都有边相连，则相应的左儿与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。点优先队列，否则就不是可行结点。接着继续考察当前扩展结点的右儿子结点。当接着继续考察当前扩展结点的右儿子结点。当upperSizebestnupperSizebestn时，右子树中可能含有最优解，此时时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队将右儿子结点加入到子集树中并插入到活结点优先队列中。列中。算法的算法的whilewhile循环的终止条件是遇到子集树中

42、的一循环的终止条件是遇到子集树中的一个叶结点个叶结点(即即n+1n+1层结点层结点)成为当前扩展结点。成为当前扩展结点。对于子集树中的叶结点，有对于子集树中的叶结点，有upperSizeupperSizecliqueSizecliqueSize。此时活结点优先队列中剩余结点的。此时活结点优先队列中剩余结点的upperSizeupperSize值均不超过当前扩展结点的值均不超过当前扩展结点的upperSizeupperSize值，从值，从而进一步搜索不可能得到更大的团，此时算法已找到一而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。个最优解。1.问题描述问题描述 某售货员要到若干城市去

43、推销商品，已知各城市之间某售货员要到若干城市去推销商品，已知各城市之间的路程的路程(或旅费或旅费)。他要选定一条从驻地出发，经过每个城市。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地的路线，使总的路程一次，最后回到驻地的路线，使总的路程(或总旅费或总旅费)最小。最小。路线是一个带权图。图中各边的费用（权）为正数。路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括图的一条周游路线是包括V V中的每个顶点在内的一条回路。中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。周游路线的费用是这条路线上所有边的费用之和。旅行售货员问题的解空间可以组织成一棵

44、树，从树的旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。旅行根结点到任一叶结点的路径定义了图的一条周游路线。旅行售货员问题要在图售货员问题要在图G G中找出费用最小的周游路线。中找出费用最小的周游路线。2.算法描述算法描述 算法开始时创建一个最小堆，用于表示活结点优先算法开始时创建一个最小堆，用于表示活结点优先队列。堆中每个结点的子树费用的下界队列。堆中每个结点的子树费用的下界lcostlcost值是优先队值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用出列的优先级。接着算法计算出图中每个顶点的最小费用出边并用边并用minoutmino

45、ut记录。如果所给的有向图中某个顶点没有出记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个顶点边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的都有出边，则根据计算出的minoutminout作算法初始化。作算法初始化。算法的算法的whilewhile循环体完成对排列树内部结点的扩展。循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分对于当前扩展结点，算法分2 2种情况进行处理：种情况进行处理：1 1、首先考虑、首先考虑s=n-2s=n-2的情形，此时当前扩展结点是排列的情形，此时当前扩展结点是排列树中某个叶结点的父结点。如果

46、该叶结点相应一条可行回树中某个叶结点的父结点。如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。列中，否则舍去该叶结点。2 2、当、当sn-2sn-2时，算法依次产生当前扩展结点的所有时，算法依次产生当前扩展结点的所有儿子结点。由于当前扩展结点所相应的路径是儿子结点。由于当前扩展结点所相应的路径是x0:sx0:s，其可行儿子结点是从剩余顶点其可行儿子结点是从剩余顶点xs+1:n-1xs+1:n-1中选取的顶点中选取的顶点xixi，且，且(xs(xs，xi)xi)是所给有向图是所给有向图G G中的

47、一条边。对于中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀当前扩展结点的每一个可行儿子结点，计算出其前缀(x0:s(x0:s，xi)xi)的费用的费用cccc和相应的下界和相应的下界lcostlcost。当。当lcostbestclcostbestc时，将这个可行儿子结点插入到活结点优先时，将这个可行儿子结点插入到活结点优先队列中。队列中。算法中算法中whilewhile循环的终止条件是排列树的一个叶结循环的终止条件是排列树的一个叶结点成为当前扩展结点。当点成为当前扩展结点。当s=n-1s=n-1时，已找到的回路前缀时，已找到的回路前缀是是x0:n-1x0:n-1，它已包含图，

48、它已包含图G G的所有的所有n n个顶点。因此，当个顶点。因此，当s=n-1s=n-1时，相应的扩展结点表示一个叶结点。此时该叶时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于结点所相应的回路的费用等于cccc和和lcostlcost的值。剩余的的值。剩余的活结点的活结点的lcostlcost值不小于已找到的回路的费用。它们都值不小于已找到的回路的费用。它们都不可能导致费用更小的回路。因此已找到的叶结点所不可能导致费用更小的回路。因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可相应的回路是一个最小费用旅行售货员回路，算法可以结束。以结束。算法结束时返回找到

49、的最小费用，相应的最优解由算法结束时返回找到的最小费用，相应的最优解由数组数组v v给出。给出。n算法描述算法描述 算法开始时，将排列树的根结点置为当前扩展结点。在算法开始时，将排列树的根结点置为当前扩展结点。在do-whiledo-while循环体内算法依次从活结点优先队列中取出具有最循环体内算法依次从活结点优先队列中取出具有最小小cdcd值的结点作为当前扩展结点，并加以扩展。值的结点作为当前扩展结点，并加以扩展。首先考虑首先考虑s=n-1s=n-1的情形，当前扩展结点是排列树中的一的情形，当前扩展结点是排列树中的一个叶结点的父结点。个叶结点的父结点。x x表示相应于该叶结点的电路板排列。表

50、示相应于该叶结点的电路板排列。计算出与计算出与x x相应的密度并在必要时更新当前最优值和相应的相应的密度并在必要时更新当前最优值和相应的当前最优解。当前最优解。当当sn-1sn-1时，算法依次产生当前扩展结点的所有儿子结时，算法依次产生当前扩展结点的所有儿子结点。对于当前扩展结点的每一个儿子结点点。对于当前扩展结点的每一个儿子结点nodenode，计算出其相，计算出其相应的密度应的密度node.cdnode.cd。当。当node.cdbestdnode.cdbestd时，将该儿子结点时，将该儿子结点N N插插入到活结点优先队列中。入到活结点优先队列中。算法描述do if(enode.s=n-1