资源描述：
《《贪心算法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第四章.贪心算法(Greedmethod)例题算法设计与分析>贪心算法顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。目的：用以求解最优化问题将问题的求解过程看作是一系列选择,每次选择一个输入,每次选择都是当前状态下的最好
2、选择(局部最优解).每作一次选择后,所求问题会简化为一个规模更小的子问题.从而通过每一步的最优解逐步达到整体的最优解。4.1基本思想[算法优点]求解速度快,时间复杂性有较低的阶.[算法缺点]需证明是最优解.[常见应用]背包问题,最小生成树,最短路径,作业调度等等[适用问题]具备贪心选择和最优子结构性质的最优化问题贪心选择性质：整体的最优解可通过一系列局部最优解达到，即贪心选择到达。贪心算法通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求解的问题化简为规模更小的问题对于一个具体问题，要确定它是否具有贪心选择
3、的性质，我们必须证明每一步所作的贪心选择最终导致问题的最优解。通常可以首先证明问题的一个整体最优解，是从贪心选择开始的，而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到问题的一个整体最优解。最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。A(1)A(2)…A(n-1)A(n)某一问题的n个输入B1(1)B1(2)…B1(m)该问题的一种解（可行解）是A的一个子集满足一定的条件约束条件Bk(1)Bk(2)…Bk(m)…目标函数取极值最优解
4、算法设计与分析>贪心算法4.2.活动安排问题算法设计与分析>贪心算法活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。[问题陈述]设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si5、区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。1234567891011[例]1305356882124567891011121314is[i]f[i]设待安排的11个活动起止时间按结束时间的非减序排列最大相容活动子集(1,4,8,11),也可表示为等长n元数组:(1,0,0,1,0,0,0,1,0,0,1)[算法思路]将n个活动按结束时间非减序排列,依次考虑活动i,若i与已选择的活动相容,则添加此活动到相容活动子集.活动
6、安排问题贪心算法templatevoidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;//从第二个活动开始检查是否与前一个相容for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}算法设计与分析>贪心算法各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列算法greedySelector的计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长
7、条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列
8、，可以用O(nlogn)的时间重排。T(n)=O(nlogn)(未排序时)[算法分析]T(n)=O(n)(排序时)[算法证明]算法达到最优解.[问题描述]输入:(x1,x2,...xn),xi
