您所在位置：网站首页 > 医学/心理学 > 医学现状与发展算法9_分枝限界法

算法9_分枝限界法

57页

卖家[上传人]：壹****1

文档编号：26280879

上传时间：2017-12-24

文档格式：PPT

文档大小：1.14MB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 金贝

/ 57 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、第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自身成为死结点，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。,分枝限界法与回溯法的异同,一

2、、分枝限界法与回溯法的共同点都是在问题的状态空间树上搜索问题解的算法,都通过活结点表实现。都用约束函数剪去不含答案结点的分枝,用限界函数剪去不含最优解的分枝.二、分枝限界法与回溯法的区别（1）求解目标不同：回溯法的求解目标是找出解空间树中满足约束条件的所有可行解；而分枝限界法的求解目标则是找出满足约束条件的一个可行解，或某种意义下的最优解。（2）搜索方式不同：回溯法以深度优先的方式搜索解空间树，而分枝限界法则以广度优先的方式搜索解空间树。（3）对当前扩展结点的扩展方式不同：回溯法中的每个活结点可能多次成为当前扩展结点，纵深方向扩展其一个儿子，然后再回溯后扩展其他儿子；而分枝限界法中每一个活结点只有一次机会成为扩展结点，一次产生所有孩子结点，自身成为死结点，之后无需再返回该结点处。,分枝限界法的种类,根据从活结点中选择下一个扩展结点的不同次序，将分枝限界法分为三类：,（1）队列式(FIFO)分枝限界法：将活结点表组织成一个队列，按队列的先进先出(FIFO)原则选取下一个结点为当前扩展结点；（2）堆栈式(LIFO)分枝限界法：将活结点表组织成一个堆栈，按堆栈的后进先出(LIFO)原则选取下

3、一个结点为当前扩展结点；（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为空时 coutparent=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) 0in表示。求使得总收益最大的作业子集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 且 xixi+1隐式约束：对入选子集J的作业(x0,x1,.,xk)存在一种作业排列使J中作业均能如期完成。,

《算法9_分枝限界法》由会员壹****1分享，可在线阅读，更多相关《算法9_分枝限界法》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源

高考地理总复习人教通用习题：课时提升作业八 2.4 Word版含答案

2021年07月中共北海市海城区委统战部招聘1人（广西）模拟卷

项目组文档管理实施办法

古老的中华文明的教学设计

考点12体液调节

学习《巴山魂西铁人》心得体会范本（4篇）

贫困户基本情况登记表

做一个有文化底蕴的教师.doc

卵巢癌常用的化疗方案

高中物理运动学公式解题经验

平板电脑市场调研报告

庆典活动领导致辞稿(2篇)

物流客服个人工作总结样本（2篇）.doc

幼儿园地球日活动总结

小学生祖国在我心中演讲稿模板集锦五篇

干细胞与再生医学产业化项目可行性研究报告模板-备案立项

物流成本管理试卷含答案

个人房屋买卖合同范本

高中学生会竞选稿

瑞文智力测验及答案(经典版)

点击查看更多

新上传的PPT文档

中国医科大学21秋《康复护理学》平时作业二参考答案84 2023渔家傲·思教案加薪申请书说明文十种说明方法 2013年长春市中考数学试题及答案中秋节活动策划实施计划方案管理习题及答案(简答) 计算机应用实施性教学计划本幼儿园中班数学活动《会变的圆》装饰装修工程监理细则 (3) 福建师范大学21秋《中学物理教法研究》在线作业一答案参考70 某某车队车场日活动管理制度 IP局域网组网设计自贡工控伺服项目招商引资方案大学生团员个人小结