常用算法设计与分析_第04章_贪婪法_陈友文

第04章贪婪法湖南涉外经济学院计算机科学与技术学部邹竞导入新课当一个问题具有最优子结构性质时，可以用动态规划法求解，但有时会有更简单有效的算法。来看一个找硬币的例子。假设有4种硬币，它们的面值分别为二角五分、一角、五分和一分。现在要找给某顾客六角三分钱。这时，我们会不假思索地拿出2个二角五分的硬币，1个一角的硬币和3个一分的硬币交给顾客。这种找硬币方法与其他的找法相比，所拿出的硬币个数是最少的。这里，我们下意识地使用了这样的找硬币算法：首先选出一个面值不超过六角三分的最大硬币，即二角五分；然后从六角三分中减去二角五分，剩下三角八分；再选出一个面值不超过三角八分的最大硬币，即又一个二角五分，如此一直做下去。这个找硬币的方法实际上就是贪心算法。贪心算法总是作出在当前看来最好的选择。贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。如果硬币的面值改为一分、五分和一角一分3种，而要找给顾客的是一角五分钱。还用贪心算法，我们将找给顾客1个一角一分的硬币和4个一分的硬币。然而3个五分的硬币显然是最好的找法。4.1活动安排问题设有n个活动的集合e={0,1,2,…,n-1}，其中每个活动都要求使用同一资源，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且sifi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。在下面的活动安排问题的贪心算法GreedySelector中，各活动的起始时间和结束时间存储于数组s[]和f[]中且按结束时间的非减序：f0≤f1≤…≤fn-1排列。如果所给出的活动未按此序排列，我们可以用O(nlog2n)的时间将它重排。templatetypenameTypestructAct{intid;//活动编号Typef;//结束时间Types;//开始时间booloperator(constAct&rhs)const{returnfrhs.f;}};templatetypenameTypeclassActArrange{protected:ActType*actions;//活动数组intn;//活动个数bool*A;//A[i]表示活动i是否被选中public:voidGreedySelector();ActArrange(intActCount);~ActArrange();};templatetypenameTypevoidActArrangeType::GreedySelector(){inti,j;sort(actions,actions+n);//按结束时间的升序排列A[actions[0].id]=true;j=0;for(i=1;in;i++){if(actions[i].s=actions[j].f){A[actions[i].id]=true;j=i;//j用以记录最近一次加入到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中活动的相容性。}{maxkAkjff由于fj总是当前集合A中所有活动的最大结束时间，故活动i与当前集合A中所有活动相容的充分且必要的条件是其开始时间s不早于最近加入集合a中的活动j的结束时间fj，si≥fj。若活动i与之相容，则i成为最近加入集合A中的活动，因而取代活动j的位置。由于输入的活动是以其完成时间的非减序排列的，所以算法GreedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上按这种方法选择相容活动就为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法GreedySelector的效率极高。贪心算法并不总能求得问题的整体最优解。但对于活动安排问题，算法GreedySelector却总能求得的整体最优解，可以用数学归纳法来证明这个结论。证明：设E={0,1,2,…,n-1}为所给的活动集合。由于E中活动按结束时间的非减序排列，故活动0具有最早的完成时间。首先要证明活动安排问题有一个最优解以贪心选择开始，即该最优解中包含活动0。设A∈E是所给的活动安排问题的一个最优解，且A中活动也按结束时间非减序排列，A中的第一个活动是活动k。若k=0，则A就是一个以贪心选择开始的最优解。若k0，则我们设B=A-{k}∪{0}。由于f0≤fk，且A中活动是互为相容的，故B中的活动也是互为相容的。又由于B中活动个数与A中活动个数相同，且A是最优的，故B也是最优的。也就是说B是一个以贪心选择活动0开始的最优活动安排。因此，总存在一个以贪心选择开始的最优活动安排方案。在作了贪心选择，即选择了活动0后，原问题就简化为对E中所有与活动0相容的活动进行活动安排的子问题。即若A是原问题的一个最优解，则A’=A-{0}是活动安排问题E’={i∈E:si≥f0}的一个最优解。事实上，如果我们能找到E’的一个解B’，它包含比A’更多的活动，则将活动0加入到B’中将产生E的一个解B，它包含比A更多的活动。这与A的最优性矛盾。因此，每一步所作的贪心选择都将问题简化为一个更小的与原问题具有相同形式的子问题。对贪心选择次数用数学归纳法即知，贪心算法GreedySelector最终产生原问题的一个最优解。4.2贪心算法的基本要素贪心算法通过一系列的选择来得到一个问题的解。它所作的每一个选择都是当前状态下某种意义的最好选择，即贪心选择。希望通过每次所作的贪心选择导致最终结果是问题的一个最优解。这种启发式的策略并不总能奏效，然而在许多情况下确能达到预期的目的。解活动安排问题的贪心算法就是一个例子。下面我们着重讨论可以用贪心算法求解的问题的一般特征。从许多可以用贪心算法求解的问题中我们看到它们一般具有两个重要的性质：贪心选择性质和最优子结构性质。1．贪心选择性质贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。在动态规划算法中，每步所作的选择往往依赖于相关子问题的解。因而只有在解出相关子问题后，才能作出选择。而在贪心算法中，仅在当前状态下作出最好选择，即局部最优选择。然后再去解作出这个选择后产生的相应的子问题。贪心算法所作的贪心选择可以依赖于以往所作过的选择，但决不依赖于将来所作的选择，也不依赖于子问题的解。贪心算法中，作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一步之前的最优解则不作保留。可以知道贪心法正确的条件是：每一步的最优解一定包含上一步的最优解。而动态规划法中，全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解；动态规划的关键是状态转移方程，即如何由以求出的局部最优解来推导全局最优解；动态规划法有边界条件：即最简单的，可以直接得出的局部最优解。正是由于这种差别，动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。首先考察问题的一个整体最优解，并证明可修改这个最优解，使其以贪心选择开始。而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。2．最优子结构性质当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质。问题所具有的这个性质是该问题可用动态规划算法或贪心算法求解的一个关键特征。在活动安排问题中，其最优子结构性质表现为：若A是对于E的活动安排问题包含活动0的一个最优解，则相容活动集合A’=a-{0}是对于E’={i∈E:si≥f0}的活动安排问题的一个最优解。3．贪心算法与动态规划算法的差异贪心算法和动态规划算法都要求问题具有最优子结构性质，这是两类算法的一个共同点。但是，对于一个具有最优子结构的问题应该选用贪心算法还是动态规划算法来求解？下面研究两个经典的组合优化问题，并以此来说明贪心算法与动态规划算法的主要差别。0-1背包问题：给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的所能够容纳的重量为c。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入物品i的一部分。即，给定c0，wi0，vi0，0≤i≤n-1，要求找出一个n元的0-1向量(x0,x1,…,xn-1)，xi∈{0,1}，使得，并且最大。背包问题：与0-1背包问题类似，不同的是选择物品i装入背包时，可选择物品i的一部分，不一定要全部装入背包。即，给定c0，wi0，vi0，0≤i≤n-1，要求找出一个n元的向量(x0,x1,…,xn-1)，0≤xi≤1，使得，且最大。cxwniii1010niiixvcxwniii1010niiixv这两类问题都具有最优子结构性质：对于0-1背包问题，设A是能够装入容量为c的背包的具有最大价值的物品集合，则Aj=A-{j}是n-1个物品0,1,2,…,j-1,j+1,…,n-1可装入容量为c-wj的背包的具有最大价值的物品集合；对于背包问题，类似地，若它的一个最优解包含物品j，则从该最优解中拿出所含的物品j的那部分重量w，剩余的将是n-1个原重物品0,1,2,…,j-1,j+1,…,n-1以及重为wj-w的物品j中可装入容量为c-w的背包且具有最大价值的物品。虽然这两个问题极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。用贪心算法解背包问题的基本步骤是，首先计算每种物品单位重量的价值vi/wi然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直进行下去直到背包装满为止。具体算法可描述如下structObject{intid;//物品排序前的编号doublev;doublew;booloperator(constObject&rhs)const{returnv/wrhs.v/rhs.w;}};classKnapsack{protected:Object*objects;//物品数组