《计算机算法设计与分析》PPT第四章 贪心算法

第4章

贪心算法

学习要点

理解贪心算法的概念 掌握贪心算法的基本要素 (1)最优子结构性质 (2)贪心选择性质 理解贪心算法与动态规划算法的差异 通过应用范例学习贪心设计策略 (1)活动安排问题 (2)最优装载问题 (3)找钱问题 (4)哈夫曼编码 (5)单源最短路径 (6)最小生成树2

当一个问题具有最优子结构性质时，可用动态规划法求解， 但有时用贪心算法求解会更加的简单有效。 顾名思义，贪心算法总是作出在当前看来最好的选择。贪 心算法并不从整体最优考虑，它所作出的选择只是在某种 意义上的局部最优选择。当然，希望贪心算法得到的最终 结果也是整体最优的。虽然贪心算法不能对所有问题都得 到整体最优解，但对许多问题它能产生整体最优解，如单 源最短路径问题，最小生成树问题等。在一些情况下，即 使贪心算法不能得到整体最优解，其最终结果却是最优解 的很好近似。

例：用贪心法求解找零钱问题。 假设有面值为5元、2元、1元、5角、2角、1 角的货币，需要找给顾客4元6角现金，为使付 出的货币的数量最少。 首先选出1张面值不超过4元6角的最大面值的 货币，即2元，再选出1张面值不超过2元6角 的最大面值的货币，即2元，再选出1张面值不 超过6角的最大面值的货币，即5角，再选出1 张面值不超过1角的最大面值的货币，即1角， 总共付出4张货币。4

在找零钱问题每一步的贪心选择中，在不超过应 找零钱金额的条件下，只选择面值最大的货币， 而不去考虑在后面看来这种选择是否合理，而且 它还不会改变决定：一旦选出了一张货币，就永 远选定。 找零钱问题的贪心选择策略是尽可能使付出的货 币最快地满足支付要求，其目的是使付出的货币 张数最慢地增加，这正体现了贪心法的设计思想。

贪心法的求解过程用贪心法求解问题应该考虑如下几个方面： (1)候选集合C:为了构造问题的解决方案，有一 个候选集合C作为问题的可能解，即问题的最终 解均取自于候选集合C。例如在找零钱问题中， 各种面值的货币构成候选集合。

(2)解集合S:随着贪心选择的进行，解集合S不 断扩展，直到构成一个满足问题的完整解。例如 在找零钱问题中，已付出的货币构成解集合。

(3)可行解函数solution:检查解集合S是否构成 问题的一个可行解。例如，在找零钱问题中，可 行解函数是已付出的货币金额恰好等于应找零钱。 (4)选择函数select:即贪心策略，这是贪心法 的关键，它指出哪个候选对象最有希望构成问题 的解，选择函数通常和目标函数有关

。例如，在 找零钱问题中，贪心策略就是在候选集合中选择 面值最大的货币。 (5)约束函数constraint:检查解集合中加入一 个候选对象是否满足约束条件。例如，在找零钱 问题中，约束函数是每一步选择的货币和已付出 的货币相加不超过应找零钱。7

贪心算法的一般框架 Greedy(C) //C是问题的输入集合即候选集合 { S={ }; //初始解集合为空集 while (not solution(S)) //集合S没有构成问题的一个可行解 { x=select(C); //在候选集合C中做贪心选择 if constraint(S, x) //判断集合S中加入x后是否满足约束条件 S=S+{x}; C=C-{x}; } return S; } 8

4.1

活动安排问题

该问题是可以用贪心算法有效求解的很好例子。 该问题要求高效地安排一系列争用某一公共资源 的活动。 贪心算法提供了一个简单、漂亮的方法，使得尽 可能多的活动能兼容地使用公共资源。

设有n个活动的集合E={1,2,…,n},其中每个活 动都要求使用同一资源，如演讲会场等，而在同 一时间内只有一个活动能使用这一资源。每个活 动i都有一个要求使用该资源的起始时间si和一个 结束时间fi,且si<fi。如果选择了活动i,则它在 半开时间区间[si,fi)内占用资源。若区间[si,fi) 与区间[sj,fj)不相交，则称活动i与活动j是相容 的。即当si≥fj或sj≥fi时，活动i与活动j相容。 活动安排问题：要在所给的活动集合中选出最大 的相容活动子集合。10

用动态规划方法求解

步骤1:分析最优解的结构特征 构造子问题空间 Sij={ ak∈S: fi≤sk<fk≤sj} Sij是S中活动的子集，其中每个活动都在活动ai 结束之后开始，且在活动aj开始之前结束。 Sij包含了所有与ai和aj相容的活动，并且与不迟 于ai结束和不早于aj开始的活动相容。此外， 虚构活动a0和an+1,其中f0=0, Sn+1=∞。原 问题即为寻找S0,n+1中最大相容活动子集。11

假设活动已按结束时间的单调非递减顺序排序 f0≤f1≤f2≤… ≤fn<fn+1 则，当i≥j时， Sij=φ。

假设存在一活动ak∈Sij,其中i≥j,则在已排的序列中 ai在aj后面。 因fi≤sk<fk≤sj<fj ,与在已排的序列中ai在aj后面的 假设相矛盾。 所以，设活动按结束时间的单调非递减顺序排序，子 问题空间被用来从sij中选择最大相容活动子集，其中 0≤i<j≤n+1,而且所有其它的sij是空的。12

活动选择问题的子结构 考虑某非空子问题Sij,并假设Sij的解包含某活动 ak,其中fi≤sk<fk≤sj。 用活动 ak生成两个子问题： Sik(在ai结束后开始 且在ak开始前结束的活动),以及Skj(在ak结束后 开始且在aj开始前结束的活动),它们都是Sij的子 集。 Sij的解是连同活动ak在内的Sik和Skj解的并集。 Sij解中 …… 此处隐藏：906字，全部文档内容请下载后查看。喜欢就下载吧 ……