内蒙古大学《算法与数据结构》讲义17分枝定界
20页1、下载第1 7章分 枝 定 界任何美好的事情都有结束的时候。现在我们学习的是本书的最后一章。幸运的是,本章用到的大部分概念在前面各章中已作了介绍。类似于回溯法,分枝定界法在搜索解空间时,也经常使用树形结构来组织解空间(常用的树结构是第 1 6章所介绍的子集树和排列树) 。然而与回溯法不同的是,回溯算法使用深度优先方法搜索树结构,而分枝定界一般用宽度优先或最小耗费方法来搜索这些树。本章与第1 6章所考察的应用完全相同,因此,可以很容易比较回溯法与分枝定界法的异同。相对而言,分枝定界算法的解空间比回溯法大得多,因此当内存容量有限时,回溯法成功的可能性更大。17.1 算法思想分枝定界(branch and bound)是另一种系统地搜索解空间的方法,它与回溯法的主要区别在于对E-节点的扩充方式。每个活节点有且仅有一次机会变成 E-节点。当一个节点变为E-节点时,则生成从该节点移动一步即可到达的所有新节点。在生成的节点中,抛弃那些不可能导出(最优)可行解的节点,其余节点加入活节点表,然后从表中选择一个节点作为下一个E-节点。从活节点表中取出所选择的节点并进行扩充,直到找到解或活动表为空,扩充过程
2、才结束。有两种常用的方法可用来选择下一个E-节点(虽然也可能存在其他的方法) :1) 先进先出(F I F O)即从活节点表中取出节点的顺序与加入节点的顺序相同,因此活节点表的性质与队列相同。2) 最小耗费或最大收益法在这种模式中,每个节点都有一个对应的耗费或收益。如果查找一个具有最小耗费的解,则活节点表可用最小堆来建立,下一个 E-节点就是具有最小耗费的活节点;如果希望搜索一个具有最大收益的解,则可用最大堆来构造活节点表,下一个 E-节点是具有最大收益的活节点。例17-1 迷宫老鼠 考察图16-3a 给出的迷宫老鼠例子和图1 6 - 1的解空间结构。使用F I F O分枝定界,初始时取(1,1)作为E-节点且活动队列为空。迷宫的位置(1 , 1)被置为1,以免再次返回到这个位置。 (1,1)被扩充,它的相邻节点( 1,2)和(2,1)加入到队列中(即活节点表) 。为避免再次回到这两个位置,将位置( 1,2)和(2,1)置为1。此时迷宫如图1 7 - 1 a所示,E-节点(1,1)被删除。1 1 01 1 1 1 1 11 1 11 1 11 1 10 0 00 0 01 0 0a)b
3、)c)图17-1 迷宫问题的F I F O分枝定界方法节点(1,2)从队列中移出并被扩充。检查它的三个相邻节点(见图1 6 - 1的解空间) ,只有(1,3)是可行的移动(剩余的两个节点是障碍节点) ,将其加入队列,并把相应的迷宫位置置为1,所得到的迷宫状态如图17-1b 所示。节点(1,2)被删除,而下一个E-节点(2,1)将会被取出,当此节点被展开时,节点(3,1)被加入队列中,节点(3,1)被置为1,节点(2,1)被删除,所得到的迷宫如图17-1c 所示。此时队列中包含(1,3)和(3,1)两个节点。随后节点(1,3)变成下一个E-节点,由于此节点不能到达任何新的节点,所以此节点即被删除,节点(3,1)成为新的E-节点,将队列清空。节点(3,1)展开, (3,2)被加入队列中,而(3,1)被删除。 (3,2)变为新的E-节点,展开此节点后,到达节点(3,3) ,即迷宫的出口。使用F I F O搜索,总能找出从迷宫入口到出口的最短路径。需要注意的是:利用回溯法找到的路径却不一定是最短路径。有趣的是,程序 6 - 11已经给出了利用F I F O分枝定界搜索从迷宫的(1,1)位置到(
4、n,n) 位置的最短路径的代码。例17-2 0/1背包问题 下面比较分别利用F I F O分枝定界和最大收益分枝定界方法来解决如下背包问题:n=3, w=20,15,15, p=40,25,25, c= 3 0。F I F O分枝定界利用一个队列来记录活节点,节点将按照F I F O顺序从队列中取出;而最大收益分枝定界使用一个最大堆,其中的 E-节点按照每个活节点收益值的降序,或是按照活节点任意子树的叶节点所能获得的收益估计值的降序从队列中取出。本例所使用的背包问题与例1 6 . 2相同,并且有相同的解空间树。使用F I F O分枝定界法搜索,初始时以根节点A作为E-节点,此时活节点队列为空。当节点A展开时,生成了节点B和C,由于这两个节点都是可行的,因此都被加入活节点队列中,节点A被删除。下一个E-节点是B,展开它并产生了节点 D和E,D是不可行的,被删除,而 E被加入队列中。下一步节点 C成为E-节点,它展开后生成节点 F和G,两者都是可行节点,加入队列中。下一个E-节点E生成节点J和K,J不可行而被删除,K是一个可行的叶节点,并产生一个到目前为止可行的解,它的收益值为4 0。下一
5、个E-节点是F,它产生两个孩子L、M,L代表一个可行的解且其收益值为5 0,M代表另一个收益值为1 5的可行解。G是最后一个E-节点,它的孩子N和O都是可行的。由于活节点队列变为空,因此搜索过程终止,最佳解的收益值为5 0。可以看到,工作在解空间树上的 F I F O分枝定界方法非常象从根节点出发的宽度优先搜索。它们的主要区别是在F I F O分枝定界中不可行的节点不会被搜索。最大收益分枝定界算法以解空间树中的节点A作为初始节点。 展开初始节点得到节点B和C,两者都是可行的并被插入堆中,节点B获得的收益值是4 0(设x1 = 1) ,而节点C得到的收益值为0。A被删除,B成为下一个E-节点,因为它的收益值比 C的大。当展开B时得到了节点D和E,D是不可行的而被删除,E加入堆中。由于E具有收益值4 0,而C为0,因为E成为下一个E-节点。展开E时生成节点J和K,J不可行而被删除,K是一个可行的解,因此K为作为目前能找到的最优解而记录下来,然后K被删除。由于只剩下一个活节点C在堆中,因此C作为E-节点被展开,生成F、G两个节点插入堆中。F的收益值为2 5,因此成为下一个E-节点,展开后得到
《内蒙古大学《算法与数据结构》讲义17分枝定界》由会员东***分享,可在线阅读,更多相关《内蒙古大学《算法与数据结构》讲义17分枝定界》请在金锄头文库上搜索。
幼儿园大班科学活动《智能留言机》课件
幼儿园大班语言绘本阅读《手电筒看见了什么》PPT
幼儿园小班科学《教宝宝认识动物》课件
幼儿园中班语言《灰狼家的小饭桶们》教案
【国家审计报告】审计报告W-06审计处罚决定书
【企业财务管理办法】会计档案管理办法
【员工主动离职-风险防范】劳动争议判决书
【员工被动离职-后续工作】70-070员工违反有关商业秘密的约定可以索赔吗
【员工被动离职-辞退申请】第六节 员工任免通知书
【员工被动离职-后续工作】70-050因员工的原因使服务期无法完成可以索赔吗
企业岗位管理制度12办公室行为规范
企业岗位管理制度30离职人员薪资发放通知单
幼儿园春游活动美丽的公园教案
呼职院电力机车制动机讲义11高速列车和重载列车制动
武理工《运输管理》教案第1章 运输系统
中海大海洋化学讲义02海洋的形成和海水的组成——兼论地球上水的起源、变迁和循环
武理工船舶柴油机习题库及答案04燃油喷射和燃烧
厦大海洋生态学课件07海洋初级生产力
华北理工水声学课件05声波在目标上的反射和散射-1目标强度及常见声纳目标的目标强度的一般特征
武理工船舶结构与设备课件02船体结构与管系-4专用船特殊船体结构特点
2023-09-25 37页
2023-09-25 10页
2023-09-25 33页
2023-09-25 26页
2023-04-03 8页
2023-04-03 4页
2023-04-03 8页
2023-03-29 10页
2023-03-22 10页
2023-03-20 8页