- 1、本文档共42页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
计算机算法设计与分析 North China Electric Power University Computer Algorithms Design Analysis 华北电力大学计算机科学与工程系 Dept. of Computer ScienceEngineering of North China Electric Power University 第五章 贪心算法(Greedy Algorithm) ★ 活动安排问题 ★ 最优装载 ★ 单源最短路径 ★ 最小生成树 ★ 多机调度问题 North China Electric Power University ★ 贪心算法的基本要素 例 找钱问题: 假定有四种面值分别为二角五分、一角、五分和一分,现要找给某顾客六角三分钱,问怎样找钱,才能使所拿出的硬币个数是最少的? 分析与解答: 1. 动态规划算法 设ak是找k分钱所需的最少硬币个数,则存在如下递归关系: ak=1+min{ak-25,ak-10,ak-5,ak-1} 2. 贪心算法:每次尽可能将面值大的硬币找给客户。 问题的解为:需要找6枚硬币,面值分别为: {25分,25分,10分,1分,1分,1分} 该解是问题的一个整体最优解。 §1 活动安排问题 North China Electric Power University 问题的描述: 设有n个活动的集合E={1,2, …,n},其中每个活动都要求使用同一资源,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si 和结束时间fi 且si fi 。如果选择了活动i,则它在半开时间区间 [si ,fi ) 内占用资源。若区间[si ,fi )与区间[sj ,fj ) 不相交,则称活动i与活动j是相容的。也就是说 ,当si ≥ fj或sj ≥ fi时,活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。 下面给出的算法GreedySelector中,各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非递减序排列。 North China Electric Power University 2.算法描述: templateclass Type void GreedySelector(int n,Type s[], Type f[],bool A[]) { A[1]=true;//表示活动进入相容集合,即活动被安排 int j=1;//进入相容集合的最后一个活动 for (int i=2;i=n;i+ +) { if (s[i]=f[j] { A[i]=ture; j=i; } else A[i]=false; } } North China Electric Power University 集合A用来存储所选择的活动。活动i在集合A中,当且仅当A[i]的值为ture。变量j用以记录最近一次加入到A中的活动。由于输入的活动是以其完成时间的非递减序排列的,所以算法GreedySelector每次总是选择具有最早完成时间的相容活动加入A中。直观上按这种方法选择相容活动就为未安排活动留下尽可能多的时间。也就是说,该算法的贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相同活动。 3.例: 设待安排的11个活动的开始时间和结束时间按时间的非减序排列如下: 14 13 12 11 10 9 8 7 6 5 4 f[i] 12 2 8 8 6 5 3 5 0 3 1 s[i] 11 10 9 8 7 6 5 4 3 2 1 i 计算过程如图: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 4 8 11 1 4 8 8 8 8 1 1 1 1 1 1 1 1 1 4 4 4 4 4 4 4 2 3 5 6
您可能关注的文档
- 第四章剪力墙平法施工图识读.ppt
- 第四章-建模技术.ppt
- 第四章抗干扰二元编码原理及方法1_抗干扰编码的基本原理.ppt
- 第四章抗干扰二元编码原理及方法2_构造检错码的基本方法.ppt
- 第四章抗干扰二元编码原理及方法5_卷积码.ppt
- 第四章抗力统计分析.ppt
- 第四章-控制工程或自动控制-上海交通大学课件.ppt
- 第四章-连续时间傅里叶变换.ppt
- 第四章门电路和组合逻辑电路.ppt
- 第四章破坏金融机构存贷款管理秩序犯罪案件侦查.ppt
- 10《那一年,面包飘香》教案.docx
- 13 花钟 教学设计-2023-2024学年三年级下册语文统编版.docx
- 2024-2025学年中职学校心理健康教育与霸凌预防的设计.docx
- 2024-2025学年中职生反思与行动的反霸凌教学设计.docx
- 2023-2024学年人教版小学数学一年级上册5.docx
- 4.1.1 线段、射线、直线 教学设计 2024-2025学年北师大版七年级数学上册.docx
- 川教版(2024)三年级上册 2.2在线导航选路线 教案.docx
- Unit 8 Dolls (教学设计)-2024-2025学年译林版(三起)英语四年级上册.docx
- 高一上学期体育与健康人教版 “贪吃蛇”耐久跑 教案.docx
- 第1课时 亿以内数的认识(教学设计)-2024-2025学年四年级上册数学人教版.docx
最近下载
- 尼康 F80&F80D&F80S 使用说明书.PDF
- 小学道德与法治思想品德课程标准试题(三套).pdf
- 上海市域铁路机场联络线与国铁共同停靠车站旅客组织方案研究.pptx VIP
- 《德国爱尔博300S智能高频电刀》.ppt VIP
- 2024新人教版初中英语七年级上全册知识点归纳总结(复习必背).pdf
- 2024年燃气公司分析报告:城燃销气量位列五大城燃第一,居民用气顺价有望修复盈利能力.pdf
- 新黄氏水有源树有根族人历来视族谱传家宝那因为其载承了源流世系.pdf
- 新版标准-《管道外防腐补口技术规范》征求意见稿.doc
- 人教版九年级语文试卷-试卷答案.doc VIP
- 口腔科常见疾病诊疗规范诊疗指南2022版.pdf VIP
文档评论(0)