计算机算法设计与分析 第4章

《计算机算法设计与分析 第4章》由会员分享，可在线阅读，更多相关《计算机算法设计与分析 第4章（59页珍藏版）》请在金锄头文库上搜索。

1、第4章 贪心算法1学习要点理解贪心算法的概念。掌握贪心算法的基本要素 （1）最优子结构性质（2）贪心选择性质理解贪心算法与动态规划算法的差异理解贪心算法的一般理论通过应用范例学习贪心设计策略。（1）活动安排问题；（2）最优装载问题；（3）哈夫曼编码；（4）单源最短路径；（5）最小生成树；（6）多机调度问题。2顾名思义，贪心算法总是作出在当前看来最好的选择 。也就是说贪心算法并不从整体最优考虑，它所作出的选 择只是在某种意义上的局部最优选择。当然，希望贪心算 法得到的最终结果也是整体最优的。虽然贪心算法不能对 所有问题都得到整体最优解，但对许多问题它能产生整体 最优解。如单源最短路经问题，最小生

2、成树问题等。在一 些情况下，即使贪心算法不能得到整体最优解，其最终结 果却是最优解的很好近似。34.1 活动安排问题活动安排问题就是要在所给的活动集合中选出最大的 相容活动子集合，是可以用贪心算法有效求解的很好例子。 该问题要求高效地安排一系列争用某一公共资源的活动。贪 心算法提供了一个简单、漂亮的方法使得尽可能多的活动能 兼容地使用公共资源。44.1 活动安排问题设有n个活动的集合E=1,2,n，其中每个活动都 要求使用同一资源，如演讲会场等，而在同一时间内只有 一个活动能使用这一资源。每个活动i都有一个要求使用 该资源的起始时间si和一个结束时间fi,且si vvoid GreedySel

3、ector(int n, Type s, Type f, bool A)vv A1=true;v int j=1;v for (int i=2;i=fj) Ai=true; j=i; v else Ai=false;v v下面给出解活动安排问题的贪心算法GreedySelector :各活动的起始时间和结 束时间存储于数组s和f 中且按结束时间的非减 序排列 64.1 活动安排问题由于输入的活动以其完成时间的非减序排列，所以 算法greedySelector每次总是选择具有最早完成时间的 相容活动加入集合A中。直观上，按这种方法选择相容 活动为未安排活动留下尽可能多的时间。也就是说，该 算法的

4、贪心选择的意义是使剩余的可安排时间段极大化 ，以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已 按结束时间的非减序排列，算法只需O(n)的时间安排n 个活动，使最多的活动能相容地使用公共资源。如果所 给出的活动未按非减序排列，可以用O(nlogn)的时间重 排。 74.1 活动安排问题例：设待安排的11个活动的开始时间和结束时间按结 束时间的非减序排列如下：i1234567891011Si 130535688212fi456789101112131484.1 活动安排问题算法greedySelector 的 计算过程如左图所示。图 中每行相应于算法的一次

5、迭代。阴影长条表示的活 动是已选入集合A的活动 ，而空白长条表示的活动 是当前正在检查相容性的 活动。94.1 活动安排问题若被检查的活动i的开始时间Si小于最近选择的活动j的 结束时间fi，则不选择活动i，否则选择活动i加入集合A中 。 贪心算法并不总能求得问题的整体最优解。但对于活动 安排问题，贪心算法greedySelector却总能求得的整体最优 解，即它最终所确定的相容活动集合A的规模最大。这个结 论可以用数学归纳法证明。104.2 贪心算法的基本要素本节着重讨论可以用贪心算法求解的问题的一般特征。 对于一个具体的问题，怎么知道是否可用贪心算法解此 问题，以及能否得到问题的最优解呢?

6、这个问题很难给予肯 定的回答。但是，从许多可以用贪心算法求解的问题中看到这类问 题一般具有2个重要的性质：贪心选择性质和最优子结构性 质。 114.2 贪心算法的基本要素 1、贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以 通过一系列局部最优的选择，即贪心选择来达到。这是 贪心算法可行的第一个基本要素，也是贪心算法与动态 规划算法的主要区别。动态规划算法通常以自底向上的方式解各子问题， 而贪心算法则通常以自顶向下的方式进行，以迭代的方 式作出相继的贪心选择，每作一次贪心选择就将所求问 题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性 质，必须证明每一步所作的贪

7、心选择最终导致问题的整 体最优解。124.2 贪心算法的基本要素当一个问题的最优解包含其子问题的最优解时， 称此问题具有最优子结构性质。问题的最优子结构性 质是该问题可用动态规划算法或贪心算法求解的关键 特征。 2、最优子结构性质134.2 贪心算法的基本要素贪心算法和动态规划算法都要求问题具有最优子 结构性质，这是2类算法的一个共同点。但是，对于具 有最优子结构的问题应该选用贪心算法还是动态规划 算法求解?是否能用动态规划算法求解的问题也能用贪 心算法求解?下面研究2个经典的组合优化问题，并以 此说明贪心算法与动态规划算法的主要差别。3、贪心算法与动态规划算法的差异144.2 贪心算法的基本

8、要素v0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值 为Vi，背包的容量为C。应如何选择装入背包的物品，使得 装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即 装入背包或不装入背包。不能将物品i装入背包多次，也不能只 装入部分的物品i。154.2 贪心算法的基本要素v背包问题： 与0-1背包问题类似，所不同的是在选择物品i装入背包 时，可以选择物品i的一部分，而不一定要全部装入背包， 1in。这2类问题都具有最优子结构性质，极为相似，但 背包问题可以用贪心算法求解，而0-1背包问题却不能 用贪心算法求解。 164.2 贪心算法的基本要素首先

9、计算每种物品单位重量的价值Vi/Wi，然后，依贪心 选择策略，将尽可能多的单位重量价值最高的物品装入背包 。若将这种物品全部装入背包后，背包内的物品总重量未超 过C，则选择单位重量价值次高的物品并尽可能多地装入背 包。依此策略一直地进行下去，直到背包装满为止。具体算法可描述如下页： 用贪心算法解背包问题的基本步骤：174.2 贪心算法的基本要素vvoid Knapsack(int n,float M,float v,float w,float x)vv Sort(n,v,w);v int i;v for (i=1;ic) break;v xi=1;v c-=wi;v v if (ivvoid

10、Loading(int x, Type w, Type c, int n)vv int *t = new int n+1;v Sort(w, t, n);v for (int i = 1; i 0，则称拟阵M为带权拟阵。依此权函数，S的任一子集A的权定义为 。2、关于带权拟阵的贪心算法 许多可以用贪心算法求解的问题可以表示为求带权拟阵的最大权独 立子集问题。 474.8 贪心算法的理论基础给定带权拟阵M=(S,I)，确定S的独立子集AI使得W(A) 达到最大。这种使W(A)最大的独立子集A称为拟阵M的最优子 集。由于S中任一元素x的权W(x)是正的，因此，最优子集也 一定是极大独立子集。 例如

11、，在最小生成树问题可以表示为确定带权拟阵 的最优子集问题。求带权拟阵的最优子集A的算法可用于解 最小生成树问题。 下面给出求带权拟阵最优子集的贪心算法。该算法以具 有正权函数W的带权拟阵M=(S,I)作为输入，经计算后输出M 的最优子集A。484.8 贪心算法的理论基础vSet greedy (M,W)vA=;v 将S中元素依权值W（大者优先）组成优先队列；v while (S!=) v S.removeMax(x);v if (AxI) A=Ax;v v return Av494.8 贪心算法的理论基础算法greedy的计算时间复杂性为 。 引理4.2(拟阵的贪心选择性质) 设M=(S,I)

12、是具有权函数W的带权拟阵，且S中元素依权 值从大到小排列。又设x S是S中第一个使得x是独立子集 的元素，则存在S的最优子集A使得x A。算法greedy在以贪心选择构造最优子集A时，首次选入 集合A中的元素x是单元素独立集中具有最大权的元素。此时 可能已经舍弃了S中部分元素。可以证明这些被舍弃的元素 不可能用于构造最优子集。504.8 贪心算法的理论基础引理4.3：设M=(S,I)是拟阵。若S中元素x不是空集的可扩 展元素，则x也不可能是S中任一独立子集A的可扩展元素。 引理4.4(拟阵的最优子结构性质) 设x是求带权拟阵M(S，I)的最优子集的贪心算法 greedy所选择的S中的第一个元素

13、。那么，原问题可简化为 求带权拟阵M=(S,I)的最优子集问题，其中： S=y|y S且x,y I I=B|B S-x且Bx I M的权函数是M的权函数在S上的限制(称M为M关于 元素x的收缩)。514.8 贪心算法的理论基础定理4.5(带权拟阵贪心算法的正确性) 设M(S,I)是具有权函数W的带权拟阵，算法greedy 返回M的最优子集。3、任务时间表问题给定一个单位时间任务的有限集S。关于S的一个时 间表用于描述S中单位时间任务的执行次序。时间表中第 1个任务从时间0开始执行直至时间1结束，第2个任务从 时间1开始执行至时间2结束，第n个任务从时间n-1 开始执行直至时间n结束。524.8

14、 贪心算法的理论基础具有截止时间和误时惩罚的单位时间任务时间表问题可 描述如下。 (1) n个单位时间任务的集合S=1,2,n； (2) 任务i的截止时间 ,1in,1 n，即要求任 务i在时间 之前结束； (3) 任务i的误时惩罚 ,1in,即任务i未在时间 之前结束将招致的 惩罚；若按时完成则无惩罚。 任务时间表问题要求确定S的一个时间表（最优时间表 ）使得总误时惩罚达到最小。534.8 贪心算法的理论基础这个问题看上去很复杂，然而借助于拟阵，可以用带权 拟阵的贪心算法有效求解。 对于一个给定的S的时间表，在截止时间之前完成的任 务称为及时任务，在截止时间之后完成的任务称为误时任务 。 S

15、的任一时间表可以调整成及时优先形式，即其中所有 及时任务先于误时任务，而不影响原时间表中各任务的及时 或误时性质。 类似地，还可将S的任一时间表调整成为规范形式，其 中及时任务先于误时任务，且及时任务依其截止时间的非减 序排列。544.8 贪心算法的理论基础首先可将时间表调整为及时优先形式，然后再进一步调 整及时任务的次序。 任务时间表问题等价于确定最优时间表中及时任务子集 A的问题。一旦确定了及时任务子集A，将A中各任务依其截 止时间的非减序列出，然后再以任意次序列出误时任务，即 S-A中各任务，由此产生S的一个规范的最优时间表。 对时间t=1,2,n，设 (A)是任务子集A中所有截止时 间是t或更早的任务数。考察任务子集A的独立性。554.8 贪心算法的理论基础引理4.6：对于S的任一任务子集A，下面的各命题是等价的 。 (1) 任务子集A是独立子集。 (2) 对于t=1,2,n， (A)t。 (3) 若A中任务依其截止时间非减序排列，则A中所有任务都 是及时的。 任务时间表问题要求使总误时惩罚达到最小，这等价于 使任务时间表中的及时任务的惩罚值之和达到最大。下面的 定理表明可用带权拟阵的贪心算法解