1分支限定法.ppt_第1页
1分支限定法.ppt_第2页
1分支限定法.ppt_第3页
1分支限定法.ppt_第4页
1分支限定法.ppt_第5页
已阅读5页，还剩3页未读， 继续免费阅读

下载本文档

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

文档简介

1 分支限界法 2 学习要点理解分支限界法的剪枝搜索策略 应用范例 旅行售货员问题见材料 P225 3 分支限界法的基本思想 分支限界法与回溯法 1 求解目标 回溯法的求解目标是找出解空间树中满足约束条件的所有解 而分支限界法的求解目标则是找出满足约束条件的一个解 或是在满足约束条件的解中找出在某种意义下的最优解 2 搜索方式的不同 回溯法以深度优先的方式搜索解空间树 而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树 4 分支限界法的基本思想 分支限界法常以广度优先或以最小耗费 最大效益 优先的方式搜索问题的解空间树 此后 从活结点表中取下一结点成为当前扩展结点 并重复上述结点扩展过程 这个过程一直持续到找到所需的解或活结点表为空时为止 在分支限界法中 每一个活结点只有一次机会成为扩展结点 活结点一旦成为扩展结点 就一次性产生其所有儿子结点 在这些儿子结点中 导致不可行解或导致非最优解的儿子结点被舍弃 其余儿子结点被加入活结点表中 5 旅行售货员 旅行商 问题 1 问题描述 某售货员要到若干城市去推销商品 已知各城市之间的路程 或旅费 他要选定一条从驻地出发 经过每个城市一次 最后回到驻地的路线 使总的路程 或总旅费 最小 路线是一个带权图 图中各边的费用 权 为正数 图的一条周游路线是包括V中的每个顶点在内的一条回路 周游路线的费用是这条路线上所有边的费用之和 旅行售货员问题的解空间可以组织成一棵树 从树的根结点到任一叶结点的路径定义了图的一条周游路线 旅行售货员问题要在图G中找出费用最小的周游路线 6 旅行售货员问题 是本世纪人类要解决的25个问题之一 详细信息见 量子计算机 DNA计算机等不同方向的计算机都要用此问题来验证运算能力是NP问题之一 P问题是指能在确定型的多项式时间内完成处理的问题 NP是指非确定型的多项式 7 旅行售货员问题 2 问题分析 1 旅行线路是一个闭合的路径 是一个简单回路 2 每个旅行线路恰好包含 耗费矩阵 记为A 的每一列和每一行的一条边和它的联结的耗费 3 设A的某一行的最小的元素为mi 若这一行每个元素都减去mi 得到新的矩阵 记为B 并记A B
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

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

最新文档

评论

0/150

提交评论