算法设计与分析 课件 第七章 分支限界 7.2.1 分支限界方式_第1页
算法设计与分析 课件 第七章 分支限界 7.2.1 分支限界方式_第2页
算法设计与分析 课件 第七章 分支限界 7.2.1 分支限界方式_第3页
算法设计与分析 课件 第七章 分支限界 7.2.1 分支限界方式_第4页
算法设计与分析 课件 第七章 分支限界 7.2.1 分支限界方式_第5页
已阅读5页，还剩2页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

计算机算法设计与分析第7章分支限界法7.2.1分支限界方式分支限界法根据从活结点表中选择下一个扩展结点的方式，可分为队列式分支限界和优先队列式分支限界。（1）队列式分支限界法队列式（FIFO）式分支限界法的基本思想：（1）首先将初始状态节点放入活结点队列中。（2）若队列非空，则重复下列步骤：①出队，将出队结点作为当前扩展结点。②判断当前扩展结点是否为目标结点，若是目标结点，则搜索到一个可行解而结束。③对当前扩展结点进行扩展。在扩展节点时，一次性产生它的所有子结点，并利用剪枝函数检测，把满足约束和限界条件的的子结点依次加入活结点队列。（3）重复（2），直到队列为空，则搜索失败结束。（2）优先队列式分支限界法将活结点表组成一个优先队列，按照优先队列中指定的结点优先级，选取优先级最高的结点作为当前扩展结点，以优先队列储存活结点。结点的优先级常用一个与该结点相关的限界函数值来表示。也称为最小耗费优先分支限界法(LC)该策略与队列式分支限界法的主要区别是：优先队列式分支限界法的活结点表组成一个优先队列，每个活结点入队时会计算其优先级，优先级最高的活结点位于队首位置。（2）优先队列式分支限界法优先队列通常采用堆数据结构来组织，通过维护堆属性，可以保证优先队列的入队操作时按结点元素优先级重新排序，也即队列中优先级最高的结点元素始终位于队列首部位置。每次出队的队首结点总是当前队列中具有优先级最高（最有利）的结点成为当前扩展结点，使搜索朝着解空间树有最优解的分支方向快速推进，以便快速找到问题的最优解。优先队列式分支限界法基本思想（1）确定合理的限界函数，并根据限界函数确定问题的目标函数的上（下）界，又称耗费函数值或代价值。（2）初始化一个空的优先队列H，并将初始状态加入队列。初始化一个变量best_score用于保存当前找到的最优解（初值=无穷大）。（3）当队列H不为空时，执行以下步骤：优先队列式分支限界法基本思想

①出队结点保存为node。

②ifnode结点对应更优的解then更新当前最优解best_score的值。③fornode的每一个子结点child：a.计算child结点的目标函数限界值。b.ifchild满足解的约束条件且耗费函数值不超过

目标函数的当前限界thenc.将child加入

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论