电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本
换一换
首页 金锄头文库 > 资源分类 > PPT文档下载
分享到微信 分享到微博 分享到QQ空间

算法9_分枝限界法

  • 资源ID:26280879       资源大小:1.14MB        全文页数:57页
  • 资源格式: PPT        下载积分:10金贝
快捷下载 游客一键下载
账号登录下载
微信登录下载
三方登录下载: 微信开放平台登录   支付宝登录   QQ登录  
二维码
微信扫一扫登录
下载资源需要10金贝
邮箱/手机:
温馨提示:
快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
如填写123,账号就是123,密码也是123。
支付方式: 支付宝    微信支付   
验证码:   换一换

 
账号:
密码:
验证码:   换一换
  忘记密码?
    
1、金锄头文库是“C2C”交易模式,即卖家上传的文档直接由买家下载,本站只是中间服务平台,本站所有文档下载所得的收益全部归上传人(卖家)所有,作为网络服务商,若您的权利被侵害请及时联系右侧客服;
2、如你看到网页展示的文档有jinchutou.com水印,是因预览和防盗链等技术需要对部份页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有jinchutou.com水印标识,下载后原文更清晰;
3、所有的PPT和DOC文档都被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;下载前须认真查看,确认无误后再购买;
4、文档大部份都是可以预览的,金锄头文库作为内容存储提供商,无法对各卖家所售文档的真实性、完整性、准确性以及专业性等问题提供审核和保证,请慎重购买;
5、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据;
6、如果您还有什么不清楚的或需要我们协助,可以点击右侧栏的客服。
下载须知 | 常见问题汇总

算法9_分枝限界法

第9章 分枝限界法,学习要点:理解分枝限界法的剪枝搜索策略。分枝限界法与回溯法的异同。掌握几种常见的分枝限界法思想:(1)FIFO(先进先出)分枝限界法(2)LIFO(堆栈,即D-检索)分枝限界法(3)LC(优先权队列)分枝限界法 分枝限界法的算法框架。通过应用范例学习分枝限界法的设计策略。(1)15谜问题(2)带时限的作业排序(3)0/1背包,章节内容:9.1 一般方法9.2 求最优解的分枝限界法9.3 带时限的作业排序9.4 0/1背包,9.1分枝限界法的一般方法,采用广度优先产生状态空间树的结点,并使用剪枝函数的方法称为分枝限界法。分枝限界法的基本做法是:以广度优先的方式搜索问题的状态空间树。每一个活结点只有一次机会成为扩展结点。按照广度优先的原则,活结点一旦成为扩展结点(E结点)R后,就依次生成它的所有孩子结点。在这些孩子结点中,导致不可行解或导致非最优解的孩子结点被舍弃,其余孩子结点被一一加入活结点表中。 此后,R自身成为死结点,从活结点表中取下一结点成为当前扩展结点,并重复上述结点扩展过程。 这个过程一直持续到找到所需的解或活结点表为空时为止。,分枝限界法与回溯法的异同,一、分枝限界法与回溯法的共同点都是在问题的状态空间树上搜索问题解的算法,都通过活结点表实现。都用约束函数剪去不含答案结点的分枝,用限界函数剪去不含最优解的分枝.二、分枝限界法与回溯法的区别(1)求解目标不同:回溯法的求解目标是找出解空间树中满足约束条件的所有可行解;而分枝限界法的求解目标则是找出满足约束条件的一个可行解,或某种意义下的最优解。(2)搜索方式不同:回溯法以深度优先的方式搜索解空间树,而分枝限界法则以广度优先的方式搜索解空间树。(3)对当前扩展结点的扩展方式不同:回溯法中的每个活结点可能多次成为当前扩展结点,纵深方向扩展其一个儿子,然后再回溯后扩展其他儿子;而分枝限界法中每一个活结点只有一次机会成为扩展结点,一次产生所有孩子结点,自身成为死结点,之后无需再返回该结点处。,分枝限界法的种类,根据从活结点中选择下一个扩展结点的不同次序,将分枝限界法分为三类:,(1)队列式(FIFO)分枝限界法:将活结点表组织成一个队列,按队列的先进先出(FIFO)原则选取下一个结点为当前扩展结点;(2)堆栈式(LIFO)分枝限界法:将活结点表组织成一个堆栈,按堆栈的后进先出(LIFO)原则选取下一个结点为当前扩展结点;(3)优先队列式(LC)分枝限界法:将活结点表组织成一个优先队列,并按优先队列中规定的结点优先级选取优先级最高的下一个结点为当前扩展结点。,程序9-1 分枝限界法的算法框架 (为简化起见,用指针代表所指向的结点)void BranchBound(Node *t) /t是指向状态空间树的根结点指针 do /lst为活结点表,表中元素为指针类型; for (对结点E的每个不受限的孩子) x=new Node;x->parent=E;/构造E的孩子结点x if (x是一个答案结点) 输出从x到t的一条路径; return; /输出一个可行解后,算法终止 lst.Append(x);/否则(x不是答案结点)x进活结点表if (lst.IsEmpty()/活结点表lst为空时 cout<<“没有答案结点”; return; /搜索失败终止lst.Serve(E);/从活结点表lst中输出一个活结点为E-结点 while(1);,求得一个可行解后终止,利用FIFO分枝限界法求解4-皇后问题时,实际生成的部分状态空间树如图9-1所示 (请与P182 图8-6比较) :,比较图8-6和图9-1可以看到:(n-皇后问题求第一个可行解时) FIFO分枝限界法并不占优势.,LC分枝限界法,从活结点表中选择下一个扩展结点(E结点)时,通过衡量一个活结点的搜索代价,来确定哪个活结点能够尽快到达一个答案结点。,答案结点X的搜索代价cost(X):从根结点开始,直到搜索到答案结点X为止所耗费的搜索时间.,代价函数 :从根结点到X的搜索代价。若X是答案结点,则 是从根结点到X的搜索代价;若X不是答案结点且子树X上不含任何答案结点,则 =;若X不是答案结点但子树X上包含答案结点,则 等于子树X上具有最小搜索代价的答案结点的代价.(见图9-2 (a) ),定义4个相关函数:,相对代价函数 :衡量一个结点X的相对代价。衡量标准一:生成答案结点前,子树X上需要生成的结点数目衡量标准二:子树X上离X最近的答案结点到X的路径长度(见图9-2 (b) ),相对代价估计函数 :估计结点X的相对代价。 是 的估计值,是X到达一个答案结点所需代价的估计一般的,若Y是X的孩子,则 。,结点的代价和相对代价都难以计算,因此通常采用它们的估计值作为评价函数:,代价估计函数 :由两个部分组成:从根到X的代价f(X)和从X到答案结点的估计代价 ,即 。一般的,f(X)为X在树中的层次。,以代价估计函数 最小的活结点作为下一个扩展结点(E结点)的搜索策略称为最小成本检索,简称LC-检索。,如果 ,则 ,LC-检索表现出深度优先搜索特性,成为D-检索(LIFO检索)。,如果 ,且f(X)等于X在树中的层次,则LC-检索表现出宽度优先搜索特性,成为FIFO检索。,15谜问题,问题描述:在一个4×4的方形棋盘上放置了15块编了号的牌,还剩下一个空格。号牌的一次合法移动是指将位于空格四周(上、下、左、右)的一块号牌移入空格位置的四种移动方式。要求:对于任意给定的一种初始排列,通过一系列的合法移动,将给定的初始排列转换成如图9-3 (c)所示的目标排列:,注意:(一个4×4的棋盘有16!种不同的排列)并非所有可能的状态作为初始状态都能到达目标状态。,采用广度优先搜索由初始状态图9-3(b)移动号牌得到目标状态图9-3(c)的过程。(见图9-4状态空间树),由于移动号牌和移动空格是等价的,因此从父状态到子状态的一次转换可以视为空格的一次向上、下、左或右的合法移动。图中剪去了那些与双亲状态重复的孩子结点及其子树。(即不能和上一步移动方向刚好相反)到达边界时,也无法继续移向界外方向。,第一种搜索方式: FIFO分枝限界法,采用深度优先搜索(回溯法)生成状态空间树的方式。(见图9-5部分状态空间树)深度优先搜索沿着状态生成树中最左边的路径搜索,离目标状态越来越远。,第二种搜索方式:LIFO分枝限界法(D-检索),第三种搜索方式:LC分枝限界法,定义代价估计函数: 作为搜索代价进行LC检索。(见图9-6状态空间树)其中: 是从根到结点X的路径长度, 是不在其位的非空白牌数目。 可以看到这种代价估计函数对这一实例十分有效。,课堂作业,判断由如图(a)所示的初始状态出发,经过一系列合法的号牌移动能否到达图(b)所示的目标状态?为什么?如果可以到达目标状态,请画出其LC分枝限界法实际生成的那部分状态空间树。,(a),(b),课外提高题,请编程实现用LC分枝限界法求解15迷问题。,9.2 求最优解的分枝限界法,定义一个与最优化问题的目标函数有关的代价函数(不同于上一节的搜索代价)和上下界函数:,用分枝限界法求最优解时,需要使用上下界函数作为限界函数(也即一种剪枝函数),以剪去不含最优解的分枝。,定义9-1: 状态空间树上一个结点X的代价函数 定义为:若X是答案结点,则c(X)为X所代表的可行解的目标函数值;若X为非可行解结点,则c(X)=;若X代表部分向量,则c(X)是以X为根的子树上具有最小代价的结点代价。,定义9-2: 函数 和 分别是代价函数 的上界和下界函数。对所有结点X,总有,难以计算,基于上下界函数的分枝限界法,对任意结点X,若 ,则X子树可以剪枝。,因为c(X)是X子树上最小代价答案结点的代价, 是其下界。而U是迄今已知的最小代价答案结点的代价值(即:整个树最小代价的上界值)。现若有 ,必可断定:X子树上不含最小代价答案结点。,(假定目标函数取最小值时为最优解。)设定一个上界变量U,记录迄今为止已知的最小代价答案结点的代价值(即最小代价的上界值,最小代价答案结点的代价值不会超过U)。,基于上下界函数的分枝限界法,对任意结点X,若 ,则X子树可以剪枝。,(假定目标函数取最小值时为最优解。)设定一个上界变量U,记录迄今为止已知的最小代价答案结点的代价值(即最小代价的上界值,最小代价答案结点的代价值不会超过U)。,U的值是不断修改的,根据搜索中获取的越来越多关于最小代价的上界信息,逐渐逼近最小代价答案结点的代价值(即整棵树的最小目标函数值最优解值)。,在算法已经搜索到一个答案结点之后,所有满足 的子树X都可以剪除。,基于上下界函数的分枝限界法,求最优解的限界方法:(按以下原则修正U的值)如果X是答案结点,cost(X)是X所代表的可行解的目标函数值,则U =mincost(X),U;如果X代表部分分量,u(X)是该子树上最小代价答案结点代价的上界值,则U=minu(X)+,U;于是,算法可使用 作为剪枝条件尽可能剪除多余分枝。,Livelist lst(mSize);Node *ans=null,*x,*E=t;/lst为FIFO队列do for ( 对结点E的每个孩子) x=new Node;x->parent=E;if ( )/若 ,则x不会被限界函数剪枝 lst.Append(x);/x进FIFO队列lst if (x是一个答案结点 ,基于上下界函数的FIFO分枝限界法:,Livelist lst(mSize);Node *ans=null,*x,*E=t;/lst为优先权队列do for ( 对结点E的每个孩子) x=new Node;x->parent=E;if ( )/若 ,则x不会被限界函数剪枝 lst.Append(x);/x进优先权队列lst if (x是一个答案结点 ,基于上下界函数的LC分枝限界法:,9.3 带时限的作业排序,n个作业,每个作业i处理所需时间为ti,如果能够在时限di内完成将可收益pi。将每个作业所需的处理时间、要求时限和收益用三元组(ti,di,pi) 0i<n表示。求使得总收益最大的作业子集J。,采用可变大小元组(x0,x1,.,xk)表示解,xi为作业编号。,例9-1 设有带时限的作业排序实例:n=4,(p0,d0,t0)=(5,1,1),(p1,d1,t1)=(10,3,2),(p2,d2,t2)=(6,2,1),(p3,d3,t3)=(3,1,1),求使得总收益最大的作业子集J。,显式约束:xi0, 1, ., n-1 且 xi<xi+1隐式约束:对入选子集J的作业(x0,x1,.,xk)存在一种作业排列使J中作业均能如期完成。,

注意事项

本文(算法9_分枝限界法)为本站会员(壹****1)主动上传,金锄头文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即阅读金锄头文库的“版权提示”【网址:https://www.jinchutou.com/h-59.html】,按提示上传提交保证函及证明材料,经审查核实后我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.