六章分支限界法.ppt
《六章分支限界法.ppt》由会员分享,可在线阅读,更多相关《六章分支限界法.ppt(33页珍藏版)》请在三一办公上搜索。
1、,第六章 分支限界法,算法设计与分析Design and Analysis of Computer Algorithm,信息工程学院张永梅,学时分配,本课程成绩由平时作业、上机实验和期末考试进行评定:,考核方法及成绩评定标准,平时作业:10%上机实验:30%期末考试:60%,考试形式为开卷,第六章 分支限界法(Branch-and-Bound),1、基本要求要求掌握分治限界法的基本思想,算法设计步骤,及常见问题的算法。要求理解分支限界法的剪枝搜索策略。,2、教学内容基本思想 0-1背包问题,第六章 分支限界法(Branch-and-Bound),6.1分支限界法的基本思想,分支限界法与回溯法,
2、(1)求解目标:回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出在某种意义下的最优解。,(2)搜索方式的不同:回溯法以深度优先的方式搜索解空间树,而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。,回溯与分支限界是对穷举法的改进。它们每次只构造候选解的一个分量,然后评估这个部分解:如果加上剩下的分量也不可能求得一个解,就不再生成剩下的分量。回溯法和分支限界都是以构造一棵状态空间树为基础,树的节点反映了对一个部分解所做的特定的选择。,6.1分支限界法的基本思想,分支限界法与回溯法,有两种生成问题状态的
3、基本方法。它们都是从根结点开始然后生成状态空间树上的其它结点。,6.1分支限界法的基本思想,如果已生成一个结点而它的所有儿子结点还没有全部生成,则这个结点叫做活结点(Live node)。当前正在生成其儿子结点的活结点叫E-结点(正在扩展的结点,Expanded node)。不再进一步扩展或者其儿子结点已全部生成的结点就是死结点(Dead node)。,在生成问题状态的两种方法中,都要有一张活结点表。问题状态的生成可以采用两种不同的方法:如果对一个E-结点R一旦生成了它的一个新的儿子C,就把C当作新的扩展结点,在完成对子树C(以C为根的子树)的穷尽搜索之后。将R结点重新变成 E-结点,继续生成
4、R的下一个儿子(如果存在)。这称做深度优先的问题状态生成法。在另一种状态生成方法中,一个E-结点一直保持到变成死结点为止。即在一个E-结点变成死结点之前,它一直是扩展结点。这实际上是一种宽度优先的问题状态生成法。,6.1分支限界法的基本思想,广度优先遍历(BFS)方法:从图的某一顶点V0出发,访问此顶点后,依次访问V0的各个未曾访问过的邻接点;然后分别从这些邻接点出发,广度优先遍历图,直至图中所有已被访问的顶点的邻接点都被访问到;若此时图中尚有顶点未被访问,则另选图中一个未被访问的顶点作起点,重复上述过程,直至图中所有顶点都被访问为止。,广度遍历:V1 V2 V3 V4 V5 V6 V7 V8
5、,6.1分支限界法的基本思想,在这两种方法中,为了避免生成那些不可能产生最佳解(或所需解)的问题状态,将用限界函数去杀死那些实际上不可能产生所需解的活结点,以减少问题的计算工作量。这样做要非常小心,以使得在处理结束时至少能生成一个答案结点;如果这个问题要求找出全部解,则要能生成所有的答案结点。使用限界函数的深度优先结点生成方法称为回溯法(backtracking)。E-结点一直保持到死为止的状态生成方法导致分枝-限界方法(branch-and-bound)。,6.1分支限界法的基本思想,6.1分支限界法的基本思想,分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。对已
6、处理的各结点根据限界函数估算目标函数的可能取值,从中选取使目标函数取得极值(极大/极小)的结点优先进行广度优先搜索不断调整搜索方向,尽快找到解。,特点:限界函数常基于问题的目标函数,适用于求解最优化问题。,6.1分支限界法的基本思想,分支限界法常以广度优先或以最小耗费(最大效益)优先的方式搜索问题的解空间树。,此后,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,在分支限界法中,每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点,就一次性产生其所有儿子结点。在这些儿子结点中,导致不可行解或导致非最优解的儿子结点被舍
7、弃,其余儿子结点被加入活结点表中。,分支限界法是最佳优先搜索法,分支限界法就是最佳优先(包括广度优先在内)的搜索法。分支限界法将要搜索的结点按评价函数的优劣排序,让好的结点优先搜索,将坏的结点剪去。所以准确说,此方法应称为界限剪支法。分支限界法中有两个要点:,评价函数的构造;搜索路径的构造。,6.1分支限界法的基本思想,评价函数的构造,评价函数要能够提供一个评定候选扩展结点的方法,以便确定哪个结点最有可能在通往目标的最佳路径上。,6.1分支限界法的基本思想,搜索路径的构造,在回溯法中,每次仅考察一条路径,因而只需要构造这一条路径即可:前进时记下相应结点,回溯时删去最末尾结点的记录。这比较容易实
8、现。在分支限界法中,是同时考察若干条路径,那么又该如何构造搜索的路径呢?,对每一个扩展的结点,建立三个信息:,(1)该结点的名称;(2)它的评价函数值;(3)指向其前驱的指针;,这样一旦找到目标,即可逆向构造其路径。,6.1分支限界法的基本思想,界限(Bounding),评价函数f(d)关系着算法的效率乃至成败。因为在大多数问题中f(d)只是个估计值,所以单靠f(d)是不够的。通常还要设计它的上、下界函数U(d)和L(d)。L(d)f(d)U(d)。所谓分支限界法就是通过评价函数及其上、下界函数的计算,将状态空间中不可能产生最佳解的子树剪去,减少搜索的范围,提高效率。因而更准确的称呼应是“界限
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分支 限界
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-5353602.html