第6讲-分支界限法分析.ppt

《第6讲-分支界限法分析.ppt》由会员分享，可在线阅读，更多相关《第6讲-分支界限法分析.ppt（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第1 1页页第第6章章 分支限界法分支限界法1 1广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2 2页页学习要点学习要点理解分支限界法的剪枝搜索策略。理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架掌握分支限界法的算法框架（1）队列式）队列式(FIFO)分支限界法分支限界法（2）优先队列式分支限界法）优先队列式分支限界法 2 2广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3 3页页学习要点学习要点通过应用范例学习分支限界法的设计策略。通过应用范例学习分支限界法的设计策略。（1）单源最短路径问题）单源最短路径问题（2）装载问题；

2、）装载问题；（3）布线问题）布线问题（4）0-1背包问题；背包问题；（5）最大团问题；）最大团问题；（6）旅行售货员问题）旅行售货员问题（7）电路板排列问题）电路板排列问题（8）批处理作业调度问题）批处理作业调度问题3 3广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4 4页页6.1分支限界法的基本思想分支限界法的基本思想分支限界法与回溯法分支限界法与回溯法（1）求解目标：）求解目标：回溯法的求解目标是找出解空间树回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是

3、在满足约标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。束条件的解中找出在某种意义下的最优解。（2）搜索方式的不同：）搜索方式的不同：回溯法以深度优先的方式回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。小耗费优先的方式搜索解空间树。4 4广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第5 5页页6.1分支限界法的基本思想分支限界法的基本思想 分支限界法常以广度优先或以最小耗费（最大分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问

4、题的解空间树。效益）优先的方式搜索问题的解空间树。此后，从活结点表中取下一结点成为当前扩展此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。续到找到所需的解或活结点表为空时为止。在分支限界法中，每一个活结点只有一次机会成在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余

5、儿子结点解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。被加入活结点表中。5 5广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第6 6页页6.1分支限界法的基本思想分支限界法的基本思想常见的两种分支限界法常见的两种分支限界法（1 1）队列式队列式(FIFO)FIFO)分支限界法分支限界法 按照队列先进先出（按照队列先进先出（FIFOFIFO）原则选取下一原则选取下一个节点为扩展节点。个节点为扩展节点。（2 2）优先队列式分支限界法）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。

6、最高的节点成为当前扩展节点。6 6广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第7 7页页6.2单源最短路径问题单源最短路径问题1.问题描述问题描述 下面以一个例子来说明单源最短路径问题：下面以一个例子来说明单源最短路径问题：在在下图所给的有向图下图所给的有向图G G中，每一边都有一个非负边权。中，每一边都有一个非负边权。要求图要求图G G的从源顶点的从源顶点s s到目标顶点到目标顶点t t之间的最短路径。之间的最短路径。7 7广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第8 8页页6.2单源最短路径问题单源最短路径问题1.问题描述问题描

7、述 下图是用优先队列式分支限界法解有向图下图是用优先队列式分支限界法解有向图G G的单的单源最短路径问题产生的解空间树。其中，每一个结点源最短路径问题产生的解空间树。其中，每一个结点旁边的数字表示该结点所对应的当前路长。旁边的数字表示该结点所对应的当前路长。8 8广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第9 9页页2.算法思想算法思想 解单源最短路径问题的优先队列式分支限界法用解单源最短路径问题的优先队列式分支限界法用一极小堆来存储活结点表。其优先级是结点所对应的一极小堆来存储活结点表。其优先级是结点所对应的当前路长。当前路长。算法从图算法从图G G的源顶点的源

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

9、优先队列中。这个则将该顶点作为活结点插入到活结点优先队列中。这个结点的扩展过程一直继续到活结点优先队列为空时为止。结点的扩展过程一直继续到活结点优先队列为空时为止。9 9广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1010页页3.剪枝策略剪枝策略 在在算算法法扩扩展展结结点点的的过过程程中中，一一旦旦发发现现一一个个结结点点的的下下界界不不小小于于当当前前找找到到的的最最短短路路长长，则则算算法法剪剪去去以以该该结结点为根的子树。点为根的子树。在在算算法法中中，利利用用结结点点间间的的控控制制关关系系进进行行剪剪枝枝。从从源源顶顶点点s s出出发发，2 2条条不不

10、同同路路径径到到达达图图G G的的同同一一顶顶点点。由由于于两两条条路路径径的的路路长长不不同同，因因此此可可以以将将路路长长长长的的路路径径所所对对应的树中的结点为根的子树剪去。应的树中的结点为根的子树剪去。1010广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1111页页6.2单源最短路径问题单源最短路径问题 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

11、;/加入活结点优先队列加入活结点优先队列 MinHeapNode N;N.i=j;N.length=distj;H.Insert(N);try H.DeleteMin(E);/取下一扩展结点取下一扩展结点 catch(OutOfBounds)break;/优先队列空优先队列空 顶点顶点I I和和j j间有边，且间有边，且此路径长小于原先从此路径长小于原先从原点到原点到j j的路径长的路径长 1111广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1212页页6.3 装载问题装载问题1.问题描述有有一一批批共共个个集集装装箱箱要要装装上上2 2艘艘载载重重量量分分别别为

12、为C1C1和和C2C2的的轮轮船船，其中集装箱其中集装箱i i的重量为的重量为WiWi，且且装载问题要求确定是否有一个合理的装载方案可将这装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这个集装箱装上这2 2艘轮船。如果有，找出一种装载方案。艘轮船。如果有，找出一种装载方案。容容易易证证明明：如如果果一一个个给给定定装装载载问问题题有有解解，则则采采用用下下面面的策略可得到最优装载方案。的策略可得到最优装载方案。(1)(1)首先将第一艘轮船尽可能装满；首先将第一艘轮船尽可能装满；(2)(2)将剩余的集装箱装上第二艘轮船。将剩余的集装箱装上第二艘轮船。1212广州大学华软软件学院广州大

13、学华软软件学院 算法分析与设计算法分析与设计第第1313页页6.3 装载问题装载问题2.队列式分支限界法队列式分支限界法 在在算算法法的的whilewhile循循环环中中，首首先先检检测测当当前前扩扩展展结结点点的的左左儿儿子子结结点点是是否否为为可可行行结结点点。如如果果是是则则将将其其加加入入到到活活结结点点队队列列中中。然然后后将将其其右右儿儿子子结结点点加加入入到到活活结结点点队队列列中中(右右儿儿子子结结点点一一定定是是可可行行结结点点)。2 2个个儿儿子子结结点点都都产产生生后后，当前扩展结点被舍弃。当前扩展结点被舍弃。活活结结点点队队列列中中的的队队首首元元素素被被取取出出作作为

14、为当当前前扩扩展展结结点点，由由于于队队列列中中每每一一层层结结点点之之后后都都有有一一个个尾尾部部标标记记-1-1，故故在在取取队队首首元元素素时时，活活结结点点队队列列一一定定不不空空。当当取取出出的的元元素素是是-1-1时时，再再判判断断当当前前队队列列是是否否为为空空。如如果果队队列列非非空空，则则将将尾尾部部标标记记-1-1加加入入活活结结点点队队列列，算算法法开开始始处处理理下下一一层层的的活活结点。结点。1313广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1414页页2.队列式分支限界法队列式分支限界法while(true)/检查左儿子结点检查左儿子

15、结点 if(Ew+wi=c)/xi=1 EnQueue(Q,Ew+wi,bestw,i,n);/右儿子结点总是可行的右儿子结点总是可行的 EnQueue(Q,Ew,bestw,i,n);/xi=0 Q.Delete(Ew);/取下一扩展结点取下一扩展结点 if(Ew=-1)/同层结点尾部同层结点尾部 if(Q.IsEmpty()return bestw;Q.Add(-1);/同层结点尾部标志同层结点尾部标志 Q.Delete(Ew);/取下一扩展结点取下一扩展结点 i+;/进入下一层进入下一层 1414广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1515页页6.3

16、 装载问题装载问题3.算法的改进算法的改进 节点的左子树表示将此集装箱装上船，右子树表示节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设不将此集装箱装上船。设bestwbestw是当前最优解；是当前最优解；ewew是当是当前扩展结点所相应的重量；前扩展结点所相应的重量；r r是剩余集装箱的重量。则是剩余集装箱的重量。则当当ew+rew+r bestwbestw时，可将其右子树剪去，因为此时若要时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。船装最多集装箱，就应该把此箱装上船。另外，为了确保右子树成功剪枝，应该在算法每另外，为了确保右子树成功剪枝，应该在算

17、法每一次进入左子树的时候更新一次进入左子树的时候更新bestwbestw的值。的值。1515广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1616页页3.算法的改进算法的改进/检查左儿子结点检查左儿子结点 Type wt=Ew+wi;/左儿子结点的重量左儿子结点的重量 if(wt bestw)bestw=wt;/加入活结点队列加入活结点队列 if(i bestw&i 0;j-)bestxj=bestE-LChild;bestE=bestE-parent;1818广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第1919页页6.3 装载问题装载

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

19、中叶结点所相应的载重量与。子集树中叶结点所相应的载重量与其优先级相同。其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。最优解。此时可终止算法。1919广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2020页页6.4 布线问题布线问题1.算法思想算法思想 解解此此问问题题的的队队列列式式分分支支限限界界法法从从起起始始位位置置a a开开始始将将它它作作为为第第一一个个扩扩展展结结点点。与与该该扩扩

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

21、即即加加入入剪剪枝的广度优先搜索。枝的广度优先搜索。2020广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2121页页6.4 布线问题布线问题Position offset4;offset0.row=0;offset0.col=1;/右右 offset1.row=1;offset1.col=0;/下下 offset2.row=0;offset2.col=-1;/左左 offset3.row=-1;offset3.col=0;/上上定义移动方向的定义移动方向的相对位移相对位移 for(int i=0;i=m+1;i+)grid0i=gridn+1i=1;/顶部和底部顶

22、部和底部 for(int i=0;i=n+1;i+)gridi0=gridim+1=1;/左翼和右翼左翼和右翼设置边界的设置边界的围墙围墙2121广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2222页页6.4 布线问题布线问题for(int i=0;i NumOfNbrs;i+)nbr.row=here.row+offseti.row;nbr.col=here.col+offseti.col;if(gridnbr.rownbr.col=0)/该方格未标记该方格未标记 gridnbr.rownbr.col =gridhere.rowhere.col+1;if(nbr

23、.row=finish.row)&(nbr.col=finish.col)break;/完成布线完成布线 Q.Add(nbr);找到目标位置找到目标位置后，可以通过后，可以通过回溯方法找到回溯方法找到这条最短路径。这条最短路径。2222广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2323页页6.5 0-1背包问题背包问题算法的思想算法的思想 首先，要对输入数据进行预处理，将各物品依其单首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。位重量价值从大到小进行排列。节点的优先级由已装袋节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品

24、装满剩的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价值和。余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子性。如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。才将它加入子集树和活结点优先队列。当扩展到叶节当扩展到叶节点时为问题的最优值。点时为问题的最优值。2323广州大学华软软

25、件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2424页页6.5 0-1背包问题背包问题上界函数上界函数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为上界函数为上界函数2424广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2525页页6.5 0-1背包问题背包问题 while(i!=n+1

26、)/非叶结点非叶结点 /检查当前扩展结点的左儿子结点检查当前扩展结点的左儿子结点 Typew wt=cw+wi;if(wt bestp)bestp=cp+pi;AddLiveNode(up,cp+pi,cw+wi,true,i+1);up=Bound(i+1);/检查当前扩展结点的右儿子结点检查当前扩展结点的右儿子结点 if(up=bestp)/右子树可能含最优解右子树可能含最优解 AddLiveNode(up,cp,cw,false,i+1);/取下一个扩展节点（略）取下一个扩展节点（略）分支限界搜分支限界搜索过程索过程2525广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析

27、与设计第第2626页页分支限界法解分支限界法解0-1背包问题背包问题n=3,w=16,15,15,p=45,25,25,c=30FIFO队列：队列：A活结点队列：BCB,CDEJKFGLMNOC,EE,F,GF,GG 4550252502626广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2727页页 一般情况下，解空间树中第一般情况下，解空间树中第i层的每个结点，都代表了对物层的每个结点，都代表了对物品品1i做出的某种特定选择，这个特定选择由从根结点到该结做出的某种特定选择，这个特定选择由从根结点到该结点的路径唯一确定：左分支表示装入物品，右分支表示不装入点的路径

28、唯一确定：左分支表示装入物品，右分支表示不装入物品。对于第物品。对于第i层的某个结点，假设背包中已装入物品的重量是层的某个结点，假设背包中已装入物品的重量是w，获得，获得的价值是的价值是v，计算该结点的目标函数上界的一个简单方，计算该结点的目标函数上界的一个简单方法是把已经装入背包中的物品取得的价值法是把已经装入背包中的物品取得的价值v，加上背包剩余容量，加上背包剩余容量c-w与剩下物品的最大单位重量价值与剩下物品的最大单位重量价值vi+1/wi+1的积，于是，得到限的积，于是，得到限界函数：界函数：2727广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第2828页页

29、分支限界法解分支限界法解0-1背包问题背包问题n=3,w=16,15,15,p=45,25,25,c=30FIFO队列，带上界函数。队列，带上界函数。A活结点队列：BCB,CDEJKFGLMC,EE,F,GF,GG 45502568.3050068.3050452545504545=4525bestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。3333广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3434页页6.6 最大团问题最大团问题3.算法思想 算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为

30、当前扩展结点。对于子集树中的叶结点，有upperSizecliqueSize。此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。3434广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3535页页6.7 旅行售货员问题旅行售货员问题1.问题描述问题描述 某售货员要到若干城市去推销商品，已知各城市之间的某售货员要到若干城市去推销商品，已知各城市之间的路程路程(或旅费或旅费)。他要选定一条从驻地出发，经过每个城市一。他要选定一条从驻地出发，经过每个城市一次，最后回到驻地

31、的路线，使总的路程次，最后回到驻地的路线，使总的路程(或总旅费或总旅费)最小。最小。路线是一个带权图。图中各边的费用（权）为正数。图路线是一个带权图。图中各边的费用（权）为正数。图的一条周游路线是包括的一条周游路线是包括V V中的每个顶点在内的一条回路。周中的每个顶点在内的一条回路。周游路线的费用是这条路线上所有边的费用之和。游路线的费用是这条路线上所有边的费用之和。旅行售货员问题的解空间可以组织成一棵树，从树的根旅行售货员问题的解空间可以组织成一棵树，从树的根结点到任一叶结点的路径定义了图的一条周游路线。结点到任一叶结点的路径定义了图的一条周游路线。旅行售旅行售货员问题要在图货员问题要在图G

32、 G中找出费用最小的周游路线。中找出费用最小的周游路线。3535广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3636页页6.7 旅行售货员问题旅行售货员问题2.算法描述算法描述 算法开始时创建一个最小堆，用于表示活结点优先算法开始时创建一个最小堆，用于表示活结点优先队列。堆中每个结点的子树费用的下界队列。堆中每个结点的子树费用的下界lcostlcost值是优先队值是优先队列的优先级。接着算法计算出图中每个顶点的最小费用列的优先级。接着算法计算出图中每个顶点的最小费用出边并用出边并用minoutminout记录。如果所给的有向图中某个顶点没记录。如果所给的有向图中某

33、个顶点没有出边，则该图不可能有回路，算法即告结束。如果每有出边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的个顶点都有出边，则根据计算出的minoutminout作算法初始化。作算法初始化。算法的算法的whilewhile循环体完成对排列树内部结点的扩展。对循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分于当前扩展结点，算法分2 2种情况进行处理：种情况进行处理：3636广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3737页页6.7 旅行售货员问题旅行售货员问题2.算法描述算法描述 1 1、首先考虑、首先考虑s=n-2s=n-2

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

35、中选取的顶点xixi，且且(xsxs，xi)xi)是所给有向图是所给有向图G G中的一条边。对中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀于当前扩展结点的每一个可行儿子结点，计算出其前缀(x0:sx0:s，xi)xi)的费用的费用cccc和相应的下界和相应的下界lcostlcost。当当lcostbestclcostbestc时，将这个可行儿子结点插入到活结点优时，将这个可行儿子结点插入到活结点优先队列中。先队列中。3737广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3838页页6.7 旅行售货员问题旅行售货员问题2.算法描述算法描述 算法中算法

36、中whilewhile循环的终止条件是排列树的一个叶结点循环的终止条件是排列树的一个叶结点成为当前扩展结点。当成为当前扩展结点。当s=n-1s=n-1时，已找到的回路前缀是时，已找到的回路前缀是x0:n-1x0:n-1，它已包含图它已包含图G G的所有的所有n n个顶点。因此，当个顶点。因此，当s=n-s=n-1 1时，相应的扩展结点表示一个叶结点。此时该叶结点时，相应的扩展结点表示一个叶结点。此时该叶结点所相应的回路的费用等于所相应的回路的费用等于cccc和和lcostlcost的值。剩余的活结的值。剩余的活结点的点的lcostlcost值不小于已找到的回路的费用。它们都不可值不小于已找到的

37、回路的费用。它们都不可能导致费用更小的回路。因此已找到的叶结点所相应的能导致费用更小的回路。因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可以结束。回路是一个最小费用旅行售货员回路，算法可以结束。算法结束时返回找到的最小费用，相应的最优解由算法结束时返回找到的最小费用，相应的最优解由数组数组v v给出。给出。3838广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第3939页页分支限界法解旅行售货员问题分支限界法解旅行售货员问题1234302010654FIFO队列：队列：活结点队列：BCDEGIKFHJMOQLNP222223333344444592

38、525666659C,D,E D,E,F,GE,F,G,H,I F,G,H,I,J,K G,H,I,J,K H,I,J,K I,J,K J,K K 3939广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4040页页某某条条路路径径的的一一些些边边被被确确定定后后，就就可可以以并并入入这这些些信信息息并并计计算算部部分分解解的的目目标标函函数数值值的的下下界界。一一般般情情况况下下，对对于于一一个个正正在在生生成成的的路路径径，假假设设已已确确定定的的顶顶点点集集合合U=(r1,r2,rk)，即即路路径径上上已已确确定了定了k个顶点个顶点。该部分解的目标函数值的计算方

39、法如下：该部分解的目标函数值的计算方法如下：4040广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4141页页分支限界法解旅行售货员问题分支限界法解旅行售货员问题1234302010654FIFO队列，带下界函数。队列，带下界函数。活结点队列：BCDEGIKFHJMLNP222333334444459252566C,D,E D,E,F,GE,F,G,H,I F,G,H,I,J,K G,H,I,J,K H,I,J,K I,J,K J,K K 441012010118101441014959202524254141广州大学华软软件学院广州大学华软软件学院 算法分析与设计

40、算法分析与设计第第4242页页分支限界法解旅行售货员问题分支限界法解旅行售货员问题1234302010654最小费用优先队列：最小费用优先队列：活结点队列：BCDEGIKFHJMOQLNP2222233333444443064402624351114592525666659E,D,C D,J,K,C H,J,K,I,C J,K,I,C K,I,C I,C C F,G G 4242广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4343页页分支限界法解旅行售货员问题分支限界法解旅行售货员问题1234302010654最小费用优先队列，带下界函数。最小费用优先队列，带下界

41、函数。活结点队列：CDEIKHJNP2223334443064262411142525E,D,C D,J,K,C H,J,K,I,C J,K,N,I,C K,N,P,I,C N,P,I,C1810120101201012425N为叶结点，结束。B4343广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4444页页6.8 电路板排列问题电路板排列问题算法描述算法描述 算法开始时，将排列树的根结点置为当前扩展结点。算法开始时，将排列树的根结点置为当前扩展结点。在在do-whiledo-while循环体内算法依次从活结点优先队列中取出循环体内算法依次从活结点优先队列中取出具

42、有最小具有最小cdcd值的结点作为当前扩展结点，并加以扩展。值的结点作为当前扩展结点，并加以扩展。首先考虑首先考虑s=n-1s=n-1的情形，当前扩展结点是排列树中的的情形，当前扩展结点是排列树中的一个叶结点的父结点。一个叶结点的父结点。x x表示相应于该叶结点的电路板排表示相应于该叶结点的电路板排列。计算出与列。计算出与x x相应的密度并在必要时更新当前最优值和相应的密度并在必要时更新当前最优值和相应的当前最优解相应的当前最优解。当当sn-1sn-1时，算法依次产生当前扩展结点的所有儿子时，算法依次产生当前扩展结点的所有儿子结点。对于当前扩展结点的每一个儿子结点结点。对于当前扩展结点的每一个

43、儿子结点nodenode，计算计算出其相应的密度出其相应的密度node.cdnode.cd。当当node.cdbestdnode.cdbestd时，将该儿时，将该儿子结点子结点N N插入到活结点优先队列中。插入到活结点优先队列中。4444广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4545页页6.8 电路板排列问题电路板排列问题算法描述算法描述do/结点扩展结点扩展 if(E.s=n-1)/仅一个儿子结点仅一个儿子结点 int ld=0;/最后一块电路板的密度最后一块电路板的密度 for(int j=1;j=m;j+)ld+=BE.xnj;if(ld bestd)

44、/密度更小的电路板排列密度更小的电路板排列 delete bestx;bestx=E.x;bestd=max(ld,E.cd);S=n-1S=n-1的情况，的情况，计算出此时的密计算出此时的密度和度和bestdbestd进行进行比较。比较。4545广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4646页页6.8 电路板排列问题电路板排列问题算法描述算法描述else /产生当前扩展结点的所有儿子结点产生当前扩展结点的所有儿子结点 for(int i=E.s+1;i=n;i+)BoardNode N;N.now=new int m+1;for(int j=1;j=m;j

45、+)/新插入的电路板新插入的电路板 N.nowj=E.nowj+BE.xij;4646广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第4747页页6.8 电路板排列问题电路板排列问题int ld=0;/新插入电路板的密度 for(int j=1;j 0&totalj!=N.nowj)ld+;N.cd=max(ld,E.cd);if(N.cd bestd)/可能产生更好的叶结点 N.x=new int n+1;N.s=E.s+1;for(int j=1;j=k=r r+1+1时依非减序排列，时依非减序排列，S1S1则取得极小值则取得极小值。同理如果选择同理如果选择P P

46、k k使使t t2pk2pk依非减序排列，依非减序排列，则则S2S2取得极小值。取得极小值。这可以作为优先队列式分支限界法中的限界函数。这可以作为优先队列式分支限界法中的限界函数。4949广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第5050页页6.9 批处理作业调度问题批处理作业调度问题3.算法描述算法描述 算法的算法的whilewhile循环完成对排列树内部结点的有序扩展。循环完成对排列树内部结点的有序扩展。在在whilewhile循环体内算法依次从活结点优先队列中取出具有循环体内算法依次从活结点优先队列中取出具有最小最小bbbb值（完成时间和下界）的结点作为当

47、前扩展结点，值（完成时间和下界）的结点作为当前扩展结点，并加以扩展。并加以扩展。5050广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第5151页页6.9 批处理作业调度问题批处理作业调度问题3.算法描述算法描述 首先考虑首先考虑E E.s=n.s=n的情形，当前扩展结点的情形，当前扩展结点E E是排列树中的是排列树中的叶结点。叶结点。E.sf2E.sf2是相应于该叶结点的完成时间和。当是相应于该叶结点的完成时间和。当E.sf2 E.sf2 bestc bestc时更新当前最优值时更新当前最优值bestcbestc和相应的当前最优解和相应的当前最优解bestxbest

48、x。当当E.snE.sn时，算法依次产生当前扩展结点时，算法依次产生当前扩展结点E E的所有儿子的所有儿子结点。对于当前扩展结点的每一个儿子结点结点。对于当前扩展结点的每一个儿子结点nodenode，计算出计算出其相应的完成时间和的下界其相应的完成时间和的下界bbbb。当当bb bestcbb bestc时，将该儿时，将该儿子结点插入到活结点优先队列中。而当子结点插入到活结点优先队列中。而当bbbb bestc bestc时，可时，可将结点将结点nodenode舍去。舍去。5151广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第5252页页6.9 批处理作业调度问题批

49、处理作业调度问题 while(E.s=n)if(E.s=n)/叶结点 if(E.sf2 bestc)bestc=E.sf2;for(int i=0;i n;i+)bestxi=E.xi;delete E.x;3.算法描述 当当E.sf2bestcE.sf2bestc时，更时，更新当前最优值新当前最优值bestcbestc和相和相应的最优解应的最优解bestxbestx5252广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第5353页页6.9 批处理作业调度问题批处理作业调度问题3.算法描述else/产生当前扩展结点的儿子结点 for(int i=E.s;i n;i+)Swap(E.xE.s,E.xi);int f1,f2;int bb=Bound(E,f1,f2,y);if(bb bestc)MinHeapNode N;N.NewNode(E,f1,f2,bb,n);H.Insert(N);Swap(E.xE.s,E.xi);delete E.x;/完成结点扩展当当bbbestcbbbestc时，将儿时，将儿子结点插入到活结点子结点插入到活结点优先队列中优先队列中5353广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计第第5454页页小结小结5454广州大学华软软件学院广州大学华软软件学院 算法分析与设计算法分析与设计