算法设计与分析_第4章_贪心算法

详细介绍贪心算法

算法设计与分析第4章贪心算法

详细介绍贪心算法

学习要点理解贪心算法的概念掌握贪心算法的基本要素 (1)最优子结构性质 (2)贪心选择性质理解贪心算法与动态规划算法的差异理解贪心算法的一般理论

详细介绍贪心算法

学习要点通过应用范例学习贪心设计策略 (1)活动安排问题； (2)最优装载问题； (3)哈夫曼编码； (4)单源最短路径； (5)最小生成树；

详细介绍贪心算法

背景Similar to dynamic programming. Used for optimization problems. Optimization problems typically go through a sequence of steps, with a set of choices at each step. For many optimization problems, using dynamic programming to determine the best choices is overkill (过度的杀伤威力).贪心算法: Simpler, more efficient

4

详细介绍贪心算法

背景应用找钱排队时出现拥挤情况，如何做才能节省时间？

详细介绍贪心算法

背景研究程卫芳,廖湘科,沈昌祥.有向传感器网络最大覆盖调度算法.软件学报,2009,20(4):975-984崔鹏,刘红静.测试集问题的集合覆盖贪心算法的深入近似.软件学报,2006,17(7):1494-1500刘勇,高宏,李建中.基于联合意义度量的Top-K图模式挖掘 .计算机学报,2010,2期:215-230张海英,温玄,张田文.低信噪比多目标检测的贪心算法 .计算机学报,2008,1期:142-150

详细介绍贪心算法

贪心算法的基本要素贪心(Greedy)算法总是作出在当前看来最好的选择。贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但其最终结果却是最优解的很好近似。

详细介绍贪心算法

贪心算法的基本要素贪心算法求解的问题一般具有2个重要的性质(1)最优子结构性质 (2)贪心选择性质

没有一般化的规则来说明贪心算法是否最优，但有两个基本要点

详细介绍贪心算法

贪心算法的基本要素最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。

贪心选择性质(1)贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 (2)贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。动态规划算法通常以自底向上的方式解各子问题。

详细介绍贪心算法

贪心算法的基本要素0-1背包问题n个物品,物品i价值vi,重wi背包的最大负载量为W,如何选取物品，使得背包装的物品价值最大每个物品是一个整体，不能分割，因此，要么选取

该物品，要么不选取

(分数)背包问题Like the 0-1 knapsack problem,但是可以取走物品的一部分.10

详细介绍贪心算法

贪心算法的基本要素实例50 30 20 10 0/1背包问题￥60￥100￥120背包问题背包

30 30 20 20 10￥220￥160 10￥180

20/ 30 20

10￥24011

详细介绍贪心算法

贪心算法的基本要素0-1背包问题没有贪心选择性质

贪心策略:take items 1 and 2 value= 160, weight= 30 20 pounds剩余空间.

最优策略:Take items 2 and 3 value=220, weight=50没有剩余空间20 20 1012

30

￥160

￥220

详细介绍贪心算法

贪心算法的基本要素要解决分数背包问题，按照单位重量价值(vi/wi)将物品降序排列 Let vi/wi≥ vi+1/wi+1 for all i20/ 30 20 FRACTIONAL-KNAPSACK(v,w,W) 1 load← 0 2 i←1 3 while load< W and i≤ n{ 4 do if wi≤ W - load 5 then take all of item i 6 else take W-load of wi from item i 7 add what was taken to load 8 i←i+ 1}13

10￥24013

详细介绍贪心算法

贪心算法的基本要素都有最优子结构性质0-1: choose the most valuable load j that weighs wj≤ W, remove j, choose the most valuable load i that weighs wi≤ W-wj fractional:若先选 item j的一部分，其重 w,则接下来的最优挑选方案为从余下的 n-1个物品〔除 j外〕和 j的另外重 wj-w的部分中挑选，其重量不超过 W-w

但是分数背包问题具有贪心选择性质，而0-1背包问题没有这个性质

14

详细介绍贪心算法

贪心算法的基本要素通过局部最优解可导出全局最优解

Si,r-1kr

ki

..

kr kr

..

kj

动态规划

Si,ji

..r-1 r+1

.. kj

Sr-1,j k k k Make a choice at each step. Choice depends on knowing optimal solutions to subproblems. Solve subproblems first. (依赖于已知子问题的最优解再作出选择) Solve bottom-up. 11 10 S0,n+1 am19

贪心算法子问题)

Sm1,n+15 4 3

8 7 6

2 Make a choice at each step. 1 Make the choice before solving the subproblems. (先作选择，再解

Solve top-down.15

详细介绍贪心算法

贪心算法的基本要素可用贪心方法时，动态规划方法可能不适用 (背包问题)

可用动态规划方法时，贪心方法可能不适用。 (0/1背包问题)贪心算法需要正确性证明①证明算法所求解的问题具有最优子结构；②证明算法所求解的问题具有贪心选择性；③算法按照②中的贪心选择性进行局部优化选 16择。