第9章 分支限界法完精选PPT.ppt
![资源得分’ 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)
《第9章 分支限界法完精选PPT.ppt》由会员分享,可在线阅读,更多相关《第9章 分支限界法完精选PPT.ppt(57页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第第9章章 分支限界法完分支限界法完第1页,本讲稿共57页2022/10/7第9章 分支限界法 Page 29.1 概 述 9.2 图问题中的分支限界法9.3 组合问题中的分支限界法9.4 实验项目实验项目电路布线问题电路布线问题第9章 分支限界法 第2页,本讲稿共57页2022/10/7第9章 分支限界法 Page 39.1.1 解空间树的动态搜索(2)9.1.2 分支限界法的设计思想9.1.3 分支限界法的时间性能9.1 概 述 第3页,本讲稿共57页2022/10/7第9章 分支限界法 Page 4 分支限界法首先确定一个合理的限界函数,并根据限界函数确定目标函数的界down,up。然后
2、,按照广度优先策略遍历问题的解空间树,在分支结点上,依次搜索该结点的所有孩子结点,分别估算这些孩子结点的目标函数的可能取值,如果某孩子结点的目标函数可能取得的值超出目标函数的界,则将其丢弃,因为从这个结点生成的解不会比目前已经得到的解更好;否则,将其加入待处理结点表(以下简称表PT)中。依次从表PT中选取使目标函数的值取得极值的结点成为当前扩展结点,重复上述过程,直到找到最优解。9.1.1 解空间树的动态搜索(2)第4页,本讲稿共57页2022/10/7第9章 分支限界法 Page 5 随着这个遍历过程的不断深入,表PT中所估算的目标函数的界越来越接近问题的最优解。当搜索到一个叶子结点时,如果
3、该结点的目标函数值是表PT中的极值(对于最小化问题,是极小值;对于最大化问题,是极大值),则该叶子结点对应的解就是问题的最优解;否则,根据这个叶子结点调整目标函数的界(对于最小化问题,调整上界;对于最大化问题,调整下界),依次考察表PT中的结点,将超出目标函数界的结点丢弃,然后从表PT中选取使目标函数取得极值的结点继续进行扩展。第5页,本讲稿共57页2022/10/7第9章 分支限界法 Page 6 例:0/1背包问题。假设有4个物品,其重量分别为(4,7,5,3),价值分别为(40,42,25,12),背包容量W=10。首先,将给定物品按单位重量价值从大到小排序,结果如下:物品重量(w)价值
4、(v)价值/重量(v/w)144010274263525543124第6页,本讲稿共57页2022/10/7第9章 分支限界法 Page 7 应用贪心法求得近似解为应用贪心法求得近似解为(1,0,0,0),获得的价值为,获得的价值为40,这可以作为,这可以作为0/1背包问题的下界。背包问题的下界。如何求得如何求得0/1背包问题的一个合理的上界呢?考虑最背包问题的一个合理的上界呢?考虑最好情况,背包中装入的全部是第好情况,背包中装入的全部是第1个物品且可以将背包装个物品且可以将背包装满,则可以得到一个非常简单的上界的计算方法:满,则可以得到一个非常简单的上界的计算方法:ub=W(v1/w1)=1
5、010=100。于是,得到了目标函数的界于是,得到了目标函数的界40,100。第7页,本讲稿共57页2022/10/7第9章 分支限界法 Page 8假设背包中已装入物品的重量是w,获得的价值是v,计算该结点的目标函数上界的一个简单方法是把已经装入背包中的物品取得的价值v,加上背包剩余容量W-w与剩下物品的最大单位重量价值的积,于是,得到限界函数为:第8页,本讲稿共57页2022/10/7第9章 分支限界法 Page 9w=0,v=0ub=100w=4,v=40ub=76w=0,v=0ub=60w=11无效解w=4,v=40ub=70w=9,v=65ub=69w=4,v=40ub=64w=12
6、无效解w=9,v=65ub=65234567891分支限界法求解0/1背包问题第9页,本讲稿共57页2022/10/7第9章 分支限界法 Page 10 分分支支限限界界法法求求解解0/1背背包包问问题题,其其搜搜索索空空间间如如图图9.1所所示示,具具体的搜索过程如下:体的搜索过程如下:(1)在在根根结结点点1,没没有有将将任任何何物物品品装装入入背背包包,因因此此,背背包包的的重重量量和和获获得得的的价价值值均均为为0,根根据据限限界界函函数数计计算算结结点点1的的目目标标函函数数值值为为1010=100;(2)在在结结点点2,将将物物品品1装装入入背背包包,因因此此,背背包包的的重重量量
7、为为4,获获得得的的价价值值为为40,目目标标函函数数值值为为40+(10-4)6=76,将将结结点点2加加入入待待处处理理结结点点表表PT中中;在在结结点点3,没没有有将将物物品品1装装入入背背包包,因因此此,背背包包的的重重量量和和获获得得的的价价值值仍仍为为0,目目标标函函数数值值为为10660,将将结结点点3加入表加入表PT中;中;(3)在表)在表PT中选取目标函数值取得极大的结点中选取目标函数值取得极大的结点2优先进行搜索;优先进行搜索;第10页,本讲稿共57页2022/10/7第9章 分支限界法 Page 11(4)在在结结点点4,将将物物品品2装装入入背背包包,因因此此,背背包包
8、的的重重量量为为11,不不满满足足约约束束条条件件,将将结结点点4丢丢弃弃;在在结结点点5,没没有有将将物物品品2装装入入背背包包,因因此此,背背包包的的重重量量和和获获得得的的价价值值与与结结点点2相相同同,目目标标函函数数值为值为40+(10-4)5=70,将结点,将结点5加入表加入表PT中;中;(5)在在表表PT中中选选取取目目标标函函数数值值取取得得极极大大的的结结点点5优优先先进进行行搜搜索;索;(6)在在结结点点6,将将物物品品3装装入入背背包包,因因此此,背背包包的的重重量量为为9,获获得得的的价价值值为为65,目目标标函函数数值值为为65+(10-9)4=69,将将结结点点6加
9、加入入表表PT中中;在在结结点点7,没没有有将将物物品品3装装入入背背包包,因因此此,背背包包的的重重量量和和获获得得的的价价值值与与结结点点5相相同同,目目标标函函数数值值为为40+(10-4)464,将将结结点点6加加入入表表PT中;中;第11页,本讲稿共57页2022/10/7第9章 分支限界法 Page 12(7)在表PT中选取目标函数值取得极大的结点6优先进行搜索;(8)在结点8,将物品4装入背包,因此,背包的重量为12,不满足约束条件,将结点8丢弃;在结点9,没有将物品4装入背包,因此,背包的重量和获得的价值与结点6相同,目标函数值为65;(9)由于结点9是叶子结点,同时结点9的目
10、标函数值是表PT中的极大值,所以,结点9对应的解即是问题的最优解,搜索结束。第12页,本讲稿共57页2022/10/7第9章 分支限界法 Page 13 假假设设求求解解最最大大化化问问题题,解解向向量量为为X=(x1,x2,xn),其其中中,xi的的取取值值范范围围为为某某个个有有穷穷集集合合Si,|Si|=ri(1in)。在在使使用用分分支支限限界界法法搜搜索索问问题题的的解解空空间间树树时时,首首先先根根据据限限界界函函数数估估算算目目标标函函数数的的界界down,up,然然后后从从根根结结点点出出发发,扩扩展展根根结结点点的的r1个个孩孩子子结结点点,从从而而构构成成分分量量x1的的r
11、1种种可可能能的的取取值值方方式式。对对这这r1个个孩孩子子结结点点分分别别估估算算可可能能取取得得的的目目标标函函数数值值bound(x1),其其含含义义是是以以该该孩孩子子结结点点为为根根的的子子树树所所可可能取得的目标函数值不大于能取得的目标函数值不大于bound(x1),也就是部分解应满足:也就是部分解应满足:bound(x1)bound(x1,x2)bound(x1,x2,xk)bound(x1,x2,xn)9.1.2 分支限界法的设计思想 第13页,本讲稿共57页2022/10/7第9章 分支限界法 Page 14 若若某某孩孩子子结结点点的的目目标标函函数数值值超超出出目目标标函
12、函数数的的界界,则则将将该该孩孩子子结结点点丢丢弃弃;否否则则,将将该该孩孩子子结结点点保保存存在在待待处处理理结结点点表表PT中中。从从表表PT中中选选取取使使目目标标函函数数取取得得极极大大值值的的结结点点作作为为下下一一次次扩扩展展的的根根结结点点,重重复复上上述述过过程程,当当到到达达一一个个叶叶子子结结点点时时,就就得得到到了了一一个个可可行行解解X=(x1,x2,xn)及及其其目目标标函函数数值值bound(x1,x2,xn)。第14页,本讲稿共57页2022/10/7第9章 分支限界法 Page 15如如果果bound(x1,x2,xn)是是表表PT中中目目标标函函数数值值最最大
13、大的的结结点点,则则bound(x1,x2,xn)就就是是所所求求问问题题的的最最大大值值,(x1,x2,xn)就是问题的最优解;就是问题的最优解;如如果果bound(x1,x2,xn)不不是是表表PT中中目目标标函函数数值值最最大大的的结结点点,说说明明还还存存在在某某个个部部分分解解对对应应的的结结点点,其其上上界界大大于于bound(x1,x2,xn)。于于是是,用用bound(x1,x2,xn)调调整整目目标标函函数数的的下下界界,即即令令down=bound(x1,x2,xn),并并将将表表PT中中超超出出目目标标函函数数下下界界down的的结结点点删删除除,然然后后选选取取目目标标
14、函函数数值值取取得得极极大大值值的的结结点点作作为为下下一一次次扩扩展展的的根根结结点点,继继续续搜搜索索,直直到到某某个个叶叶子子结结点点的的目目标标函函数数值值在在表表PT中中最最大。大。第15页,本讲稿共57页2022/10/7第9章 分支限界法 Page 16分支限界法求解最大化问题的一般过程分支限界法的一般过程1根据限界函数确定目标函数的界down,up;2将待处理结点表PT初始化为空;3对根结点的每个孩子结点x执行下列操作 3.1 估算结点x的目标函数值value;3.2 若(value=down),则将结点x加入表PT中;4循环直到某个叶子结点的目标函数值在表PT中最大 4.1
15、i=表PT中值最大的结点;4.2 对结点i的每个孩子结点x执行下列操作 4.2.1 估算结点x的目标函数值value;4.2.2 若(value=down),则将结点x加入表PT中;4.2.3 若(结点x是叶子结点且结点x的value值在表PT中最大),则将结点x对应的解输出,算法结束;4.2.4 若(结点x是叶子结点但结点x的value值在表PT中不是最大),则令down=value,并且将表PT中所有小于value的结点删除;第16页,本讲稿共57页2022/10/7第9章 分支限界法 Page 17应用分支限界法的关键问题(1)如何确定合适的限界函数(2)如何组织待处理结点表(3)如何确
16、定最优解中的各个分量 第17页,本讲稿共57页2022/10/7第9章 分支限界法 Page 18分支限界法对问题的解空间树中结点的处理是跳跃式的,回溯分支限界法对问题的解空间树中结点的处理是跳跃式的,回溯也不是单纯地沿着双亲结点一层一层向上回溯,因此,当搜索也不是单纯地沿着双亲结点一层一层向上回溯,因此,当搜索到某个叶子结点且该叶子结点的目标函数值在表到某个叶子结点且该叶子结点的目标函数值在表PT中最大时中最大时(假设求解最大化问题),求得了问题的最优值,但是,却无(假设求解最大化问题),求得了问题的最优值,但是,却无法求得该叶子结点对应的最优解中的各个分量。这个问题可以法求得该叶子结点对应
17、的最优解中的各个分量。这个问题可以用如下方法解决:用如下方法解决:对每个扩展结点保存该结点到根结点的路径;对每个扩展结点保存该结点到根结点的路径;在在搜搜索索过过程程中中构构建建搜搜索索经经过过的的树树结结构构,在在求求得得最最优优解解时时,从叶子结点不断回溯到根结点,以确定最优解中的各个分量。从叶子结点不断回溯到根结点,以确定最优解中的各个分量。对于(3):如何确定最优解中的各个分量:第18页,本讲稿共57页2022/10/7第9章 分支限界法 Page 19(0)60 (1,0,0)64 (1,0,1,0)65(a)扩展根结点后表PT状态 (b)扩展结点2后表PT状态(c)扩展结点扩展结点
18、5后表后表PT状态状态 (d)扩展结点扩展结点6后表后表PT状态,最优解为状态,最优解为(1,0,1,0)65图图9.2 方法方法确定确定0/1背包问题最优解的各分量背包问题最优解的各分量(0)60 (1,0,1)69 (1,0,0)64(1)76 (0)60(0)60 (1,0)70 方法一:方法一:例如图例如图9.1所示所示0/1背包问题,为了对每个扩展结点保存该结点到根结背包问题,为了对每个扩展结点保存该结点到根结点的路径,将部分解点的路径,将部分解(x1,xi)和该部分解的目标函数值都存储在和该部分解的目标函数值都存储在待处理结点表待处理结点表PT中,在搜索过程中表中,在搜索过程中表P
19、T的状态如图的状态如图9.2所示。所示。第19页,本讲稿共57页2022/10/7第9章 分支限界法 Page 20(a)扩展根结点后 (b)扩展结点2后(c)扩展结点扩展结点5后后 (d)扩展结点扩展结点6后,最优解为后,最优解为(1,0,1,0)65 图图9.3 方法方法确定确定0/1背包问题最优解的各分量背包问题最优解的各分量(0,76)(0,60)PTST(0,60)(1,70)PTST(0,76)(0,60)(0,69)(0,64)PTST(0,76)(1,70)(0,60)(0,64)(1,65)PTST(0,76)(1,70)(0,69)方法二:图9.1所示0/1背包问题,为了在
20、搜索过程中构建搜索经过的树结构,设一个表ST,在表PT中取出最小值结点进行扩充时,将最小值结点存储到表ST中,表PT和表ST的数据结构为(物品i-1的选择结果,ub),在搜索过程中表PT和表ST的状态如图9.3所示。第20页,本讲稿共57页2022/10/7第9章 分支限界法 Page 21 分支限界法和回溯法实际上都属于蛮力穷举法,当然不能指望它有很好的最坏时间复杂性,遍历具有指数阶个结点的解空间树,在最坏情况下,时间复杂性肯定为指数阶。与回溯法不同的是,分支限界法首先扩展解空间树中的上层结点,并采用限界函数,有利于实行大范围剪枝,同时,根据限界函数不断调整搜索方向,选择最有可能取得最优解的
21、子树优先进行搜索。所以,如果选择了结点的合理扩展顺序以及设计了一个好的限界函数,分支界限法可以快速得到问题的解。9.1.3 分支限界法的时间性能 第21页,本讲稿共57页2022/10/7第9章 分支限界法 Page 22 分支限界法的较高效率是以付出一定代价为基础的,其工作方式也造成了算法设计的复杂性。首先,一个更好的限界函数通常需要花费更多的时间计算相应的目标函数值,而且对于具体的问题实例,通常需要进行大量实验,才能确定一个好的限界函数;其次,由于分支限界法对解空间树中结点的处理是跳跃式的,因此,在搜索到某个叶子结点得到最优值时,为了从该叶子结点求出对应的最优解中的各个分量,需要对每个扩展
22、结点保存该结点到根结点的路径,或者在搜索过程中构建搜索经过的树结构,这使得算法的设计较为复杂;再次,算法要维护一个待处理结点表PT,并且需要在表PT中快速查找取得极值的结点,等等。这都需要较大的存储空间,在最坏情况下,分支限界法需要的空间复杂性是指数阶。第22页,本讲稿共57页2022/10/7第9章 分支限界法 Page 239.2.1 TSP问题 9.2.2 多段图的最短路径问题9.2 图问题中的分支限界法 第23页,本讲稿共57页2022/10/7第9章 分支限界法 Page 24 TSP问题是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短。2
23、71563134253984C=3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3 (a)一个无向图 (b)无向图的代价矩阵图9.4 无向图及其代价矩阵9.2.1 TSP问题第24页,本讲稿共57页2022/10/7第9章 分支限界法 Page 25 采用贪心法求得近似解为采用贪心法求得近似解为135421,其路径长度为,其路径长度为1+2+3+7+3=16,这可以作为,这可以作为TSP问题的上界。问题的上界。把矩阵中每一行最小的元素相加,可以得到一个简单的把矩阵中每一行最小的元素相加,可以得到一个简单的下界,其路径长度为下界,其路径长度为1+3+1+3+2=10,
24、但是还有一个信息量更,但是还有一个信息量更大的下界:考虑一个大的下界:考虑一个TSP问题的完整解,在每条路径上,每个城市问题的完整解,在每条路径上,每个城市都有两条邻接边,一条是进入这个城市的,另一条是离开这个城市都有两条邻接边,一条是进入这个城市的,另一条是离开这个城市的,那么,如果把矩阵中每一行最小的两个元素相加再除以的,那么,如果把矩阵中每一行最小的两个元素相加再除以2,如,如果图中所有的代价都是整数,再对这个结果向上取整,就得果图中所有的代价都是整数,再对这个结果向上取整,就得到了一个合理的下界。到了一个合理的下界。lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=
25、14 于是,得到了目标函数的界于是,得到了目标函数的界14,16。需要强调的是,这个解并不是一个合法的选择(可能没有构成哈密顿需要强调的是,这个解并不是一个合法的选择(可能没有构成哈密顿回路),它仅仅给出了一个参考下界。回路),它仅仅给出了一个参考下界。第25页,本讲稿共57页2022/10/7第9章 分支限界法 Page 26部分解的目标函数值的计算方法 例如图9.4所示无向图,如果部分解包含边(1,4),则该部分解的下界是lb=(1+5)+(3+6)+(1+2)+(3+5)+(2+3)/2=16。第26页,本讲稿共57页2022/10/7第9章 分支限界法 Page 27412lb=142
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第9章 分支限界法完精选PPT 分支 限界 精选 PPT
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内