算法课件(六)分支定界.ppt
《算法课件(六)分支定界.ppt》由会员分享,可在线阅读,更多相关《算法课件(六)分支定界.ppt(32页珍藏版)》请在三一文库上搜索。
1、1,分支限界法,2,1 概述 2 分支限界法 3 应用举例,3,1. 概述,搜索法 在动态产生问题的解空间,并搜索问题的可行解或最优解。 在生成的结点中,抛弃那些不满足约束条件(或者说不可能导出最优可行解)的结点。 搜索方式 深度优先搜索 广度优先搜索,4,1. 概述,方法1:深度优先搜索 通常深度优先搜索法不全部保留结点,扩展完的结点从数据存储结构栈中弹出删去,这样,一般在数据栈中存储的结点数就是解空间树的深度,因此它占用空间较少。 所以,当搜索树的结点较多,用其它方法易产生内存溢出时,深度优先搜索不失为一种有效的求解方法。,5,1. 概述,方法2:广度优先搜索 广度优先搜索算法,一般需存储
2、产生的所有结点,占用的存储空间要比深度优先搜索大得多,因此,程序设计中,必须考虑溢出和节省内存空间的问题。 但广度优先搜索法一般无回溯操作,即入栈和出栈的操作,所以运行速度比深度优先搜索快。,6,2. 分支限界法,采用广度优先产生状态空间树的结点,并使用剪枝函数的方法称为分支限界法。 所谓“分支”是采用广度优先的策略,依次生成扩展结点的所有分支(即:儿子结点)。 所谓“限界”是在结点扩展过程中,计算结点的上界(或下界),边搜索边减掉搜索树的某些分支,从而提高搜索效率,7,分支限界算法思想,对E-节点的扩充方式:引入活节点表 【思想】每个活节点有且仅有一次机会变成 E-节点。当一个节点变为E-节
3、点时,则生成从该节点移动一步即可到达的所有新节点。在生成的节点中,抛弃那些不可能导出(最优)可行解的节点,其余节点加入活节点表,然后从表中选择一个节点作为下一个E-节点。 从活节点表中取出所选择的节点并进行扩充,直到找到解或活动表为空,扩充过程才结束。,8,不同的活结点表形成不同的分枝限界法: FIFO分支限界法(队列式分支限界法):活结点表是先进先出队列 LIFO分支限界法:活结点表是堆栈 最小耗费或最大收益法分支限界法(优先队列式分支限界法):活结点表是优先权队列,LC分支限界法将选取具有最高优先级的活结点出队列,成为新的扩展结点。,几种常见的分支限界法,9,FIFO分支定界法,在解空间树
4、上的FIFO法,类似从根节点出发的BFS方法; 与BFS的区别在于:在FIFO分支定界中,不可行的节点不会被搜索!,10,示例1:0/1背包问题解1,FIFO分支定界,n=3, w=20,15,15, p=40,25,25, c=30,E-节点 活节点表,A,B,C,E,解1:1,0,0, 收益40,F,G,解2:0,1,1, 收益50,G,NULL,20,35,20,15,35,30,15,15,11,最大收益-分支定界思想,使用一个最大堆:其中的 E-节点按照每个活节点收益值的降序,或是按照活节点任意子树的叶节点所能获得的收益估计值的降序从队列中取出。 FIFO分支-限界算法用队存储活结点
5、,优先队列式分支限界法用堆存储活结点,以保证比较优良的结点先被扩展。且对于优先队列式分支限界算法,一旦扩展到叶结点就已经找到最优解,可以停止搜索。 采用广度优先搜索策略的目的是:尽早发现剪枝点。,12,或,堆,13,0-1背包问题解2:最大收益法,E-节点 活节点表,A,B,E,C,解1:1,0,0, 收益40,C,解2:0,1,1, 收益50,G,NULL,n=3, w=20,15,15, p=40,25,25, c=30,F,G,不可行的解:D【1,1,1】, J【1,0,1】,20,20,15,30,14,示例2:旅行商问题,FIFO分支定界,E-节点 活节点表,B,C,E,F,路径12
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 课件 分支 定界
链接地址:https://www.31doc.com/p-3488348.html