算法设计与分析 第二版 第9章 分支限界课件.ppt
《算法设计与分析 第二版 第9章 分支限界课件.ppt》由会员分享,可在线阅读,更多相关《算法设计与分析 第二版 第9章 分支限界课件.ppt(77页珍藏版)》请在三一办公上搜索。
1、第9章分支限界法Branch and Bound Method,算法设计与分析本科生课程Design and Analysis of Algorithm,海南大学信息科学技术学院College of Information Science and Technology,Hainan University,2023/1/17,2,学习目标,Chapter 8 Back Track Method,2023/1/17,Branch and Bound Method,3,第9章 分支限界法,9.1 概 述,9.2 图问题中的分支限界法,9.3 组合问题中的分支限界法,2023/1/17,Branch
2、and Bound Method,4,回溯法:按深度优先策略遍历问题的解空间树,应用约束条件、目标函数等剪枝函数实行剪枝分支限界法:按广度优先策略遍历问题的解空间树,在遍历过程中,对已经处理的每一个结点根据限界函数估算目标函数的可能取值,从中选取使目标函数取得极值的结点优先进行广度优先搜索,从而不断调整搜索方向,尽快找到问题的解。,9.1 概 述,2023/1/17,Branch and Bound Method,5,9.1 概 述,9.1.1 分支限界法的设计思想,9.1.2 分支限界法的时间性能,2023/1/17,Branch and Bound Method,6,回溯法存在的问题虽用剪
3、枝减少了搜索空间,但按深度优先策略机械地进行,搜索是盲目的。如0/1背包问题。首先将目标函数初始化为最大值,目标函数只有在有一个可行解(第一个叶子)后才有意义,此后的搜索相对来说才有方向,所以从搜索的整个过程来看还是盲目的。如TSP问题(图8.6)。分支限界法先确定一个合理的限界函数由限界函数确定目标函数的界down,up仍以穷举法的解空间树为基础,但以广度优先的原理搜索该结点的所有孩子结点,分别估算这些孩子结点的目标函数的可能取值,分支限界法的设计思想,2023/1/17,Branch and Bound Method,7,如果某孩子结点的目标函数可能取值超出目标函数的界,则将其丢弃,因为从
4、这个结点生成的解不会比目前已经得到的解更好;否则,将其加入待处理结点表(表PT)依次从表PT中选取使目标函数的值取极值的结点成为当前扩展结点,重复上述过程,直到找到最优解。目标函数的界down,up的确定对最大化问题Up由限界函数确定,down由某种启发方式得到,如贪心算法对最小化问题down由限界函数确定,up由某种启发方式得到,如贪心算法,分支限界法的设计思想,2023/1/17,Branch and Bound Method,8,例:0/1背包问题。假设有4个物品,其重量分别为(4,7,5,3),价值分别为(40,42,25,12),背包容量W=10。首先,将给定物品按单位重量价值从大到
5、小排序,结果如下:,分支限界法的设计思想,2023/1/17,Branch and Bound Method,9,确定上下界 down:应用贪心法求得近似解为(1,0,0,0),获得的价值为40,这可以作为0/1背包问题的下界。up:考虑最好情况,背包中全部装入第1个物品且可以将背包装满,则可得到一个简单上界的计算方法:up=W(v1/w1)=1010=100则目标函数的界:40,100限界函数为:,分支限界法的设计思想,2023/1/17,Branch and Bound Method,10,PT表,图9.1 0/1背包问题,分支限界法的设计思想,2023/1/17,Branch and B
6、ound Method,11,分支限界法的搜索过程如下:在根结点1 没有物品装入背包,w=0,v=0 限界函数值:ub=0+(10-0)=1010=100在结点2 物品1装入背包,w=w1=4,v=40 目标函数值:ub=40+(10-4)6=76 将结点2加入待处理结点表PT中在结点3 物品1不装入背包,w=0,v=0 目标函数值:10ub=0+(10-0)660,将结点3加入表PT中,在表PT中选取目标函数值取得极大的结点2 优先进行搜索;,分支限界法的设计思想,2023/1/17,Branch and Bound Method,12,在结点4 物品2装入背包,w=11W,不满足约束条件,
7、将结点4丢弃在结点5 物品2不装入背包,w=4,v=40 与结点2相同 目标函数值为:ub=40+(10-4)5=70 将结点5加入表PT中在结点6 物品3装入背包,w=4+5=9,v=40+25=65 目标函数值为:ub=65+(10-9)4=69 将结点6加入表PT中,在表PT中选取目标函数值取得极大的结点5 优先进行搜索,分支限界法的设计思想,2023/1/17,Branch and Bound Method,13,在结点7 物品3不装入背包,w=4,v=40,与结点5相同 目标函数值为:ub=40+(10-4)464 将结点7加入表PT中在结点8 物品4装入背包,w=12W,不满足约束
8、条件,将结点8丢弃;在结点9 物品4不装入背包,w=9,v=65,与结点6相同 目标函数值为:ub=65+(W-w)*0=65 将结点7加入表PT中,在表PT 中选取目标函数值取得极大的结点6 优先进行搜索,分支限界法的设计思想,2023/1/17,Branch and Bound Method,14,结点9是叶子结点 同时结点9 的目标函数值是表PT 中的极大值,结点9 对应的解即是问题的最优解,搜索结束在图9.1的0/1背包问题中,为了在搜索过程中构建搜索经过的树结构,设一个表PT,记录搜索过程,如图9.2。再设计了一表ST,从PT中取出最大值结点进行扩充时,将最大值结点存储到表ST中,表
9、PT和表ST的数据结构为:(物品i-1的选择结果,ub)在搜索过程中表PT和表ST 的状态如图9.2所示,分支限界法的设计思想,2023/1/17,Branch and Bound Method,15,(c)扩展结点5后(d)扩展结点6 后,最优解为(1,0,1,0)65 图9.2 方法确定0/1背包问题最优解的各分量,3,7,9,2,5,6,7,分支限界法的设计思想,2023/1/17,Branch and Bound Method,16,基本思想分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩
10、展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍弃,其余儿子结点被加入活结点表中。此后,从活结点表中取下一结点(使目标函数取得极值的结点)成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,分支限界法的设计思想,2023/1/17,Branch and Bound Method,17,分支限界法的一般过程 1根据限界函数计算目标函数的 down,up;2将待处理结点表PT 初始化为空;3.对根结点的每个孩子结点x执行下列操作 3.1 估算结点x的目标函数值value;3.2 若(value=down),则
11、将结点x加入表PT中;4循环直到某个叶子结点的目标函数值在表PT中最大4.1 i=表PT中值最大的结点;4.2 对结点i的每个孩子结点x执行下列操作4.2.1 估算结点x的目标函数值value;4.2.2 若(value=down),则将结点x加入表PT中;4.2.3 若(结点x是叶子结点且value值在表PT中最大),则将结点x对应的解输出,算法结束;4.2.4 若(结点x是叶子结点但value值在表PT中不是最大),则令down=value,并且将表PT中所有小于value的结点删除;,分支限界法的设计思想,2023/1/17,Branch and Bound Method,18,目标函数
12、“界”的特性问题的解向量为X=(x1,x2,xn),其中,xi 的取值范围为某个有穷集合Si,|Si|=ri(1in)是部分解,是相应的界对最小值问题,称为下界,意思是向下搜索所可能取得的值最小不会小于这些下界。若X=(x1,x2,xn)是所得到的部分解,满足:,分支限界法的设计思想,2023/1/17,Branch and Bound Method,19,对最大值问题,称为上界,意思是向下搜索所可能取得的值最大不会大于这些上界。若 是所得到的部分解,满足:,分支限界法的设计思想,2023/1/17,Branch and Bound Method,20,两种分支方法设解向量 X=(x1,x2,
13、xn)xi 的取值范围为有穷集Si,|Si|=n,1in每棵子树都有ni个分支最坏情况下,结点表的空间为O(n1*n2*nn)若状态空间树是完全n叉树,n1=n2=nn=n,结点表的空间为O(nn)每棵子树只有两个分支xi 取特定值的分支、及不取特定值的分支:状态空间树是完全二叉树,最坏情况下结点表的空间为O(2n),分支限界法的设计思想,2023/1/17,Branch and Bound Method,21,用分支限界法求解问题的关键如何确定合适的限界函数限界函数用于估算结点的目标函数的可能取值。好的限界函数不仅计算简单,还要保证最优解在搜索空间中,更重要的是能尽早对超出目标函数界的结点进
14、行剪枝,减少搜索空间。有时需要对具体的问题实例进行大量实验才能确定一个合理的限界函数。如何组织待处理结点表为提高查找极值的效率,待处理结点表PT可采用堆或优先队列的形式存储。,分支限界法的设计思想,2023/1/17,Branch and Bound Method,22,用分支限界法求解问题的关键(续)如何确定最优解中的各个分量分支限界法对问题的解空间树中结点的处理是跳跃式的,回溯也不是单纯地沿着双亲结点一层一层向上回溯,因此当搜索到最优解(叶子结点)时,却无法求得该叶子结点对应的最优解中的各个分量。解决方法:对每个扩展结点保存根结点到该结点的路径;在搜索过程中构建搜索经过的树结构,在求得最优
15、解时,从叶子结点不断回溯到根结点,以确定最优解中的各个分量。,分支限界法的设计思想,2023/1/17,Branch and Bound Method,23,(c)扩展结点5后(d)扩展结点6 后,最优解为(1,0,1,0)65 图9.3 方法确定0/1背包问题最优解的各分量,3,7,9,2,5,6,7,分支限界法的设计思想,2023/1/17,Branch and Bound Method,24,9.1 概 述,9.1.1 分支限界法的设计思想,9.1.2 分支限界法的时间性能,2023/1/17,Branch and Bound Method,25,与回溯法相同点分支限界法和回溯法实际上都
16、是基于蛮力法,遍历具有指数阶个结点的解空间树在最坏情况下,时间复杂性肯定为指数阶2n或nn与回溯法不同点分支限界法首先扩展解空间树中的上层结点,并用限界函数大范围剪枝根据限界函数不断调整搜索方向,选择最有可能取得最优解的子树优先进行搜索如果选择了结点的合理扩展顺序以及设计好的限界函数,分支界限法可以快速得到问题的解,9.1.2 分支限界法的时间性能,2023/1/17,Branch and Bound Method,26,分支限界法的代价首先,设计一个好的限界函数通常需要花费更多的时间计算相应的目标函数值,而且对于具体的问题实例,通常需要进行大量实验,才能确定一个好的限界函数;其次,分支限界法
17、对解空间树中结点的处理是跳跃式的,因此,在搜索到某个叶子结点得到最优值时,为了从该叶子结点求出对应的最优解中的各个分量,需要对每个扩展结点保存该结点到根结点的路径,或者在搜索过程中构建搜索经过的树结构,这使得算法的设计较为复杂;再次,分支限界法为维护PT 表需要较大的存储空间,在最坏情况下,分支限界法需要的空间复杂性是指数阶。,9.1.2 分支限界法的时间性能,2023/1/17,Branch and Bound Method,27,第9章 分支限界法,9.1 概 述,9.2 图问题中的分支限界法,9.3 组合问题中的分支限界法,9.2 图问题中的分支限界法,9.2.1 TSP问题,9.2.2
18、 多段图的最短路径问题,28,Branch and Bound Method,算法设计与分析,2023/1/17,Branch and Bound Method,29,9.2.1 TSP问题,TSP问题是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次然后回到出发城市,并要求所走的路程最短。,C=,3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3,(a)一个无向图(b)无向图的代价矩阵图9.4 无向图及其代价矩阵,2023/1/17,Branch and Bound Method,30,确定上界ub采用贪心法求得近似解为:135421 ub=1+2+3+7+3
19、=16 这可以作为TSP问题的上界确定下界lb把矩阵中每一行最小的元素相加,可以得到一个简单的下界:lb=1+3+1+3+2=10一个信息量更大的下界:把矩阵中每一行最小的两个元素相加再除以2,再对这个结果向上取整,就得到了一个合理的下界:lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14 则,目标函数的界:lb,ub=14,16注意:该解并不是一个合法的选择(即没构成哈密顿回路),仅给出了一个参考下界。,9.2 TSP问题,2023/1/17,Branch and Bound Method,31,部分解的目标函数值的计算方法假设当前已确定的路径为U=(r1,r2,rk
20、),则:例如图10.4所示无向图,如果部分解包含顶点U=(1,4),则该部分解的下界是:lb=(2*5+(1+3)+(3+6)+(1+2)+(2+3)/2=16,分支限界法求解TSP问题示例,2023/1/17,Branch and Bound Method,32,TSP问题的搜索过程根结点1,加入表PT,为扩展结点 目标函数:lb=(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2=14考察孩子结点。结点2:C1C2,路径长度为3 目标函数:lb=(2*3+(1+6)+(1+2)+(3+4)+(2+3)/2=14 将结点2加入待处理结点表PT中;在结点3:C1C3,路径长度为1
21、目标函数:lb=(2*1+(3+2)+(3+6)+(3+4)+(2+3)/2=14 将结点3加入表PT中在结点4:C1C4,路径长度为5 目标函数:lb=(2*5+(1+3)+(3+6)+(1+2)+(2+3)/2=16 将结点4加入表PT中,3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3,2023/1/17,Branch and Bound Method,33,在结点5:C1C5,路径长度为8 目标函数:lb=(2*8+(1+2)+(3+6)+(1+2)+(3+4)/2=19 超出目标函数的界,将结点5丢弃;处理结点2的孩子结点。结点6,C1C2C3,路径长度
22、为3+6 目标函数:lb=(2*9+(1+1)+(3+4)+(2+3)/2=16 将结点6加入表PT中在结点7,C1 C2C4,路径长度为3+7 目标函数lb=(2*10+(1+3)+(1+2)+(2+3)/2=16 将结点7加入表PT中,分支限界法求解TSP问题示例,在表PT中选取目标函数值极小的结点2优先进行搜索,3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3,2023/1/17,Branch and Bound Method,34,在结点8,C1 C2C5,路径长度为3+9目标函数:lb=(2*12+(1+2)+(1+2)+(3+4)/2=19超出目标函数
23、的界,将结点8丢弃处理结点3的孩子。结点9,C1 C3C2,路径长度为1+6 目标函数值:lb=(2*7+(3+3)+(3+4)+(2+3)/2=16 将结点9加入表PT中在结点10,C1 C3C4,路径长度为1+4 目标函数:lb=(2*5+(3+3)+(3+6)+(2+3)/2=15 将结点10加入表PT中,分支限界法求解TSP问题示例,在表PT中选取目标函数值极小的结点3优先进行搜索,3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3,2023/1/17,Branch and Bound Method,35,在结点11,C1C3C5,路径长度为1+2 目标函数
24、值:lb=(2*3+(3+3)+(3+6)+(3+4)/2=14 将结点11加入表PT中,在表PT中选取目标函数值极小的结点11优先进行搜索,处理结点11的孩子。结点12,C1C3C5C2,路径长度为1+2+9,目标函数值:lb=(2*12+(3+3)+(3+4)/2=19 超出目标函数的界,将结点12丢弃在结点13,C1C3 C5C4,路径长度为1+2+3 目标函数值:lb=(2*6+(3+4)+(3+6)/2=14,将结点13加入表PT中,在表PT中选取目标函数值极小的结点13优先进行搜索,3 1 5 8 3 6 7 9 1 6 4 2 5 7 4 3 8 9 2 3,2023/1/17,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法设计与分析 第二版 第9章 分支限界课件 算法 设计 分析 第二 分支 限界 课件
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-2138101.html