正文描述:《算法设计教程03》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第三章贪心算法本章主要知识点(4~6学时):3.1活动安排问题3.2贪心算法的基本要素3.3最优装载3.4哈夫曼编码3.5单源最短路径3.6最小生成树3.7多机调度问题1引言【找零钱问题】希望用数目最少的硬币找零假设提供了数目不限的面值为25美分、10美分、5美分、及1美分的硬币。假设需要找67美分,25+25+10+5+1+1,共6枚。假设提供了数目不限的面值为11美分、5美分及1美分的硬币?找零15美分11+1+1+1+1,共5枚(贪心算法)5+5+5,共3枚(非贪心算法)在一些情况下,即使贪心算法不
2、能得到整体最优解,其最终结果却是最优解的很好近似。2引言贪心算法:总是做出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择。贪心法的基本思路:——从问题的某一个初始解出发逐步逼近给定的目标,以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时,算法停止。3引言贪心法存在的问题:1.不能保证求得的最后解是最佳的;2.不能用来求最大或最小解问题;3.只能求满足某些约束条件的可行解的范围。43.1活动安排问题【活动安排问题】就是要在所给的活动集
3、合中选出最大的相容活动子集合。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si
4、,当sj≥fi时,活动i与活动j相容。5复杂性分析由于输入的活动以其完成时间的升序排列,所以算法greedySelector每次总是选择最早完成时间的相容活动加入集合A中。为未安排活动留下尽可能多的时间。该算法的贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的活动。6一个实例例:设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下:i1234567891011S[i]130535688212f[i]45678910111213147说明若被检查的活动i的开始时间Si小于最近选择
5、的活动j的结束时间fi,则不选择活动i,否则选择活动i加入集合A中。贪心算法并不总能求得问题的整体最优解。对于活动安排问题,贪心算法greedySelector却总能求得的整体最优解,即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。8贪心算法描述publicstaticintgreedySelector(int[]s,int[]f,booleana[]){intn=s.length-1;a[1]=true;//选择最早结束活动intj=1;//j表示已安排活动编号intcount=
6、1;//已安排活动数for(inti=2;i<=n;i++)//i表示待安排活动{if(s[i]>=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列9复杂性分析算法greedySelector的效率极高。当输入的活动已按结束时间的升序排列,算法只需O(n)的时间安排n个活动,使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列,可以用O(nlogn)的时间重排
7、。103.2贪心算法的基本要素对于一个具体的问题,怎么知道是否可用贪心算法解此问题,以及能否得到问题的最优解呢?这个问题很难给予肯定的回答。但是,从许多可以用贪心算法求解的问题中看到这类问题一般具有2个重要的性质:贪心选择性质最优子结构性质。111.贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,每作一
8、次贪心选择就将所求问题简化为规模更小的子问题。122.最优子结构性质当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。130-1背包问题与背包问题0-1背包问题:给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?在选择装入背包的物品时,对每种物品i只有2种选
显示全部收起
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。