计算机算法设计与分析 第6章.ppt

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

1、第6章 分支限界法1学习要点学习要点理解分支限界法的剪枝搜索策略。掌握分支限界法的算法框架（1）队列式(FIFO)分支限界法（2）优先队列式分支限界法 通过应用范例学习分支限界法的设计策略。（1）单源最短路径问题（2）装载问题；（3）布线问题（4）0-1背包问题；（5）最大团问题；（6）旅行售货员问题（7）电路板排列问题（8）批处理作业调度问题26.1 分支限界法的基本思想分支限界法的基本思想分支限界法与回溯法分支限界法与回溯法（1）求解目标：）求解目标：回溯法的求解目标是找出解空间树中满足约束条回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的

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

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

4、点被加入活结点表中。余儿子结点被加入活结点表中。46.1 分支限界法的基本思想分支限界法的基本思想常见的两种分支限界法常见的两种分支限界法（1 1）队列式队列式(FIFO)FIFO)分支限界法分支限界法 按照队列先进先出（按照队列先进先出（FIFOFIFO）原则选取下一个节点原则选取下一个节点为扩展节点。为扩展节点。（2 2）优先队列式分支限界法）优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。点成为当前扩展节点。56.2 单源最短路径问题单源最短路径问题1.问题描述问题描述 下面以一个例子来说明单源最短路径问题

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

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

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

8、则算法剪去以该结点为根的子树。于当前找到的最短路长，则算法剪去以该结点为根的子树。在在算算法法中中，利利用用结结点点间间的的控控制制关关系系进进行行剪剪枝枝。从从源源顶顶点点s s出出发发，2 2条条不不同同路路径径到到达达图图G G的的同同一一顶顶点点。由由于于两两条条路路径径的的路路长长不不同同，因因此此可可以以将将路路长长长长的的路路径径所所对对应应的的树树中中的的结结点点为为根根的的子子树树剪去。剪去。96.2 单源最短路径问题单源最短路径问题 while(true)for(int j=1;j=n;j+)if(cE.ijinf)&(E.length+cE.ijdistj)/顶点顶点i到

9、顶点到顶点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(OutOfBounds)break;/优先队列空优先队列空 顶点顶点i i和和j j间有边，且此间有边，且此路径长小于原先从原点路径长小于原先从原点到到j j的路径长的路径长 106.3 装载问题装载问题1.问题描述问题描述有一批共个集装箱要装上有一批共个集装箱要装上

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

11、116.3 装载问题装载问题2.队列式分支限界法队列式分支限界法 在在算算法法的的whilewhile循循环环中中，首首先先检检测测当当前前扩扩展展结结点点的的左左儿儿子子结结点点是是否否为为可可行行结结点点。如如果果是是则则将将其其加加入入到到活活结结点点队队列列中中。然然后后将将其其右右儿儿子子结结点点加加入入到到活活结结点点队队列列中中(右右儿儿子子结结点点一一定定是是可可行结点行结点)。2 2个儿子结点都产生后，当前扩展结点被舍弃。个儿子结点都产生后，当前扩展结点被舍弃。活活结结点点队队列列中中的的队队首首元元素素被被取取出出作作为为当当前前扩扩展展结结点点，由由于于队队列列中中每每一

12、一层层结结点点之之后后都都有有一一个个尾尾部部标标记记-1-1，故故在在取取队队首首元元素素时时，活活结结点点队队列列一一定定不不空空。当当取取出出的的元元素素是是-1-1时时，再再判判断断当当前前队队列列是是否否为为空空。如如果果队队列列非非空空，则则将将尾尾部部标标记记-1-1加加入入活活结结点点队队列，算法开始处理下一层的活结点。列，算法开始处理下一层的活结点。126.3 装载问题装载问题2.队列式分支限界法队列式分支限界法while(true)/检查左儿子结点检查左儿子结点 if(Ew+wi=c)/xi=1 EnQueue(Q,Ew+wi,bestw,i,n);/右儿子结点总是可行的右

13、儿子结点总是可行的 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+;/进入下一层进入下一层 136.3 装载问题装载问题3.算法的改进算法的改进 节点的左子树表示将此集装箱装上船，右子树表示不将节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设此集装箱装上船。设bestwbestw是当前最优解

14、；是当前最优解；ewew是当前扩展结点是当前扩展结点所相应的重量；所相应的重量；r r是剩余集装箱的重量。则当是剩余集装箱的重量。则当ew+rew+r bestwbestw时，时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。把此箱装上船。另外，为了确保右子树成功剪枝，应该在算法每一次进另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新入左子树的时候更新bestwbestw的值。的值。146.3 装载问题装载问题3.算法的改进算法的改进/检查左儿子结点检查左儿子结点 Type wt=Ew+wi;/左儿子结点

15、的重左儿子结点的重量量 if(wt bestw)bestw=wt;/加入活结点队列加入活结点队列 if(i bestw&i 0;j-)bestxj=bestE-LChild;bestE=bestE-parent;176.3 装载问题装载问题5.优先队列式分支限界法优先队列式分支限界法 解装载问题的优先队列式分支限界法用最大优先队列存储解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。活结点活结点表。活结点x x在优先队列中的优先级定义为从根结点到结在优先队列中的优先级定义为从根结点到结点点x x的路径所相应的载重量再加上剩余集装箱的重量之和。的路径所相应的载重量再加上剩余集装箱的重量

16、之和。优先队列中优先级最大的活结点成为下一个扩展结点。以优先队列中优先级最大的活结点成为下一个扩展结点。以结点结点x x为根的子树中所有结点相应的路径的载重量不超过为根的子树中所有结点相应的路径的载重量不超过它的优它的优先级先级。子集树中叶结点所相应的载重量与其优先级相同。子集树中叶结点所相应的载重量与其优先级相同。在优先队列式分支限界法中，一旦有一个叶结点成为当前在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。可终止算法。186.4 布线问题布线问题1.算法思想算法思想

17、解解此此问问题题的的队队列列式式分分支支限限界界法法从从起起始始位位置置a a开开始始将将它它作作为为第第一一个个扩扩展展结结点点。与与该该扩扩展展结结点点相相邻邻并并且且可可达达的的方方格格成成为为可可行行结结点点被被加加入入到到活活结结点点队队列列中中，并并且且将将这这些些方方格格标标记记为为1 1，即从起始方格，即从起始方格a a到这些方格的距离为到这些方格的距离为1 1。接接着着，算算法法从从活活结结点点队队列列中中取取出出队队首首结结点点作作为为下下一一个个扩扩展展结结点点，并并将将与与当当前前扩扩展展结结点点相相邻邻且且未未标标记记过过的的方方格格标标记记为为2 2，并并存存入入活

18、活结结点点队队列列。这这个个过过程程一一直直继继续续到到算算法法搜搜索索到到目目标标方方格格b b或或活活结结点点队队列列为为空空时时为为止止。即即加加入入剪剪枝枝的的广广度度优优先先搜索。搜索。196.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

19、+)grid0i=gridn+1i=1;/顶部和底部顶部和底部 for(int i=0;i=n+1;i+)gridi0=gridim+1=1;/左翼和右翼左翼和右翼设置边界的围墙设置边界的围墙206.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.row=finish.row)&(

20、nbr.col=finish.col)break;/完成布线完成布线 Q.Add(nbr);找到目标位置后，可以通过回溯方法找到这条最短路径。找到目标位置后，可以通过回溯方法找到这条最短路径。216.5 0-1背包问题背包问题算法的思想算法的思想 首先，要对输入数据进行预处理，将各物品依其单位首先，要对输入数据进行预处理，将各物品依其单位重量价值从大到小进行排列。重量价值从大到小进行排列。在下面描述的优先队列分支限界法中，节点的优先级在下面描述的优先队列分支限界法中，节点的优先级由已装袋的物品价值加上剩下的最大单位重量价值的物品由已装袋的物品价值加上剩下的最大单位重量价值的物品装满剩余容量的价

21、值和。装满剩余容量的价值和。算法首先检查当前扩展结点的左儿子结点的可行性。算法首先检查当前扩展结点的左儿子结点的可行性。如果该左儿子结点是可行结点，则将它加入到子集树和活如果该左儿子结点是可行结点，则将它加入到子集树和活结点优先队列中。当前扩展结点的右儿子结点一定是可行结点优先队列中。当前扩展结点的右儿子结点一定是可行结点，仅当右儿子结点满足上界约束时才将它加入子集树结点，仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列。和活结点优先队列。当扩展到叶节点时为问题的最优值。当扩展到叶节点时为问题的最优值。226.5 0-1背包问题背包问题上界函数上界函数while(i=n&wi=cl

22、eft)/n表示物品总数，表示物品总数，cleft为剩余空间为剩余空间 cleft-=wi;/wi表示表示i所占空间所占空间 b+=pi;/pi表示表示i的价值的价值 i+;if(i=n)b+=pi/wi*cleft;/装填剩余容量装满背包装填剩余容量装满背包return b;/b为上界函数为上界函数236.5 0-1背包问题背包问题 while(i!=n+1)/非叶结点非叶结点 /检查当前扩展结点的左儿子结点检查当前扩展结点的左儿子结点 Typew wt=cw+wi;if(wt bestp)bestp=cp+pi;AddLiveNode(up,cp+pi,cw+wi,true,i+1);up

23、=Bound(i+1);/检查当前扩展结点的右儿子结点检查当前扩展结点的右儿子结点 if(up=bestp)/右子树可能含最优解右子树可能含最优解 AddLiveNode(up,cp,cw,false,i+1);/取下一个扩展节点（略）取下一个扩展节点（略）分支限界搜索过分支限界搜索过程程246.6 最大团问题最大团问题 给定无向图给定无向图G=(VG=(V，E)E)。如果如果U U V V，且对任意且对任意u u，v v U U有有(u u，v)v)E E，则称则称U U是是G G的完全子图。的完全子图。G G的完全子图的完全子图U U是是G G的团当且仅当的团当且仅当U U不包不包含在含在

24、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的最大团。的最大团。1.问题描述问题描述256.6 最大团问题最大团问题2.上界函数上界函数用变量用变量cliqueSizecliqueSize表示与该

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

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

27、相应应的的左左儿儿子子结结点点是是可可行行结结点点，将将它它加加入入到到子子集集树树中中并并插入活结点优先队列，否则就不是可行结点。插入活结点优先队列，否则就不是可行结点。接接 着着 继继 续续 考考 察察 当当 前前 扩扩 展展 结结 点点 的的 右右 儿儿 子子 结结 点点。当当upperSizeupperSize bestnbestn时时，右右子子树树中中可可能能含含有有最最优优解解，此此时时将将右右儿儿子子结结点加入到子集树中并插入到活结点优先队列中。点加入到子集树中并插入到活结点优先队列中。276.6 最大团问题最大团问题3.算法思想算法思想 算法的算法的whilewhile循环的终

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

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

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

31、计算出图中每个顶点的最小费用出边并用着算法计算出图中每个顶点的最小费用出边并用minoutminout记录。如记录。如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。如果每个顶点都有出边，则根据计算出的法即告结束。如果每个顶点都有出边，则根据计算出的minoutminout作作算法初始化。算法初始化。算法的算法的whilewhile循环体完成对排列树内部结点的扩展。对于当前循环体完成对排列树内部结点的扩展。对于当前扩展结点，算法分扩展结点，算法分2 2种情况进行处理：种情况进行处理：306.7 旅行售货员问题旅行售货员

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

33、儿子结点是从剩余顶点剩余顶点xs+1:n-1xs+1:n-1中选取的顶点中选取的顶点xixi，且且(xsxs，xixi)是所给是所给有向图有向图G G中的一条边。对于当前扩展结点的每一个可行儿子结点，中的一条边。对于当前扩展结点的每一个可行儿子结点，计算出其前缀计算出其前缀(x0:sx0:s，xi)xi)的费用的费用cccc和相应的下界和相应的下界lcostlcost。当当lcostlcost bestcbestc时，将这个可行儿子结点插入到活结点优先队列中。时，将这个可行儿子结点插入到活结点优先队列中。316.7 旅行售货员问题旅行售货员问题2.算法描述算法描述 算法中算法中whilewhi

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

35、费用更小的回路。因此已找到的叶结点所相应的们都不可能导致费用更小的回路。因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可以结束。回路是一个最小费用旅行售货员回路，算法可以结束。算法结束时返回找到的最小费用，相应的最优解由数组算法结束时返回找到的最小费用，相应的最优解由数组v v给出。给出。326.8 电路板排列问题电路板排列问题算法描述算法描述 算法开始时，将排列树的根结点置为当前扩展结点。在算法开始时，将排列树的根结点置为当前扩展结点。在do-do-whilewhile循环体内算法依次从活结点优先队列中取出具有最小循环体内算法依次从活结点优先队列中取出具有最小cdcd值的值

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

37、算出其相应的密度计算出其相应的密度node.cdnode.cd。当当node.cdnode.cd bestdbestd时，将该儿子结点时，将该儿子结点N N插入到活结点优先插入到活结点优先队列中。队列中。336.8 电路板排列问题电路板排列问题算法描述算法描述do/结点扩展结点扩展 if(E.s=n-1)/仅一个儿子结点仅一个儿子结点 int ld=0;/最后一块电路板的密度最后一块电路板的密度 for(int j=1;j=m;j+)ld+=BE.xnj;if(ld bestd)/密度更小的电路板排列密度更小的电路板排列 delete bestx;bestx=E.x;bestd=max(ld,

38、E.cd);S=n-1S=n-1的情况，计算出的情况，计算出此时的密度和此时的密度和bestdbestd进进行比较。行比较。346.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+)/新插入的电路板新插入的电路板 N.nowj=E.nowj+BE.xij;356.8 电路板排列问题电路板排列问题int ld=0;/新插入电路板的密度新插入电路板的密度 for(int j=1;j 0

39、&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 Pk k使使t t2pk2pk依非减序排列，则依非减序排列，则S2S2取得极小值。取得极小值。这可以作为优先队列式分支限界法中的限界函数。这可以作为优先队列式分支限界法中的限界函数。386.9 批处理作业调度问题批处理作业调度问题3.算法描述算法描述 算法的算

40、法的whilewhile循环完成对排列树内部结点的有序扩展。在循环完成对排列树内部结点的有序扩展。在whilewhile循环体内算法依次从活结点优先队列中取出具有最小循环体内算法依次从活结点优先队列中取出具有最小bbbb值（完成时值（完成时间和下界）的结点作为当前扩展结点，并加以扩展。间和下界）的结点作为当前扩展结点，并加以扩展。首先考虑首先考虑E E.s.s=n=n的情形，当前扩展结点的情形，当前扩展结点E E是排列树中的叶结点。是排列树中的叶结点。E.sf2E.sf2是相应于该叶结点的完成时间和。当是相应于该叶结点的完成时间和。当E.sf2 E.sf2 bestcbestc时更新当时更新当

41、前最优值前最优值bestcbestc和相应的当前最优解和相应的当前最优解bestxbestx。当当E.sE.snn时，算法依次产生当前扩展结点时，算法依次产生当前扩展结点E E的所有儿子结点。对的所有儿子结点。对于当前扩展结点的每一个儿子结点于当前扩展结点的每一个儿子结点nodenode，计算出其相应的完成时间计算出其相应的完成时间和的下界和的下界bbbb。当当bb bb bestcbestc时，将该儿子结点插入到活结点优先队时，将该儿子结点插入到活结点优先队列中。而当列中。而当bbbb bestcbestc时，可将结点时，可将结点nodenode舍去。舍去。396.9 批处理作业调度问题批处

42、理作业调度问题 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.sf2E.sf2bestcbestc时，更时，更新当前最优值新当前最优值bestcbestc和相和相应的最优解应的最优解bestxbestx406.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;/完成结点扩展完成结点扩展当当bbbbbestcbestc时，将儿时，将儿子结点插入到活结点子结点插入到活结点优先队列中优先队列中41