常用算法设计与分析_第04章_贪婪法_陈友文ppt课件.pptx

《常用算法设计与分析_第04章_贪婪法_陈友文ppt课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第04章贪婪法湖南涉外经济学院计算机科学与技术学部邹竞导入新课当一个问题具有最优子结构性质时，可以用动态规划法求解，但有时会有更简单有效的算法。来看一个找硬币的例子。假设有4种硬币，它们的面值分别为二角五分、一角、五分和一分。现在要找给某顾客六角三分钱。这时，我们会不假思索地拿出2个二角五分的硬币，1个一角的硬币和3个一分的硬币交给顾客。这种找硬币方法与其他的找法相比，所拿出的硬币个数是最少的。这里，我们下意识地使用了这样的找硬币算法：首先选出一个面值不超过六角三分的最大硬币，即二角五分；然后从六角三分中减去二角五分，剩下三角八分；再选出一个面值不超过三角八分的最大硬币，即又

2、一个二角五分，如此一直做下去。这个找硬币的方法实际上就是贪心算法。贪心算法总是作出在当前看来最好的选择。贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。如果硬币的面值改为一分、五分和一角一分3种，而要找给顾客的是一角五分钱。还用贪心算法，我们将找给顾客1个一角一分的硬币和4个一分的硬币。然而3个五分的硬币显然是最好

3、的找法。4.1活动安排问题设有n个活动的集合e={0,1,2,…,n-1}，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si

4、数组s[]和f[]中且按结束时间的非减序：f0≤f1≤…≤fn-1排列。如果所给出的活动未按此序排列，我们可以用O(nlog2n)的时间将它重排。templatestructAct{intid;//活动编号Typef;//结束时间Types;//开始时间booloperator<(constAct&rhs)const{returnfclassActArrange{protected:Act*actions;//活动数组intn;//活动个数bool*A;//A[i]表示活动

5、i是否被选中public:voidGreedySelector();ActArrange(intActCount);~ActArrange();};templatevoidActArrange::GreedySelector(){inti,j;sort(actions,actions+n);//按结束时间的升序排列A[actions[0].id]=true;j=0;for(i=1;i=actions[j].f){A[actions[i].id]=true;j=i;//j用以记录最近一次加入

6、到A中的活动}elseA[actions[i].id]=false;}}算法GreedySelector中用集合A来存储所选择的活动。活动i在集合A中，当且仅当A[i]的值为true。变量j用以记录最近一次加入到A中的活动。由于输入的活动是按其结束时间的非减序排列的，fj总是当前集合A中所有活动的最大结束时间，即：。算法GreedySelector一开始选择活动0，并将j初始化为0。然后依次检查活动i是否与当前已选择的所有活动相容。若相容，则将活动i加入到已选择活动的集合A中，否则，不选择活动i，而继续检查下一活动与集合A中活动的相容性。由于fj总是当前集合A中所有活动的最大

7、结束时间，故活动i与当前集合A中所有活动相容的充分且必要的条件是其开始时间s不早于最近加入集合a中的活动j的结束时间fj，si≥fj。若活动i与之相容，则i成为最近加入集合A中的活动，因而取代活动j的位置。由于输入的活动是以其完成时间的非减序排列的，所以算法GreedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上按这种方法选择相容活动就为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法GreedyS