【教学课件】第6章分支限界法.ppt
《【教学课件】第6章分支限界法.ppt》由会员分享,可在线阅读,更多相关《【教学课件】第6章分支限界法.ppt(44页珍藏版)》请在三一办公上搜索。
1、,第6章 分支限界法,6.1 概述 6.2 分支限界法 6.3 应用举例本章小结,6.1 概述,搜索法在动态产生问题的解空间,并搜索问题的可行解或最优解。在生成的结点中,抛弃那些不满足约束条件(或者说不可能导出最优可行解)的结点。搜索方式深度优先搜索广度优先搜索,6.1 概述,方法1:深度优先搜索通常深度优先搜索法不全部保留结点,扩展完的结点从数据存储结构栈中弹出删去,这样,一般在数据栈中存储的结点数就是解空间树的深度,因此它占用空间较少。所以,当搜索树的结点较多,用其它方法易产生内存溢出时,深度优先搜索不失为一种有效的求解方法。,6.1 概述,方法2:广度优先搜索广度优先搜索算法,一般需存储
2、产生的所有结点,占用的存储空间要比深度优先搜索大得多,因此,程序设计中,必须考虑溢出和节省内存空间的问题。但广度优先搜索法一般无回溯操作,即入栈和出栈的操作,所以运行速度比深度优先搜索要快些。,6.2 分支限界法,什么是分支限界法采用广度优先产生状态空间树的结点,并使用剪枝函数的方法称为分枝限界法。所谓“分支”是采用广度优先的策略,依次生成扩展结点的所有分支(即:儿子结点)。所谓“限界”是在结点扩展过程中,计算结点的上界(或下界),边搜索边减掉搜索树的某些分支,从而提高搜索效率,分枝限界法的搜索策略,6.2 分支限界法,搜索策略按照广度优先的原则,一个活结点一旦成为扩展结点(E-结点)R后,算
3、法将依次生成它的全部孩子结点,将那些导致不可行解或导致非最优解的儿子舍弃,其余儿子加入活结点表中。然后,从活结点表中取出一个结点作为当前扩展结点。重复上述结点扩展过程,直至找到问题的解或判定无解为止。,6.2常见的两种分支限界法,6.2 分支限界法,几种常见的分支限界法不同的活结点表形成不同的分枝限界法,分为:1.FIFO分支限界法(队列式分支限界法)活结点表是先进先出队列 LIFO分支限界法活结点表是堆栈2.LC(least cost)分支限界法(优先队列式分支限界法)活结点表是优先权队列,LC分支限界法将选取具有最高优先级的活结点出队列,成为新的E-结点。,6.2常见的两种分支限界法,1.
4、队列式(FIFO)分支限界法,基本思想:按照队列先进先出(FIFO)原则选取下一个活结点为扩展结点。搜索策略一开始,根结点是唯一的活结点,根结点入队。从活结点队中取出根结点后,作为当前扩展结点。对当前扩展结点,先从左到右地产生它的所有儿子,用约束条件检查,把所有满足约束函数的儿子加入活结点队列中。再从活结点表中取出队首结点(队中最先进来的结点)为当前扩展结点,直到找到一个解或活结点队列为空为止。,优先队列式分支限界法,2.优先队列式分支限界法,基本思想:为了加速搜索的进程,应采用有效地方式选择活结点进行扩展。按照优先队列中规定的优先级选取优先级最高的结点成为当前扩展结点。基本策略对每一活结点计
5、算一个优先级(某些信息的函数值),并根据这些优先级;从当前活结点表中优先选择一个优先级最高(最有利)的结点作为扩展结点,使搜索朝着解空间树上有最优解的分支推进,以便尽快地找出一个最优解。再从活结点表中下一个优先级别最高的结点为当前扩展结点,直到找到一个解或活结点队列为空为止。,6.3 应用举例,例1:01背包问题例2:TSP问题例3:装载问题例4:8数码难题 例5:15迷问题,例1:01背包问题,问题描述,例1:01背包问题,分析问题的解向量:n元向量x1,x2,.,xn,xi0,1,问题的解空间:子集树搜索方式1.队列式搜索(1)队列式分支法(2)队列式分支限界法 2.优先队列式搜索(1)优
6、先队列式分支法(2)优先队列式分支限界法,0-1 背包问题,1.队列式,(1)队列式分支法:n=3,c=30,w=(16,15,15),p=(45,25,25),0-1 背包问题,1.队列式,注意:队列式分支法的搜索过程是对子集树进行盲目搜索,我们虽然不能将搜索算法改进为多项式复杂度,但若在在算法中加入了“限界”技巧,还是能降低算法的复杂度。一个简单的现象:若当前分支的“装载的价值上界”,比现有的最大装载的价值小,则该分支就无需继续搜索。,6.3 0-1 背包问题,(2)队列式分支限界法:n=3,c=30,w=(16,15,15),p=(45,25,25),1.队列式,6.3 0-1 背包问题
7、,(1)优先队列式分支法:n=3,c=30,w=(16,15,15),p=(45,25,25),2.优先队列式,0-1 背包问题,优先队列式分支法:优先队列式扩展方式,若不加入限界策略其实是无意义的。因为要说明解的最优性,不搜索完所有问题空间是不能下结论的,而要对问题空间进行完全搜索,考虑优先级也就没有意义了。事实上:优先队列式搜索通过结点的优先级,可以使搜索尽快朝着解空间树上有最优解的分支推进,这样当前最优解一定较接近真正的最优解。优先队列式分支限界法我们将优先队列搜索得到当前最优解作为一个“界”,对上界(或下界)不可能达到(大于)这个界的分支则不去进行搜索,这样就缩小搜索范围,提高了搜索效
8、率。这种搜索策略称为优先队列式分支限界法。,2.优先队列式,0-1 背包问题,(2)优先队列式分支限界法n=3,c=30,w=(16,15,15),p=(45,25,25),2.优先队列式,0-1 背包问题,例1:01背包问题,注意:看了上面的例子大家会发现优先队列法扩展结点的过程,一开始实际是在进行类似“深度优先”的搜索。,TSP问题,问题提出:分析解空间:排列树,例:TSP问题,6.4 旅行售货商问题,1.队列式分支限界,例:TSP问题,6.4 旅行售货商问题,2.优先队列式分支限界法,例:TSP问题,装载问题,问题描述有两艘船,n 个货箱。第一艘船的载重量是c1,第二艘船的载重量是c2,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 教学课件 教学 课件 分支 限界
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-5659131.html