《分支限界法》PPT课件.pptx
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《《分支限界法》PPT课件.pptx》由会员分享,可在线阅读,更多相关《《分支限界法》PPT课件.pptx(53页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第第6 6章章 分支限界法分支限界法郭艺辉郭艺辉郭艺辉郭艺辉 广东金融学院广东金融学院广东金融学院广东金融学院 计算机科学与技术系计算机科学与技术系计算机科学与技术系计算机科学与技术系办公室:办公室:办公室:办公室:1622162216221622电话:,电话:,电话:,电话:,37215835372158353721583537215835mailmailmailmail:校内邮箱:校内邮箱:校内邮箱:校内邮箱第第6 6章章 分支限界法分支限界法学习要点学习要点学习要点学习要点理解分支限界法的剪枝搜索策略理解分支限界法的剪枝搜索策略理解分支限界法的剪枝搜索策略理解分支限界法的剪枝搜索策略 掌
2、握分支限界法的算法框架:掌握分支限界法的算法框架:掌握分支限界法的算法框架:掌握分支限界法的算法框架:(1 1 1 1)队列式分支限界法)队列式分支限界法)队列式分支限界法)队列式分支限界法 (2 2 2 2)优先队式分支限界法)优先队式分支限界法)优先队式分支限界法)优先队式分支限界法 第第6 6章章 分支限界法分支限界法分分支支限限界界法法类类似似于于回回溯溯法法,也也是是在在问问题题的的解解空空间间上上搜搜索索问问题题解解的的算算法法。一一般般情情况况下下,分分支支限限界界法法与与回回溯溯法法的的求求解解目目标标不不同同。回回溯溯法法的的求求解解目目标标是是找找出出解解空空间间中中满满足
3、足约约束束条条件件的的所所有有解解,而而分分支支限限界界法法的的求求解解目目标标则则是是找找出出满满足足约约束束条条件件的的一一个个解解,或或是是在在满满足足约约束束条条件件的的解解中中找找出出使使某某一一目目标标函函数数值值达达到到极极大大或或极小的解,即在某种意义下的最优解。极小的解,即在某种意义下的最优解。第第6 6章章 分支限界法分支限界法由由于于求求解解目目标标不不同同,导导致致分分支支限限界界法法与与回回溯溯法法对对解解空空间间的的搜搜索索方方式式也也不不相相同同。回回溯溯法法以以深深度度优优先先的的方方式式搜搜索索解解空空间间,而而分分支支限限界界法法则则以以广广度度优优先先或或
4、以以最最小小耗费优先的方式搜索解空间。耗费优先的方式搜索解空间。分分支支限限界界法法的的搜搜索索策策略略是是:在在扩扩展展结结点点处处,先先生生成成其其所所有有的的儿儿子子结结点点(分分支支),然然后后再再从从当当前前的的活活结结点点表表中中选选择择下下一一个个扩扩展展结结点点。为为了了有有效效地地选选择择下下一一扩扩展展结结点点,加加速速搜搜索索的的进进程程,在在每每一一活活结结点点处处,计计算算一一个个函函数数值值(限限界界),并并根根据据函函数数值值,从从当当前前活活结结点点表表中中选选择择一一个个最最有有利利的的结结点点作作为为扩扩展展结结点点,使使搜搜索索朝朝着着解解空空间间上上有有
5、最最优优解解的的分分支支推推进进,以以便便尽尽快快地地找出一个最优解。这种方法称为分支限界法。找出一个最优解。这种方法称为分支限界法。6.1 6.1 分支限界法的基本思想分支限界法的基本思想 分分支支限限界界法法常常以以广广度度优优先先或或以以最最小小耗耗费费(最最大大效效益益)优优先先的的方方式式搜搜索索问问题题的的解解空空间间树树。在在搜搜索索问问题题的的解解空空间间树树时时,分分支支限限界界法法与与回回溯溯法法的的主主要要区区别别在在于于它它们们对对当当前前扩扩展展结结点点所所采采用用的的扩扩展展方方式式不不同同。在在分分支支限限界界法法中中,每每一一个个活活结结点点只只有有一一次次机机
6、会会成成为为扩扩展展结结点点。活活结结点点一一旦旦成成为为扩扩展展结结点点,就就一一次次性性产产生生其其所所有有儿儿子子结结点点。在在这这些些儿儿子子结结点点中中,导导致致不不可可行行解解或或导导致致非非最最优优解解的的儿儿子子结结点点被被舍舍弃弃,其其余余儿儿子子结结点点被被加加入入活活结结点点表表中中。此此后后,从从活活结结点点表表中中取取下下一一结结点点成成为为当当前前扩扩展展结结点点,并并重重复复上上述述结结点点扩扩展展过过程程。这这个过程一直持续到找到所需的解或活结点表为空时。个过程一直持续到找到所需的解或活结点表为空时。6.1 6.1 分支限界法的基本思想分支限界法的基本思想从从活
7、活结结点点表表中中选选择择下下一一扩扩展展结结点点的的不不同同方方式式导导致致不不同同的分支限界法。最常见的有两种方式。的分支限界法。最常见的有两种方式。(1)队列式()队列式(FIFO)分支限界法)分支限界法 队队列列式式分分支支限限界界法法将将活活结结点点表表组组织织成成一一个个队队列列,并并按按队队列列的的先先进进先先出出原原则则选选取取下下一一个个结结点点为为当当前前扩扩展展结点。结点。(2)优先队列式分支限界法)优先队列式分支限界法 优优先先队队列列式式的的分分支支限限界界法法将将活活结结点点表表组组织织成成一一个个优优先先队队列列,并并按按优优先先队队列列中中规规定定的的结结点点优
8、优先先级级选选取取优优先级最高的下一个结点成为当前扩展结点。先级最高的下一个结点成为当前扩展结点。6.1 6.1 分支限界法的基本思想分支限界法的基本思想优优先先队队列列中中规规定定的的结结点点优优先先级级常常用用一一个个与与该该结结点点相相关关的的数数值值P来来表表示示。结结点点优优先先级级的的高高低低与与P值值的的大大小小相相关关。最最大大优优先先队队列列规规定定P值值较较大大的的结结点点优优先先级级较较高高。在在算算法法实实现现时时通通常常用用最最大大堆堆来来实实现现最最大大优优先先队队列列,用用最最大大堆堆的的 Deletemax运运算算抽抽取取堆堆中中下下一一个个结结点点成成为为当前
9、扩展结点,体现最大效益优先的原则。当前扩展结点,体现最大效益优先的原则。类类似似地地,最最小小优优先先队队列列规规定定P值值较较小小的的结结点点优优先先级级较较高高。在在算算法法实实现现时时通通常常用用最最小小堆堆来来实实现现最最小小优优先先队队列列,用用最最小小堆堆的的Deletemin运运算算抽抽取取堆堆中中下下一一个个结结点点成成为为当前扩展结点,体现最小费用优先的原则。当前扩展结点,体现最小费用优先的原则。用用优优先先队队列列式式分分支支限限界界法法解解具具体体问问题题时时,应应根根据据具具体体问问题题的的特特点点确确定定选选用用最最大大优优先先队队列列或或最最小小优优先先队队列来表示
10、解空间的活结点表。列来表示解空间的活结点表。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)ABCDEFGHIJK
11、LMNO10例例如如,考考虑虑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
12、 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个个儿儿子子结结
13、点点按按从从左左到到右右的的顺顺序序加加入入活活结结点点队队列列,并并且且舍舍弃弃当当前前扩扩展展结结点点A。依依先先进进先先出出原原则则,下下一一个个扩扩展展结结点点是是活活结结点点队队列列的的队队首首结结点点B。扩扩展展结结点点B得得到到其其儿儿子子结结点点D和和E。由由于于D是是不不可可行行结结点点,故故被被舍舍去去。E是是可可行行结结点点,被被加加入入活活结结点点队队列列。接接下下来来,C成成为为当当前前扩扩展展结结点点,它它的的2个个儿儿子子结结点点F和和G均均为为可可行行结结点点,因因此此被被加加入入到到活活结结点点队队列列中中。扩扩展展下下一一个个结结点点E得得到到结结点点J和和
14、K。J是是不不可可行行结结点点,因因而而被被舍舍去去。K是是可可行行的的叶叶结结点点,表表示示所所求求问问题题的的一一个个可可行行解解,其其价价值值为为45。6.1 6.1 分支限界法的基本思想分支限界法的基本思想当当前前活活结结点点队队列列的的队队首首结结点点F成成为为下下一一个个扩扩展展结结点点。它它的的2个个儿儿子子结结点点L和和M均均为为叶叶结结点点。L表表示示获获得得价价值值为为50的的可可行行解解;M表表示示获获得得价价值值为为25的的可可行行解解。G是是最最后后的的一一个个扩扩展展结结点点,其其儿儿子子结结点点N和和O均均为为可可行行叶叶结结点点。最最后后,活活结结点点队队列列已
15、已空空,算算法法终终止止。算算法法搜搜索索得到最优值为得到最优值为50。6.1 6.1 分支限界法的基本思想分支限界法的基本思想优优先先队队列列式式分分支支限限界界法法从从根根结结点点A开开始始搜搜索索解解空空间间树树。用用一一个个极极大大堆堆表表示示活活结结点点表表的的优优先先队队列列。初初始始时时堆堆为为空空,扩扩展展结结点点A得得到到它它的的2个个儿儿子子结结点点B和和C。这这2个个结结点点均均为为可可行行结结点点,因因此此被被加加入入到到堆堆中中,结结点点A被被舍舍弃弃。结结点点B获获得得的的当当前前价价值值是是45,而而结结点点C的的当当前前价价值值为为0。由由于于结结点点B的的价价
16、值值大大于于结结点点C的的价价值值,所所以以结结点点B是是堆堆中中最最大大元元素素,从从而而成成为为下下一一个个扩扩展展结结点点扩扩展展结结点点B得得到到结结点点D和和E。D不不是是可可行行结结点点,因因而而被被舍舍去去。E是是可可行行结结点点被被加加入入到到堆堆中中。E的的价价值值为为45,成成为为当当前前堆堆中中最最大大元元素素,从从而而成成为为下下一一个个扩扩展展结结点点。扩扩展展结结点点E得得到到2个个叶叶结结点点J和和 K。J是是不不可可行行结结点点,被被舍舍弃弃。K是是可可行行叶叶结结点点,表表示示所所求求问问题题的的一一个个可可行行解解,其价值为其价值为 45。6.1 6.1 分
17、支限界法的基本思想分支限界法的基本思想此此时时,堆堆中中仅仅剩剩下下一一个个活活结结点点C,它它成成为为当当前前扩扩展展结结点点。它它的的2个个儿儿子子结结点点F和和G均均为为可可行行结结点点,因因此此被被插插入入到到当当前前堆堆中中。结结点点F的的价价值值为为25,是是堆堆中中最最大大元元素素,成成为为下下一一个个扩扩展展结结点点。结结点点F的的2个个儿儿子子结结点点L和和M均均为为叶叶结结点点。叶叶结结点点L相相应应于于价价值值为为50的的可可行行解解。叶叶结结点点M相相应应于于价价值值为为25的的可可行行解解。叶叶结结点点L所所相相应应的的解解成成为为当当前前最最优优解解。最最后后,结结
18、点点G成成为为扩扩展展结结点点,其其儿儿子子结结点点N和和O均均为为叶叶结结点点,它它们们的的价价值值分分别别为为25和和0。接接下下来来,存存储储活活结结点点的的堆堆已已空空,算算法法终终止止。算算法法搜搜索索得得到到最最优优值值为为 50。相相应应的的最最优优解解是是从从根根结结点点 A到到结点结点L的路径(的路径(0,1,1)。)。6.1 6.1 分支限界法的基本思想分支限界法的基本思想在在寻寻求求问问题题的的最最优优解解时时,与与讨讨论论回回溯溯法法时时类类似似,可可以以用用剪剪枝枝函函数数加加速速搜搜索索。该该函函数数给给出出每每一一个个可可行行结结点点相相应应的的子子树树可可能能获
19、获得得的的最最大大价价值值的的上上界界。如如果果这这个个上上界界不不会会比比当当前前最最优优值值更更大大,则则说说明明相相应应的的子子树树中中不不含含问问题题的的最最优优解解,因因而而可可以以剪剪去去。另另一一方方面面,也也可可以以将将上上界界函函数数确确定定的的每每个个结结点点的的上上界界值值作作为为优优先先级级,以以该该优优先先级级的的非非增增序序抽抽取取当当前前扩扩展展结结点点。这这种种策略有时可以更迅速地找到最优解。策略有时可以更迅速地找到最优解。6.1 6.1 分支限界法的基本思想分支限界法的基本思想旅行售货员问题旅行售货员问题旅行售货员问题旅行售货员问题1234206305410A
20、BCDEFGHIJKLMNOPQ1234344342232432问问问问题题题题描描描描述述述述:某某某某售售售售货货货货员员员员要要要要到到到到若若若若干干干干城城城城市市市市去去去去推推推推销销销销商商商商品品品品,已已已已知知知知各各各各城城城城市市市市之之之之间间间间的的的的路路路路程程程程,他他他他要要要要选选选选定定定定一一一一条条条条从从从从驻驻驻驻地地地地出出出出发发发发,经经经经过过过过每每每每个个个个城城城城市市市市一一一一遍遍遍遍,最最最最后后后后回回回回到到到到住住住住地地地地的的的的路路路路线线线线,使使使使总总总总的路程最短。的路程最短。的路程最短。的路程最短。6.
21、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 分支限界法的基本思
22、想分支限界法的基本思想 旅行售货员问题旅行售货员问题旅行售货员问题旅行售货员问题 优先队列式分支限界法:优先队列式分支限界法:优先队列式分支限界法:优先队列式分支限界法: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)限界掉限界掉1234206305410ABCDEFGHIJKLMNOPQ12343
23、443423224236.1 6.1 分支限界法的基本思想分支限界法的基本思想解解此此问问题题的的队队列列式式分分支支限限界界法法以以排排列列树树中中结结点点B作作为为初初始始扩扩展展结结点点。此此时时,活活结结点点队队列列为为空空。由由于于从从图图G的的顶顶点点1到到顶顶点点2,3和和4均均有有边边相相连连,所所以以结结点点B的的儿儿子子结结点点C,D,E均均为为可可行行结结点点,它它们们被被加加入入到到活活结结点点队队列列中中,并并舍舍去去当当前前扩扩展展结结点点B。当当前前活活结结点点队队列列中中的的队队首首结结点点C成成为为下下一一个个扩扩展展结结点点。由由于于图图G的的顶顶点点2到到
24、顶顶点点3和和4有有边边相相连连,故故结结点点C的的2个个儿儿子子结结点点F和和G均均为为可可行行结结点点,从从而而被被加加入入到到活活结结点点队队列列中中。接接下下来来,结结点点D和和结结点点E相相继继成成为为扩扩展展结结点点而而被被扩扩展展。此此时,活结点队列中的结点依次为时,活结点队列中的结点依次为F,G,H,I,J,K。6.1 6.1 分支限界法的基本思想分支限界法的基本思想结结点点F成成为为下下一一个个扩扩展展结结点点,其其儿儿子子结结点点L是是叶叶结结点点。此此时时找找到到了了一一条条旅旅行行售售货货员员回回路路,其其费费用用为为59。从从下下一一个个扩扩展展结结点点G得得到到叶叶
25、结结点点M,它它相相应应的的旅旅行行售售货货员员回回路路的的费费用用为为66。结结点点H依依次次成成为为扩扩展展结结点点,得得到到结结点点N相相应应的的旅旅行行售售货货员员回回路路,其其费费用用为为25,这这是是当当前前最最好好的的一一条条回回路路。下下一一个个扩扩展展结结点点是是结结点点I,由由于于从从根根结结点点到到叶叶结结点点I的的费费用用26已已超超过过了了当当前前最最优优值值,故故没没有有必必要要扩扩展展结结点点I,以以结结点点I为为根根的的子子树树被被剪剪去去。最最后后,结结点点J和和K被被依依次次扩扩展展,活活结结点点队队列列成成为为空空,算算法法终终止止。算算法法搜搜索索得得到
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分支限界法 分支 限界 PPT 课件
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内