《分支限界法》PPT课件.pptx

第第6 6章章 分支限界法分支限界法郭艺辉郭艺辉郭艺辉郭艺辉 广东金融学院广东金融学院广东金融学院广东金融学院 计算机科学与技术系计算机科学与技术系计算机科学与技术系计算机科学与技术系办公室：办公室：办公室：办公室：1622162216221622电话：，电话：，电话：，电话：，37215835372158353721583537215835mailmailmailmail：校内邮箱：校内邮箱：校内邮箱：校内邮箱第第6 6章章 分支限界法分支限界法学习要点学习要点学习要点学习要点理解分支限界法的剪枝搜索策略理解分支限界法的剪枝搜索策略理解分支限界法的剪枝搜索策略理解分支限界法的剪枝搜索策略 掌握分支限界法的算法框架：掌握分支限界法的算法框架：掌握分支限界法的算法框架：掌握分支限界法的算法框架：（1 1 1 1）队列式分支限界法）队列式分支限界法）队列式分支限界法）队列式分支限界法 （2 2 2 2）优先队式分支限界法）优先队式分支限界法）优先队式分支限界法）优先队式分支限界法 第第6 6章章 分支限界法分支限界法分分支支限限界界法法类类似似于于回回溯溯法法，也也是是在在问问题题的的解解空空间间上上搜搜索索问问题题解解的的算算法法。一一般般情情况况下下，分分支支限限界界法法与与回回溯溯法法的的求求解解目目标标不不同同。回回溯溯法法的的求求解解目目标标是是找找出出解解空空间间中中满满足足约约束束条条件件的的所所有有解解，而而分分支支限限界界法法的的求求解解目目标标则则是是找找出出满满足足约约束束条条件件的的一一个个解解，或或是是在在满满足足约约束束条条件件的的解解中中找找出出使使某某一一目目标标函函数数值值达达到到极极大大或或极小的解，即在某种意义下的最优解。极小的解，即在某种意义下的最优解。第第6 6章章 分支限界法分支限界法由由于于求求解解目目标标不不同同，导导致致分分支支限限界界法法与与回回溯溯法法对对解解空空间间的的搜搜索索方方式式也也不不相相同同。回回溯溯法法以以深深度度优优先先的的方方式式搜搜索索解解空空间间，而而分分支支限限界界法法则则以以广广度度优优先先或或以以最最小小耗费优先的方式搜索解空间。耗费优先的方式搜索解空间。分分支支限限界界法法的的搜搜索索策策略略是是：在在扩扩展展结结点点处处，先先生生成成其其所所有有的的儿儿子子结结点点（分分支支），然然后后再再从从当当前前的的活活结结点点表表中中选选择择下下一一个个扩扩展展结结点点。为为了了有有效效地地选选择择下下一一扩扩展展结结点点，加加速速搜搜索索的的进进程程，在在每每一一活活结结点点处处，计计算算一一个个函函数数值值（限限界界），并并根根据据函函数数值值，从从当当前前活活结结点点表表中中选选择择一一个个最最有有利利的的结结点点作作为为扩扩展展结结点点，使使搜搜索索朝朝着着解解空空间间上上有有最最优优解解的的分分支支推推进进，以以便便尽尽快快地地找出一个最优解。这种方法称为分支限界法。找出一个最优解。这种方法称为分支限界法。6.1 6.1 分支限界法的基本思想分支限界法的基本思想 分分支支限限界界法法常常以以广广度度优优先先或或以以最最小小耗耗费费（最最大大效效益益）优优先先的的方方式式搜搜索索问问题题的的解解空空间间树树。在在搜搜索索问问题题的的解解空空间间树树时时，分分支支限限界界法法与与回回溯溯法法的的主主要要区区别别在在于于它它们们对对当当前前扩扩展展结结点点所所采采用用的的扩扩展展方方式式不不同同。在在分分支支限限界界法法中中，每每一一个个活活结结点点只只有有一一次次机机会会成成为为扩扩展展结结点点。活活结结点点一一旦旦成成为为扩扩展展结结点点，就就一一次次性性产产生生其其所所有有儿儿子子结结点点。在在这这些些儿儿子子结结点点中中，导导致致不不可可行行解解或或导导致致非非最最优优解解的的儿儿子子结结点点被被舍舍弃弃，其其余余儿儿子子结结点点被被加加入入活活结结点点表表中中。此此后后，从从活活结结点点表表中中取取下下一一结结点点成成为为当当前前扩扩展展结结点点，并并重重复复上上述述结结点点扩扩展展过过程程。这这个过程一直持续到找到所需的解或活结点表为空时。个过程一直持续到找到所需的解或活结点表为空时。6.1 6.1 分支限界法的基本思想分支限界法的基本思想从从活活结结点点表表中中选选择择下下一一扩扩展展结结点点的的不不同同方方式式导导致致不不同同的分支限界法。最常见的有两种方式。的分支限界法。最常见的有两种方式。（1）队列式（）队列式（FIFO）分支限界法）分支限界法 队队列列式式分分支支限限界界法法将将活活结结点点表表组组织织成成一一个个队队列列，并并按按队队列列的的先先进进先先出出原原则则选选取取下下一一个个结结点点为为当当前前扩扩展展结点。结点。（2）优先队列式分支限界法）优先队列式分支限界法 优优先先队队列列式式的的分分支支限限界界法法将将活活结结点点表表组组织织成成一一个个优优先先队队列列，并并按按优优先先队队列列中中规规定定的的结结点点优优先先级级选选取取优优先级最高的下一个结点成为当前扩展结点。先级最高的下一个结点成为当前扩展结点。6.1 6.1 分支限界法的基本思想分支限界法的基本思想优优先先队队列列中中规规定定的的结结点点优优先先级级常常用用一一个个与与该该结结点点相相关关的的数数值值P来来表表示示。结结点点优优先先级级的的高高低低与与P值值的的大大小小相相关关。最最大大优优先先队队列列规规定定P值值较较大大的的结结点点优优先先级级较较高高。在在算算法法实实现现时时通通常常用用最最大大堆堆来来实实现现最最大大优优先先队队列列，用用最最大大堆堆的的 Deletemax运运算算抽抽取取堆堆中中下下一一个个结结点点成成为为当前扩展结点，体现最大效益优先的原则。当前扩展结点，体现最大效益优先的原则。类类似似地地，最最小小优优先先队队列列规规定定P值值较较小小的的结结点点优优先先级级较较高高。在在算算法法实实现现时时通通常常用用最最小小堆堆来来实实现现最最小小优优先先队队列列，用用最最小小堆堆的的Deletemin运运算算抽抽取取堆堆中中下下一一个个结结点点成成为为当前扩展结点，体现最小费用优先的原则。当前扩展结点，体现最小费用优先的原则。用用优优先先队队列列式式分分支支限限界界法法解解具具体体问问题题时时，应应根根据据具具体体问问题题的的特特点点确确定定选选用用最最大大优优先先队队列列或或最最小小优优先先队队列来表示解空间的活结点表。列来表示解空间的活结点表。6.1 6.1 分支限界法的基本思想分支限界法的基本思想n n0-10-1背包队列式分支限界法：背包队列式分支限界法：背包队列式分支限界法：背包队列式分支限界法：A A B,C=B,C B,C=B,C B B,C,C D,E=E D,E=E C C,E,E F,G=F,G F,G=F,G E E,F,G,F,G J,K=K(45)1,0,0 J,K=K(45)1,0,0 F F,G,G L,M=L(50)0,1,1 M(25)L,M=L(50)0,1,1 M(25)G G N,O=N(25),O(0)N,O=N(25),O(0)ABCDEFGHIJKLMNO10例例如如，考考虑虑n=3时时0-l背背包包问问题题如如下：下：w=16，15，15，P=45，25，25,C=30。6.1 6.1 分支限界法的基本思想分支限界法的基本思想0-10-1背包优先队列式分支限界法：背包优先队列式分支限界法：背包优先队列式分支限界法：背包优先队列式分支限界法：A A B,C=B(45),C(0)B,C=B(45),C(0)B B,C,C D,E=E(45)D,E=E(45)E E,C,C J,K=K(45)1,0,0J,K=K(45)1,0,0 C C F,G=F(25),G(0)F,G=F(25),G(0)F F,G,G L,M=L(50),0,1,1 M(25)L,M=L(50),0,1,1 M(25)G G N,O=N(25),O(0)N,O=N(25),O(0)ABCDEFGHIJKLMNO10例例如如，考考虑虑n=3时时0-l背背包包问问题题如如下：下：w=16，15，15，P=45，25，25,C=30。6.1 6.1 分支限界法的基本思想分支限界法的基本思想用用队队列列式式分分支支限限界界法法解解此此问问题题时时，算算法法从从根根结结点点A开开始始。初初始始时时活活结结点点队队列列为为空空，结结点点A是是当当前前扩扩展展结结点点。结结点点A的的2个个儿儿子子结结点点B和和C均均为为可可行行结结点点，故故将将这这2个个儿儿子子结结点点按按从从左左到到右右的的顺顺序序加加入入活活结结点点队队列列，并并且且舍舍弃弃当当前前扩扩展展结结点点A。依依先先进进先先出出原原则则，下下一一个个扩扩展展结结点点是是活活结结点点队队列列的的队队首首结结点点B。扩扩展展结结点点B得得到到其其儿儿子子结结点点D和和E。由由于于D是是不不可可行行结结点点，故故被被舍舍去去。E是是可可行行结结点点，被被加加入入活活结结点点队队列列。接接下下来来，C成成为为当当前前扩扩展展结结点点，它它的的2个个儿儿子子结结点点F和和G均均为为可可行行结结点点，因因此此被被加加入入到到活活结结点点队队列列中中。扩扩展展下下一一个个结结点点E得得到到结结点点J和和K。J是是不不可可行行结结点点，因因而而被被舍舍去去。K是是可可行行的的叶叶结结点点，表表示示所所求求问问题题的的一一个个可可行行解解，其其价价值值为为45。6.1 6.1 分支限界法的基本思想分支限界法的基本思想当当前前活活结结点点队队列列的的队队首首结结点点F成成为为下下一一个个扩扩展展结结点点。它它的的2个个儿儿子子结结点点L和和M均均为为叶叶结结点点。L表表示示获获得得价价值值为为50的的可可行行解解；M表表示示获获得得价价值值为为25的的可可行行解解。G是是最最后后的的一一个个扩扩展展结结点点，其其儿儿子子结结点点N和和O均均为为可可行行叶叶结结点点。最最后后，活活结结点点队队列列已已空空，算算法法终终止止。算算法法搜搜索索得到最优值为得到最优值为50。6.1 6.1 分支限界法的基本思想分支限界法的基本思想优优先先队队列列式式分分支支限限界界法法从从根根结结点点A开开始始搜搜索索解解空空间间树树。用用一一个个极极大大堆堆表表示示活活结结点点表表的的优优先先队队列列。初初始始时时堆堆为为空空，扩扩展展结结点点A得得到到它它的的2个个儿儿子子结结点点B和和C。这这2个个结结点点均均为为可可行行结结点点，因因此此被被加加入入到到堆堆中中，结结点点A被被舍舍弃弃。结结点点B获获得得的的当当前前价价值值是是45，而而结结点点C的的当当前前价价值值为为0。由由于于结结点点B的的价价值值大大于于结结点点C的的价价值值，所所以以结结点点B是是堆堆中中最最大大元元素素，从从而而成成为为下下一一个个扩扩展展结结点点扩扩展展结结点点B得得到到结结点点D和和E。D不不是是可可行行结结点点，因因而而被被舍舍去去。E是是可可行行结结点点被被加加入入到到堆堆中中。E的的价价值值为为45，成成为为当当前前堆堆中中最最大大元元素素，从从而而成成为为下下一一个个扩扩展展结结点点。扩扩展展结结点点E得得到到2个个叶叶结结点点J和和 K。J是是不不可可行行结结点点，被被舍舍弃弃。K是是可可行行叶叶结结点点，表表示示所所求求问问题题的的一一个个可可行行解解，其价值为其价值为 45。6.1 6.1 分支限界法的基本思想分支限界法的基本思想此此时时，堆堆中中仅仅剩剩下下一一个个活活结结点点C，它它成成为为当当前前扩扩展展结结点点。它它的的2个个儿儿子子结结点点F和和G均均为为可可行行结结点点，因因此此被被插插入入到到当当前前堆堆中中。结结点点F的的价价值值为为25，是是堆堆中中最最大大元元素素，成成为为下下一一个个扩扩展展结结点点。结结点点F的的2个个儿儿子子结结点点L和和M均均为为叶叶结结点点。叶叶结结点点L相相应应于于价价值值为为50的的可可行行解解。叶叶结结点点M相相应应于于价价值值为为25的的可可行行解解。叶叶结结点点L所所相相应应的的解解成成为为当当前前最最优优解解。最最后后，结结点点G成成为为扩扩展展结结点点，其其儿儿子子结结点点N和和O均均为为叶叶结结点点，它它们们的的价价值值分分别别为为25和和0。接接下下来来，存存储储活活结结点点的的堆堆已已空空，算算法法终终止止。算算法法搜搜索索得得到到最最优优值值为为 50。相相应应的的最最优优解解是是从从根根结结点点 A到到结点结点L的路径（的路径（0，1，1）。）。6.1 6.1 分支限界法的基本思想分支限界法的基本思想在在寻寻求求问问题题的的最最优优解解时时，与与讨讨论论回回溯溯法法时时类类似似，可可以以用用剪剪枝枝函函数数加加速速搜搜索索。该该函函数数给给出出每每一一个个可可行行结结点点相相应应的的子子树树可可能能获获得得的的最最大大价价值值的的上上界界。如如果果这这个个上上界界不不会会比比当当前前最最优优值值更更大大，则则说说明明相相应应的的子子树树中中不不含含问问题题的的最最优优解解，因因而而可可以以剪剪去去。另另一一方方面面，也也可可以以将将上上界界函函数数确确定定的的每每个个结结点点的的上上界界值值作作为为优优先先级级，以以该该优优先先级级的的非非增增序序抽抽取取当当前前扩扩展展结结点点。这这种种策略有时可以更迅速地找到最优解。策略有时可以更迅速地找到最优解。6.1 6.1 分支限界法的基本思想分支限界法的基本思想旅行售货员问题旅行售货员问题旅行售货员问题旅行售货员问题1234206305410ABCDEFGHIJKLMNOPQ1234344342232432问问问问题题题题描描描描述述述述：某某某某售售售售货货货货员员员员要要要要到到到到若若若若干干干干城城城城市市市市去去去去推推推推销销销销商商商商品品品品，已已已已知知知知各各各各城城城城市市市市之之之之间间间间的的的的路路路路程程程程，他他他他要要要要选选选选定定定定一一一一条条条条从从从从驻驻驻驻地地地地出出出出发发发发，经经经经过过过过每每每每个个个个城城城城市市市市一一一一遍遍遍遍，最最最最后后后后回回回回到到到到住住住住地地地地的的的的路路路路线线线线，使使使使总总总总的路程最短。的路程最短。的路程最短。的路程最短。6.1 6.1 分支限界法的基本思想分支限界法的基本思想 旅行售货员问题旅行售货员问题 队列式分支限界法：队列式分支限界法：A B,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,4G,H,I,J,K M(66)H,I,J,K N(25)1,3,2,4I,J,K 1-3-4(限界掉限界掉)/I(26)J,K(限界掉限界掉)/P(25)K(限界掉限界掉)/Q(59)例例 旅行售货员问题旅行售货员问题1234206305410ABCDEFGHIJKLMNOPQ12343443423224236.1 6.1 分支限界法的基本思想分支限界法的基本思想 旅行售货员问题旅行售货员问题旅行售货员问题旅行售货员问题 优先队列式分支限界法：优先队列式分支限界法：优先队列式分支限界法：优先队列式分支限界法：A BB C,D,E=C(30),D(6),E(4)E,D,C J,K=D(6),C(30),J(14),K(24)D,J,K,C H,I=J(14),K(24),C(30),H(11),I(26)H,J,K,I,C N=N(25)1,3,2,4J,K,I,C P(25)限界掉限界掉K,I,C Q(59)限界掉限界掉I,C I(26),C(30)限界掉限界掉1234206305410ABCDEFGHIJKLMNOPQ12343443423224236.1 6.1 分支限界法的基本思想分支限界法的基本思想解解此此问问题题的的队队列列式式分分支支限限界界法法以以排排列列树树中中结结点点B作作为为初初始始扩扩展展结结点点。此此时时，活活结结点点队队列列为为空空。由由于于从从图图G的的顶顶点点1到到顶顶点点2，3和和4均均有有边边相相连连，所所以以结结点点B的的儿儿子子结结点点C，D，E均均为为可可行行结结点点，它它们们被被加加入入到到活活结结点点队队列列中中，并并舍舍去去当当前前扩扩展展结结点点B。当当前前活活结结点点队队列列中中的的队队首首结结点点C成成为为下下一一个个扩扩展展结结点点。由由于于图图G的的顶顶点点2到到顶顶点点3和和4有有边边相相连连，故故结结点点C的的2个个儿儿子子结结点点F和和G均均为为可可行行结结点点，从从而而被被加加入入到到活活结结点点队队列列中中。接接下下来来，结结点点D和和结结点点E相相继继成成为为扩扩展展结结点点而而被被扩扩展展。此此时，活结点队列中的结点依次为时，活结点队列中的结点依次为F，G，H，I，J，K。6.1 6.1 分支限界法的基本思想分支限界法的基本思想结结点点F成成为为下下一一个个扩扩展展结结点点，其其儿儿子子结结点点L是是叶叶结结点点。此此时时找找到到了了一一条条旅旅行行售售货货员员回回路路，其其费费用用为为59。从从下下一一个个扩扩展展结结点点G得得到到叶叶结结点点M，它它相相应应的的旅旅行行售售货货员员回回路路的的费费用用为为66。结结点点H依依次次成成为为扩扩展展结结点点，得得到到结结点点N相相应应的的旅旅行行售售货货员员回回路路，其其费费用用为为25，这这是是当当前前最最好好的的一一条条回回路路。下下一一个个扩扩展展结结点点是是结结点点I，由由于于从从根根结结点点到到叶叶结结点点I的的费费用用26已已超超过过了了当当前前最最优优值值，故故没没有有必必要要扩扩展展结结点点I，以以结结点点I为为根根的的子子树树被被剪剪去去。最最后后，结结点点J和和K被被依依次次扩扩展展，活活结结点点队队列列成成为为空空，算算法法终终止止。算算法法搜搜索索得得到到最最优优值值为为25，相相应应的的最最忧忧解是从根结点到结点解是从根结点到结点N的路径（的路径（1，3，2，4，1）。）。6.1 6.1 分支限界法的基本思想分支限界法的基本思想解解同同一一问问题题的的优优先先队队列列式式分分支支限限界界法法用用一一极极小小堆堆来来存存储储活活结结点点表表。其其优优先先级级是是结结点点的的当当前前费费用用。算算法法还还是是从从排排列列树树的的结结点点B和和空空优优先先队队列列开开始始。结结点点B被被扩扩展展后后，它它的的3个个儿儿子子结结点点C，D和和E被被依依次次插插入入堆堆中中。此此时时，由由于于E是是堆堆中中具具有有最最小小当当前前费费用用（4）的的结结点点，所所以以处处于于堆堆顶顶的的位位置置，它它自自然然成成为为下下一一个个扩扩展展结结点点。结结点点E被被扩扩展展后后，其其儿儿子子结结点点J和和K被被插插入入当当前前堆堆中中，它它们们的的费费用用分分别别为为14和和24。此此时时，堆堆顶顶元元素素是是结结点点D，它它成成为为下下一一个个扩扩展展结结点点。它它的的2个个儿儿子子结结点点H和和I被被插插入入堆堆中中。此此时时堆堆中中含含有有结结点点C，H，I，J，K。在在这这些些结结点点中中，结结点点H具具有有最最小小费费用用，从从而而它它成成为为下下一一个个扩扩展展结结点点。扩扩展展结结点点H后后得得到到一一条条旅旅行行售售货货员员回回路路（l，3，2，4，1），相相应应的的费费用用为为25。接接下下来来，结结点点J成成为为扩扩展展结结点点，由由此此得得到到另另一一条条费费用用为为25的的回回路路门门，4，2，3，1）。此此后后的的2个个扩扩展展结结点点是是结结点点K和和I。由由结结点点K得得到到的的可可行行解解费费用用高高于于当当前前最最优优解解，结结点点I本本身身的的费费用用已已高高于于当当前前最最优优解解，从从而而它它们们都都不不能能得得到到更更好好的的解解。最最后后，优优先队列为空，算法终止。先队列为空，算法终止。6.1 6.1 分支限界法的基本思想分支限界法的基本思想与与0-1背背包包问问题题的的例例子子类类似似，可可以以用用一一个个限限界界函函数数在在搜搜索索过过程程中中裁裁剪剪子子树树，以以减减少少产产生生的的活活结结点点。此此时时剪剪枝枝函函数数是是当当前前结结点点扩扩展展后后得得到到的的最最小小费费用用的的下下界界。如如果果在在当当前前扩扩展展结结点点处处，这这个个下下界界不不比比当当前前最最优优值值更更小小，则则剪剪去去以以该该结结点点为为根根的的子子树树。另另一一方方面面，也也可可以以把把每每个个结结点点的的下下界界作作为为优优先先级级，依依非非减减序序从从活活结点优先队列中抽取下一个扩展结点。结点优先队列中抽取下一个扩展结点。6.3 装载问题装载问题1.1.1.1.问题描述问题描述问题描述问题描述n n有一批共有一批共有一批共有一批共n n n n个集装箱要装上个集装箱要装上个集装箱要装上个集装箱要装上2 2 2 2艘载重量分别为艘载重量分别为艘载重量分别为艘载重量分别为C1C1C1C1和和和和C2C2C2C2的轮船，其中集装箱的轮船，其中集装箱的轮船，其中集装箱的轮船，其中集装箱i i i i的重量为的重量为的重量为的重量为wiwiwiwi，且，且，且，且w w w wi i i iC1+C2C1+C2C1+C2C1+C2n n装载问题要求确定是否有一个合理的装载方案可将装载问题要求确定是否有一个合理的装载方案可将装载问题要求确定是否有一个合理的装载方案可将装载问题要求确定是否有一个合理的装载方案可将这这这这n n n n个集装箱装上这个集装箱装上这个集装箱装上这个集装箱装上这2 2 2 2艘轮船。如果有，找出一种装艘轮船。如果有，找出一种装艘轮船。如果有，找出一种装艘轮船。如果有，找出一种装载方案。载方案。载方案。载方案。n n容易证明，如果一个给定装载问题有解，则采用下容易证明，如果一个给定装载问题有解，则采用下容易证明，如果一个给定装载问题有解，则采用下容易证明，如果一个给定装载问题有解，则采用下面的策略可得到最优装载方案：面的策略可得到最优装载方案：面的策略可得到最优装载方案：面的策略可得到最优装载方案：n n(1)(1)(1)(1)首先将第一艘轮船尽可能装满；首先将第一艘轮船尽可能装满；首先将第一艘轮船尽可能装满；首先将第一艘轮船尽可能装满；n n(2)(2)(2)(2)将剩余的集装箱装上第二艘轮船。将剩余的集装箱装上第二艘轮船。将剩余的集装箱装上第二艘轮船。将剩余的集装箱装上第二艘轮船。6.3 装载问题装载问题将将将将第第第第一一一一艘艘艘艘轮轮轮轮船船船船尽尽尽尽可可可可能能能能装装装装满满满满等等等等价价价价于于于于选选选选取取取取全全全全体体体体集集集集装装装装箱箱箱箱的的的的一一一一个个个个子子子子集集集集，使使使使该该该该子子子子集集集集中中中中集集集集装装装装箱箱箱箱重重重重量量量量之之之之和和和和最最最最接接接接近近近近C C C C1 1 1 1。由由由由此此此此可知，装载问题等价于以下特殊的可知，装载问题等价于以下特殊的可知，装载问题等价于以下特殊的可知，装载问题等价于以下特殊的0-10-10-10-1背包问题。背包问题。背包问题。背包问题。6.3 装载问题装载问题6.3 6.3 装载问题装载问题装载问题装载问题：n=3,Cn=3,Cn=3,Cn=3,C1 1 1 1=C=C=C=C2 2 2 2=30,w=16,15,15,=30,w=16,15,15,=30,w=16,15,15,=30,w=16,15,15,6.3 装载问题装载问题用用用用一一一一个个个个队队队队列列列列QQ来来来来存存存存放放放放活活活活结结结结点点点点表表表表，QQ中中中中weightweight表表表表示示示示每每每每个个个个活活活活结结结结点点点点所所所所相相相相应应应应的的的的当当当当前前前前载载载载重重重重量量量量。当当当当weightweight1 1时时时时，表表表表示示示示队列已达到解空间树同一层结点的尾部。队列已达到解空间树同一层结点的尾部。队列已达到解空间树同一层结点的尾部。队列已达到解空间树同一层结点的尾部。算算算算法法法法首首首首先先先先检检检检测测测测当当当当前前前前扩扩扩扩展展展展结结结结点点点点的的的的左左左左儿儿儿儿子子子子结结结结点点点点是是是是否否否否为为为为可可可可行行行行结结结结点点点点。如如如如果果果果是是是是则则则则将将将将其其其其加加加加入入入入到到到到活活活活结结结结点点点点队队队队列列列列中中中中。然然然然后后后后将将将将其其其其右右右右儿儿儿儿子子子子结结结结点点点点加加加加入入入入到到到到活活活活结结结结点点点点队队队队列列列列中中中中(右右右右儿儿儿儿子子子子结结结结点点点点一一一一定定定定是是是是可可可可行行行行结结结结点点点点)。2 2个个个个儿儿儿儿子子子子结结结结点点点点都都都都产产产产生生生生后后后后，当当当当前前前前扩扩扩扩展展展展结结结结点被舍弃。点被舍弃。点被舍弃。点被舍弃。活结点队列中的队首元素被取出作为当前扩展结点活结点队列中的队首元素被取出作为当前扩展结点活结点队列中的队首元素被取出作为当前扩展结点活结点队列中的队首元素被取出作为当前扩展结点 取取取取出出出出元元元元素素素素不不不不是是是是-1-1时时时时，活活活活结结结结点点点点队队队队列列列列一一一一定定定定不不不不空空空空。由由由由于于于于队队队队列列列列中中中中每每每每一一一一层层层层结结结结点点点点之之之之后后后后都都都都有有有有一一一一个个个个尾尾尾尾部部部部标标标标记记记记-1-1。取取取取出出出出的的的的元元元元素素素素是是是是-1-1时时时时，判判判判断断断断当当当当前前前前队队队队列列列列是是是是否否否否为为为为空空空空。如如如如果果果果队队队队列列列列非非非非空空空空，则则则则将将将将尾尾尾尾部部部部标标标标记记记记-1-1加加加加入入入入活活活活结结结结点点点点队队队队列列列列，算算算算法法法法开开开开始始始始处处处处理理理理下下下下一一一一层的活结点。层的活结点。层的活结点。层的活结点。6.3 装载问题装载问题n n该算法包含两个函数该算法包含两个函数该算法包含两个函数该算法包含两个函数n nMaxLoadingMaxLoading函数具体实施对解空间的分支限界搜函数具体实施对解空间的分支限界搜函数具体实施对解空间的分支限界搜函数具体实施对解空间的分支限界搜索。索。索。索。n nEnQueueEnQueue用于将活结点加入到活结点队列中，该用于将活结点加入到活结点队列中，该用于将活结点加入到活结点队列中，该用于将活结点加入到活结点队列中，该函数首先检查函数首先检查函数首先检查函数首先检查i i是否等于是否等于是否等于是否等于n n，如果，如果，如果，如果i=ni=n，则表示当前，则表示当前，则表示当前，则表示当前活结点为一个叶结点，由于叶结点不会被进一步活结点为一个叶结点，由于叶结点不会被进一步活结点为一个叶结点，由于叶结点不会被进一步活结点为一个叶结点，由于叶结点不会被进一步扩展，因此不必加入到活结点，如果该叶结点表扩展，因此不必加入到活结点，如果该叶结点表扩展，因此不必加入到活结点，如果该叶结点表扩展，因此不必加入到活结点，如果该叶结点表示的可行解优于当前最优解，更新最优解。当示的可行解优于当前最优解，更新最优解。当示的可行解优于当前最优解，更新最优解。当示的可行解优于当前最优解，更新最优解。当inin时，当前活结点是一个内部结点，加入到活结点时，当前活结点是一个内部结点，加入到活结点时，当前活结点是一个内部结点，加入到活结点时，当前活结点是一个内部结点，加入到活结点队列中。队列中。队列中。队列中。6.3 装载问题装载问题templatetemplatevoid EnQueue(Queue&Q,T wt,void EnQueue(Queue&Q,T wt,T&bestw,int i,int n)T&bestw,int i,int n)/该函数负责加入活结点该函数负责加入活结点该函数负责加入活结点该函数负责加入活结点 /如果不是叶节点，则将节点权值如果不是叶节点，则将节点权值如果不是叶节点，则将节点权值如果不是叶节点，则将节点权值w tw t加入队列加入队列加入队列加入队列QQ if(i=n)if(i=n)/叶子叶子叶子叶子 if(wt bestw)bestw=wt;if(wt bestw)bestw=wt;else Q.Add(wt);else Q.Add(wt);/不是叶子不是叶子不是叶子不是叶子 6.3 装载问题装载问题templatetemplateT MaxLoading(T w,T c,T MaxLoading(T w,T c,int n)int n)/返回最优装载值返回最优装载值返回最优装载值返回最优装载值 /为层次为层次为层次为层次1 1 初始化初始化初始化初始化 Queue Q;Queue Q;/活结点队列活结点队列活结点队列活结点队列 Q.Add(-1);Q.Add(-1);/标记本层的尾部标记本层的尾部标记本层的尾部标记本层的尾部 int i=1;int i=1;/当前扩展结点的层当前扩展结点的层当前扩展结点的层当前扩展结点的层 T Ew=0,T Ew=0,/当前扩展结点的当前扩展结点的当前扩展结点的当前扩展结点的权值权值权值权值 bestw=0;bestw=0;/目前的最优值目前的最优值目前的最优值目前的最优值 while(true)/检查左孩子结点检查左孩子结点 if(Ew+wi 0r0，故故故故Ew+rbestwEw+rbestw总总总总是是是是成成成成立立立立，也就是说，此时右子树测试不起作用。也就是说，此时右子树测试不起作用。也就是说，此时右子树测试不起作用。也就是说，此时右子树测试不起作用。算算算算法法法法中中中中结结结结点点点点相相相相应应应应的的的的重重重重量量量量仅仅仅仅在在在在搜搜搜搜索索索索进进进进入入入入左左左左子子子子树树树树时时时时增增增增加加加加，因因因因此此此此，可以在算法每一次进入左子树时更新可以在算法每一次进入左子树时更新可以在算法每一次进入左子树时更新可以在算法每一次进入左子树时更新bestwbestw的值。的值。的值。的值。6.3 装载问题装载问题n n使用定界函数进行改进使用定界函数进行改进使用定界函数进行改进使用定界函数进行改进T MaxLoading(T w,T c,int n)T MaxLoading(T w,T c,int n)Queue Q;Queue Q;/活节点队列活节点队列活节点队列活节点队列 Q.Add(-1);Q.Add(-1);/标记本层的尾部标记本层的尾部标记本层的尾部标记本层的尾部 int i=1;int i=1;/当前扩展节点的层当前扩展节点的层当前扩展节点的层当前扩展节点的层 T Ew=0,T Ew=0,/当前扩展节点的重量当前扩展节点的重量当前扩展节点的重量当前扩展节点的重量 bestw=0;bestw=0;/目前的最优值目前的最优值目前的最优值目前的最优值 r=0;r=0;/当前扩展节点中余下的重量当前扩展节点中余下的重量当前扩展节点中余下的重量当前扩展节点中余下的重量 for(int j=2;j=n;j+)for(int j=2;j=n;j+)r+=wi;r+=wi;6.3 装载问题装载问题while(true)while(true)T wt=Ew+wi;T wt=Ew+wi;/检查扩展结点的左孩子检查扩展结点的左孩子检查扩展结点的左孩子检查扩展结点的左孩子 if(wt=c)if(wt bestw)bestw=wt;if(wt bestw)bestw=wt;if(i n)Q.Add(wt);if(i bestw&i bestw&i n)/检查右孩子检查右孩子检查右孩子检查右孩子 Q.Add(Ew);Q.Add(Ew);/可能含最优解可能含最优解可能含最优解可能含最优解 Q.Delete(Ew);Q.Delete(Ew);/取下一个扩展结点取下一个扩展结点取下一个扩展结点取下一个扩展结点 if(Ew=-1)if(Ew=-1)/到达层的尾部到达层的尾部到达层的尾部到达层的尾部 if(Q.IsEmpty()return bestw;if(Q.IsEmpty()return bestw;Q.Add(-1);Q.Add(-1);/添加尾部标记添加尾部标记添加尾部标记添加尾部标记 Q.Delete(Ew);Q.Delete(Ew);/取下一个扩展结点取下一个扩展结点取下一个扩展结点取下一个扩展结点 i+;i+;r-=wi;r-=wi;提前更新提前更新bestw bestw 右儿子剪枝右儿子剪枝 6.3 装载问题装载问题3.构造最优解构造最优解6.3 装载问题装载问题6.3 装载问题装载问题6.3 装载问题装载问题4.4.优先队列式分支限界法优先队列式分支限界法优先队列式分支限界法优先队列式分支限界法n n存储活结点的方式存储活结点的方式存储活结点的方式存储活结点的方式:解装载问题的优先队列式分支限解装载问题的优先队列式分支限解装载问题的优先队列式分支限解装载问题的优先队列式分支限界法用最大优先队列存储活结点表。界法用最大优先队列存储活结点表。界法用最大优先队列存储活结点表。界法用最大优先队列存储活结点表。n n活结点活结点活结点活结点x x在优先队列中的优先级定义为：从根结点到在优先队列中的优先级定义为：从根结点到在优先队列中的优先级定义为：从根结点到在优先队列中的优先级定义为：从根结点到结点结点结点结点x x的路径所相应的载重量再加上剩余集装箱的重的路径所相应的载重量再加上剩余集装箱的重的路径所相应的载重量再加上剩余集装箱的重的路径所相应的载重量再加上剩余集装箱的重量之和。量之和。量之和。量之和。n n扩展结点的选择：扩展结点的选择：扩展结点的选择：扩展结点的选择：优先队列中优先级最大的活结点优先队列中优先级最大的活结点优先队列中优先级最大的活结点优先队列中优先级最大的活结点成为下一个扩展结点。以结点成为下一个扩展结点。以结点成为下一个扩展结点。以结点成为下一个扩展结点。以结点x x为根的子树中所有结为根的子树中所有结为根的子树中所有结为根的子树中所有结点相应的路径的载重量不超过它的优先级。子集树点相应的路径的载重量不超过它的优先级。子集树点相应的路径的载重量不超过它的优先级。子集树点相应的路径的载重量不超过它的优先级。子集树中叶结点所相应的载重量与其优先级相同。中叶结点所相应的载重量与其优先级相同。中叶结点所相应的载重量与其优先级相同。中叶结点所相应的载重量与其优先级相同。n n算法终止条件：算法终止条件：算法终止条件：算法终止条件：在优先队列式分支限界法中，一旦在优先队列式分支限界法中，一旦在优先队列式分支限界法中，一旦在优先队列式分支限界法中，一旦有一个叶结点成为当前扩展结点，则可以断言该叶有一个叶结点成为当前扩展结点，则可以断言该叶有一个叶结点成为当前扩展结点，则可以断言该叶有一个叶结点成为当前扩展结点，则可以断言该叶结点所相应的解即为最优解。此时可终止算法。结点所相应的解即为最优解。此时可终止算法。结点所相应的解即为最优解。此时可终止算法。结点所相应的解即为最优解。此时可终止算法。6.3 装载问题装载问题用一个元素类型为用一个元素类型为用一个元素类型为用一个元素类型为HeapNodeHeapNode的最大堆来表示活结点优先队列。的最大堆来表示活结点优先队列。的最大堆来表示活结点优先队列。的最大堆来表示活结点优先队列。解空间树中结点类型为解空间树中结点类型为解空间树中结点类型为解空间树中结点类型为bbnodebbnodetemplate class HeapNode;template class HeapNode;class bbnodeclass bbnode friend void