第4章贪心算法-1

第四章贪心算法

Greedymethod贪婪，我找不到一个更好的词来描述它，它就是好！它就是对！它就是有效！——影片《华尔街》中的台词主要内容贪心算法的基本概念与要素几个实例：活动安排、最优装载、Huffman编码、单源最短路径、最小生成树、多机调度问题、带有完成期限的作业调度重点与难点：算法本身较简单，很少用递归；关键是如何选择贪心策略；如何证明你选择的贪心策略能获得最优解。例贪心算法概述贪心算法也称为优先策略顾名思义是“择优录取”，在某些方面的应用是非常成功的，也是我们设计算法时经常使用的一种策略。国外叫做Greedymethod，意即见到好的就抓住不放。它并不一定对所有问题都成功，但是对某些问题特别简单、有效。在贪婪算法中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则(criterion)。贪心算法常常用于求解某些问题的最优解。这类问题一般有n个输入，而其解由这n个输入的某个子集组成，要求该子集满足预先给定的约束条件。这一子集称为该问题的一个可行解。其中使目标函数取得极值的可行解称为最优解。N个输入约束条件可行解准则最优解贪心法的关键是找到一个衡量优劣的标准，然后把n个输入按这种标准排序并尝试局部解。如果这个输入和当前的部分解加起来不能产生一个可行解，则不把此输入加入到部分解当中。一般地，选取最优度量标准并非易事，因此贪心法得到的解往往不是最优解，而是次优解。而一旦找到最优度量标准，则贪心法特别有效。贪心法逐步给出解的各部分，在每一步“贪婪地”选择最好的部分解，而不顾及这样选择对整体的影响，因此未必得到最优解。贪心法应用的成功示例有：单源最短路径问题、最小生成树问题以及作业调度等。即使得不到最优解，往往能得到较好的近似解。例1[找零钱]：一个小孩买了价值少于1美元的糖，并将1美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供了数目不限的面值为25、10、5、1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪心准则如下：每一次选择应使零钱数尽量增大。为保证解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。假设需要找给小孩67美分，首先入选的是两枚25美分的硬币，第三枚入选的不能是25美分的硬币，否则硬币的选择将不可行（零钱总数超过67美分），第三枚应选择10美分的硬币，然后是5美分的，最后加入两个1美分的硬币。贪婪算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）。可以证明采用上述贪婪算法找零钱时所用的硬币数目的确最少。例2：找零钱问题与硬币面值的设定有关。比如：要找给顾客3角7分钱，如果硬币面值为1角、5分、2分、1分，那么按照贪心算法：

1角：3枚；5分：1枚；2分：1枚合计：5枚能得到最优解。如果硬币面值为11分、7分、5分、1分，那么按照贪心算法：

11分：3枚；1分：4枚合计：7枚但最优解应该是5枚，贪心法不成功。背包问题假设：n=3,c=20,(w1,w2,w3)=(18,15,10)(v1,v2,v3)=(25,24,15)四个可行解：可行解重量价值（1/2，1/3，1/4）16.524.25

（1，2/15，0）2028.2

（0，2/3，1）2031

（0，1，1/2）2031.5选取度量标准是用贪心法求解问题的关键。任意选取策略价值优先策略重量最小优先策略单价高优先策略用贪心算法求解背包问题的步骤：1）计算每种物品的单价vi/wi2）按物品的单价，从大到小排序3）单价高的物品优先装包，直至装满。（最后一种物品可能装入一部分）时间复杂性排序：O(nlogn)其它：O(n)为什么采用贪心策略能得到最优解？0/1背包问题的几种贪婪策略：1）从剩余的物品中，选出可以装入背包的价值最大的物品2）从剩下的物品中选择可装入背包的重量最小的物品3）从剩余物品中选择可装入包的pi/wi值最大的物品这三种策略都不能保证得到最优解。我们不必因所考察的几个贪婪算法都不能保证得到最优解而沮丧，0/1背包问题是一个NP复杂问题。对于这类问题，也许根本就不可能找到具有多项式时间的算法。虽然按pi/wi非递增的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。我们希望它是一个好的启发式算法，且大多数时候能很好地接近最后算法。据统计，在600个随机产生的背包问题中，用这种启发式贪婪算法来解有239题为最优解。有583个例子与最优解相差10%，所有600个答案与最优解之差全在25%以内。该算法能在O(n

log

n)时间内获得如此好的性能。我们也许会问，是否存在一个x(x<100)，使得贪婪启发法的结果与最优值相差在x%以内。答案是否定的。为什么贪心策略不适用于0/1背包问题？例：c=50,w=(10,20,30),V=(60,100,120)单价v/w=(6,5,4)

按贪心策略，应装入前两个物品，价值160；而最优解应为装入后两种物品，价值220。原因：贪心法不能保证0/1背包装满，闲置部分使背包价值降低。考虑0/1背包问题，应比较选择wi与不选择wi所导致的结果，然后作出选择，由此导致相互重叠的子问题。所以可用动态规划法。voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//按单位价值排序/inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;//c为背包剩余空间/for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]