贪心算法-汽车加油问题.ppt_第1页
贪心算法-汽车加油问题.ppt_第2页
贪心算法-汽车加油问题.ppt_第3页
贪心算法-汽车加油问题.ppt_第4页
贪心算法-汽车加油问题.ppt_第5页
已阅读5页，还剩1页未读， 继续免费阅读

下载本文档

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

文档简介

贪心算法 汽车加油问题 贪心算法基本思想 贪心算法总是做出在当前看来是最好的选择 并不会从总体去最优考虑 虽然贪心算法不会对所有问题找到最优 但是有时候会得到最优解的近似解 贪心算法的基本要素 1 贪心选择性质 指所求问题的整体最优解可以通过一系列局部最优的选择 即贪心选择来达到 是贪心算法和动态规划的主要区别 2 最优子结构 当一个问题包含其子问题的最优解是称此问题具有最优子结构性质 问题描述 一辆汽车加满油之后可以行驶nKM 旅途中有若干个加油站 设计一个算法指出在哪些加油站停靠加油可以是沿途加油次数最少 给定n和k个加油站位置 712345166 问题分析 1 2 3 4 5 1 6 6 假设X i 表示i 1到i号加油站之间的距离 每一次都是加满油再出发 根据贪心算法的选择性质为了要使加油次数最少就会选择离加满油的点远一点的加油站加油 另外当加满油之后 都要是此后的过程中使加油次数最少 同样 在第二次加满油之后也要使此后的加油次数最少 每一次汽车中剩下的油不能再行驶到下一站就在该站加油 每一次加满油之后与起点具有相同的条件 过程也是相同的 所以说加油次数最少也具有最优子结构的性质 贪心策略 最远加油站优先 起点 终点 第一次遍历 主要是看X i 是否大于n 若大于n是到达不了重点的 错误 第二次遍历 给定s表示加满油之后行驶的距离 如果s n 说明需要加油 加油次数sum s x i intgreedy vectorx intn intsum 0 k x size for inti 0 in return 1 for inti 0 s 0 i
人人文库> 全部分类> 行业资料 > 信息产业

温馨提示

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

最新文档

评论

0/150

提交评论