计算机算法设计与分析第2版4贪心算法

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

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

2、 （6 6）多机调度问题。）多机调度问题。2 2 顾名思义，贪心算法总是作出在当前看来最好的选择。顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的只是在某种意义上的局部最优局部最优局部最优局部最优选择。当然，希望贪心算法选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问

3、题等。在一些优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。却是最优解的很好近似。3 34.1 活动安排问题 活动安排问题就是要在所给的活动集合中选出最大活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多动。贪心算法提供了一个简单、

4、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。的活动能兼容地使用公共资源。4 44.1 活动安排问题 设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi 。如果选择了活动i，则它在半开时间区间si, fi)内占用资源。若区间si, fi)与区间sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。5 54.1 活动安排问题templatetemplatevoid void GreedySele

5、ctorGreedySelector(int(int n, Type s, Type f, n, Type s, Type f, boolbool A) A) A1=true; A1=true; intint j=1; j=1; for ( for (intint i=2;i= i=2;i=fjfj) ) AiAi=true; j=i; =true; j=i; else else AiAi=false;=false; 下面给出解活动安排问题的贪心算法GreedySelectorGreedySelector :各活动的起始时间和结各活动的起始时间和结束时间存储于数组束时间存储于数组s s和和f

6、f中且按结束时间的非减中且按结束时间的非减序排列序排列 6 64.1 活动安排问题 由于输入的活动以其完成时间的由于输入的活动以其完成时间的非减序非减序非减序非减序排列，所排列，所以算法以算法greedySelectorgreedySelectorgreedySelectorgreedySelector每次总是选择每次总是选择具有最早完成时具有最早完成时具有最早完成时具有最早完成时间间间间的相容活动加入集合的相容活动加入集合A A中。直观上，按这种方法选中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意

7、义是是说，该算法的贪心选择的意义是使剩余的可安排时使剩余的可安排时使剩余的可安排时使剩余的可安排时间段极大化间段极大化间段极大化间段极大化，以便安排尽可能多的相容活动。，以便安排尽可能多的相容活动。 算法算法greedySelectorgreedySelectorgreedySelectorgreedySelector的效率极高。当输入的活动的效率极高。当输入的活动已按结束时间的非减序排列，算法只需已按结束时间的非减序排列，算法只需O(n)O(n)O(n)O(n)的时间安的时间安排排n n个活动，使最多的活动能相容地使用公共资源。个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非

8、减序排列，可以用如果所给出的活动未按非减序排列，可以用O(nlognO(nlognO(nlognO(nlogn) ) ) )的时间重排。的时间重排。 7 74.1 活动安排问题 例：例：例：例：设待安排的设待安排的1111个活动的开始时间和结束时间按结个活动的开始时间和结束时间按结束时间的非减序排列如下：束时间的非减序排列如下：i i1 12 23 34 45 56 67 78 89 910101111SiSi 1 13 30 05 53 35 56 68 88 82 21212fifi4 45 56 67 78 89 9101011111212 1313 14148 84.1 活动安排问题

9、算法算法算法算法greedySelectorgreedySelectorgreedySelectorgreedySelector 的的的的计算过程计算过程计算过程计算过程如左图所示。如左图所示。图中每行相应于算法的图中每行相应于算法的一次迭代。阴影长条表一次迭代。阴影长条表示的活动是已选入集合示的活动是已选入集合A A的活动，而空白长条表的活动，而空白长条表示的活动是当前正在检示的活动是当前正在检查相容性的活动。查相容性的活动。9 94.1 活动安排问题 若被检查的活动若被检查的活动i i的开始时间的开始时间SiSi小于最近选择的活动小于最近选择的活动j j的结束时间的结束时间fifi，则不选

10、择活动，则不选择活动i i，否则选择活动，否则选择活动i i加入集合加入集合A A中。中。 贪心算法并不总能求得问题的贪心算法并不总能求得问题的整体最优解整体最优解整体最优解整体最优解。但对于活。但对于活动安排问题，贪心算法动安排问题，贪心算法greedySelectorgreedySelector却总能求得的整体却总能求得的整体最优解，即它最终所确定的相容活动集合最优解，即它最终所确定的相容活动集合A A的规模最大。的规模最大。这个结论可以用数学归纳法证明。这个结论可以用数学归纳法证明。10104.2 贪心算法的基本要素 本节着重讨论可以用贪心算法求解的问题的一般特征。本节着重讨论可以用贪心

11、算法求解的问题的一般特征。 对于一个具体的问题，怎么知道是否可用贪心算法解对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢此问题，以及能否得到问题的最优解呢? ?这个问题很难给这个问题很难给予肯定的回答。予肯定的回答。 但是，从许多可以用贪心算法求解的问题中看到这类但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有问题一般具有2 2个重要的性质：个重要的性质：贪心选择性质贪心选择性质贪心选择性质贪心选择性质和和最优子结最优子结最优子结最优子结构性质构性质构性质构性质。 11114.2 贪心算法的基本要素1 1、贪心选择性质、贪心选择性质 所谓贪心选择性质

12、贪心选择性质是指所求问题的整体最优解整体最优解可以通过一系列局部最优局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。 动态规划算法通常以自底向上自底向上的方式解各子问题，而贪心算法则通常以自顶向下自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。12124.2 贪心算法的基本要素 当一个问题的最优解包含其子问题的最优解时，当一个问题的最优解包含其子问题的最优解时，称此问题具有称此问

13、题具有最优子结构性质最优子结构性质最优子结构性质最优子结构性质。问题的最优子结构性。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键质是该问题可用动态规划算法或贪心算法求解的关键特征。特征。 2 2、最优子结构性质、最优子结构性质13134.2 贪心算法的基本要素 贪心算法和动态规划算法都要求问题具有最优子贪心算法和动态规划算法都要求问题具有最优子结构性质，这是结构性质，这是2 2类算法的一个共同点。但是，对于具类算法的一个共同点。但是，对于具有有最优子结构最优子结构最优子结构最优子结构的问题应该选用贪心算法还是动态规划的问题应该选用贪心算法还是动态规划算法求解算法求解? ?是

14、否能用动态规划算法求解的问题也能用贪是否能用动态规划算法求解的问题也能用贪心算法求解心算法求解? ?下面研究下面研究2 2个经典的个经典的组合优化问题组合优化问题组合优化问题组合优化问题，并以，并以此说明贪心算法与动态规划算法的主要差别。此说明贪心算法与动态规划算法的主要差别。3、贪心算法与动态规划算法的差异14144.2 贪心算法的基本要素0-10-1背包问题：背包问题： 给定给定n n种物品和一个背包。物品种物品和一个背包。物品i i的重量是的重量是WiWi，其价，其价值为值为ViVi，背包的容量为，背包的容量为C C。应如何选择装入背包的物品，。应如何选择装入背包的物品，使得装入背包中物

15、品的总价值最大使得装入背包中物品的总价值最大? ? 在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i i只有只有2 2种选择，即种选择，即装入背包或不装入背包。不能将物品装入背包或不装入背包。不能将物品i i装入背包多次，也不能只装入背包多次，也不能只装入部分的物品装入部分的物品i i。15154.2 贪心算法的基本要素背包问题：背包问题： 与与0-10-1背包问题类似，所不同的是在选择物品背包问题类似，所不同的是在选择物品i i装入背装入背包时，包时，可以选择物品可以选择物品可以选择物品可以选择物品i i i i的一部分的一部分的一部分的一部分，而不一定要全部装入背，而

16、不一定要全部装入背包，包，1in1in。 这2类问题都具有最优子结构最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。 16164.2 贪心算法的基本要素 首先计算每种物品单位重量的价值首先计算每种物品单位重量的价值Vi/Vi/WiWi，然后，依贪心，然后，依贪心选择策略，将尽可能多的选择策略，将尽可能多的单位重量价值最高单位重量价值最高单位重量价值最高单位重量价值最高的物品装入背包。的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过若将这种物品全部装入背包后，背包内的物品总重量未超过C C，则选择单位重量价值次高的物品并尽可能多地

17、装入背包。，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下页：具体算法可描述如下页： 用贪心算法解背包问题的基本步骤：17174.2 贪心算法的基本要素void void KnapsackKnapsack(int(int n,floatn,float M,floatM,float v,floatv,float w,floatw,float x) x) Sort(n,v,wSort(n,v,w); ); intint i; i; for (i=1;i= for (i=1;i=n;in;i+

18、) +) xixi=0;=0; float c=M; float c=M; for (i=1;i= for (i=1;ic) break;c) break; xixi=1;=1; c-= c-=wiwi; ; if (i=n) if (i=n) xixi=c/wic/wi; ; 算法算法knapsackknapsack的的主要计算时间在于将主要计算时间在于将各种物品依其单位重各种物品依其单位重量的价值从大到小排量的价值从大到小排序。因此，算法的计序。因此，算法的计算时间上界为算时间上界为O O（nlognnlogn）。）。为了证明算法的正确为了证明算法的正确性，还必须证明背包性，还必须证明背包

19、问题具有贪心选择性问题具有贪心选择性质质。18184.2 贪心算法的基本要素 对于对于0-10-10-10-1背包问题背包问题背包问题背包问题，贪心选择之所以不能得到最优解，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑上，在考虑0-10-1背包问题时，应比较选择该物品和不选择背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就该物品所导致的最终方案，然后再作出最好选择。

20、由此就导出许多互相重叠的子问题。这正是该问题可用导出许多互相重叠的子问题。这正是该问题可用动态规划动态规划动态规划动态规划算法算法算法算法求解的另一重要特征。求解的另一重要特征。实际上也是如此，动态规划算法的确可以有效地解实际上也是如此，动态规划算法的确可以有效地解0-0-1 1背包问题。背包问题。 19194.3 最优装载 有一批集装箱要装上一艘载重量为有一批集装箱要装上一艘载重量为c c的轮船。其中集的轮船。其中集装箱装箱i i的重量为的重量为WiWi。最优装载问题要求确定在装载体积不。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。受限制的情况下，将尽可能多的

21、集装箱装上轮船。1 1 1 1、算法描述、算法描述、算法描述、算法描述最优装载问题可用贪心算法求解。采用重量最轻者先最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下页。算法描述如下页。 20204.3 最优装载templatetemplatevoid void LoadingLoading(int(int x, Type w, Type c, x, Type w, Type c, intint n) n) intint *t = new *t = new intint n+1; n+1

22、; Sort(wSort(w, t, n);, t, n); for ( for (intint i = 1; i = n; i+) i = 1; i = n; i+) xixi = 0; = 0; for ( for (intint i = 1; i = n & i = 1; i = n & wtiwti = c; i+) = c; i+) xtixti = 1; c -= = 1; c -= wtiwti; 21214.3 最优装载2 2 2 2、贪心选择性质、贪心选择性质、贪心选择性质、贪心选择性质 可以证明最优装载问题具有贪心选择性质可以证明最优装载问题具有贪心选择性质。 3 3 3

23、3、最优子结构性质、最优子结构性质、最优子结构性质、最优子结构性质最优装载问题具有最优子结构性质。最优装载问题具有最优子结构性质。由最优装载问题的贪心选择性质和最优子结构性由最优装载问题的贪心选择性质和最优子结构性质，容易证明算法质，容易证明算法loadingloadingloadingloading的正确性。的正确性。算法算法loadingloadingloadingloading的主要计算量在于将集装箱依其重量的主要计算量在于将集装箱依其重量从小到大排序，故算法所需的计算时间为从小到大排序，故算法所需的计算时间为 O(nlognO(nlognO(nlognO(nlogn) ) ) )。 2

24、2224.4 哈夫曼编码哈夫曼编码哈夫曼编码哈夫曼编码哈夫曼编码是广泛地用于数据文件压缩的十分有效的是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在编码方法。其压缩率通常在20%20%90%90%之间。哈夫曼编码算之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用法用字符在文件中出现的频率表来建立一个用0 0，1 1串表示串表示各字符的最优表示方式。各字符的最优表示方式。 给出现频率高的字符较短的编码，出现频率较低的字给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长。符以较长的编码，可以大大缩短总码长。1 1、前缀码、前缀码对每一个字符规定一

25、个对每一个字符规定一个0,10,1串作为其代码，并要求任串作为其代码，并要求任一字符的代码都不是其它字符代码的前缀。这种编码称为一字符的代码都不是其它字符代码的前缀。这种编码称为前缀码前缀码前缀码前缀码。23234.4 哈夫曼编码 编码的前缀性质可以使译码方法非常简单。编码的前缀性质可以使译码方法非常简单。 表示表示最优前缀码最优前缀码最优前缀码最优前缀码的二叉树总是一棵的二叉树总是一棵完全二叉树完全二叉树完全二叉树完全二叉树，即树，即树中任一结点都有中任一结点都有2 2个儿子结点。个儿子结点。平均码长平均码长平均码长平均码长定义为：定义为：使平均码长达到最小的前缀码编码方案称为给定编码使平均

26、码长达到最小的前缀码编码方案称为给定编码字符集字符集C C的的最优前缀码最优前缀码最优前缀码最优前缀码。 24244.4 哈夫曼编码2 2 2 2、构造哈夫曼编码、构造哈夫曼编码、构造哈夫曼编码、构造哈夫曼编码哈夫曼提出构造最优前缀码的贪心算法，由此产生的哈夫曼提出构造最优前缀码的贪心算法，由此产生的编码方案称为编码方案称为哈夫曼编码哈夫曼编码哈夫曼编码哈夫曼编码。哈夫曼算法以自底向上的方式构造表示最优前缀码的哈夫曼算法以自底向上的方式构造表示最优前缀码的二叉树二叉树T T。算法以算法以|C|C|个叶结点开始，执行个叶结点开始，执行|C|C|1 1次的次的“合并合并”运算后产生最终所要求的树运

27、算后产生最终所要求的树T T。 25254.4 哈夫曼编码 在书上给出的算法在书上给出的算法huffmanTreehuffmanTree中，编码字符集中中，编码字符集中每一字符每一字符c c的频率是的频率是f(c)f(c)。以以以以f f f f为键值的优先队列为键值的优先队列为键值的优先队列为键值的优先队列Q Q Q Q用在用在贪心选择贪心选择贪心选择贪心选择时有效地确定算法当前要合并的时有效地确定算法当前要合并的2 2棵具有最小棵具有最小频率的树。一旦频率的树。一旦2 2棵具有最小频率的树合并后，产生一棵具有最小频率的树合并后，产生一棵新的树，其频率为合并的棵新的树，其频率为合并的2 2棵

28、树的频率之和，并将新棵树的频率之和，并将新树插入优先队列树插入优先队列Q Q。经过。经过n n1 1次的合并后，优先队列中次的合并后，优先队列中只剩下一棵树，即所要求的树只剩下一棵树，即所要求的树T T。算法算法huffmanTreehuffmanTree用最小堆实现优先队列用最小堆实现优先队列Q Q。初始。初始化优先队列需要化优先队列需要O(n)O(n)计算时间，由于最小堆的计算时间，由于最小堆的removeMinremoveMin和和putput运算均需运算均需O(lognO(logn) )时间，时间，n n1 1次的合并次的合并总共需要总共需要O(nlognO(nlogn) )计算时间。

29、因此，关于计算时间。因此，关于n n个字符的哈个字符的哈夫曼算法的夫曼算法的计算时间计算时间计算时间计算时间为为O(nlognO(nlogn) ) 。26264.4 哈夫曼编码3 3 3 3、哈夫曼算法的正确性、哈夫曼算法的正确性、哈夫曼算法的正确性、哈夫曼算法的正确性要证明哈夫曼算法的正确性，只要证明最优前缀码问要证明哈夫曼算法的正确性，只要证明最优前缀码问题具有题具有贪心选择性质贪心选择性质贪心选择性质贪心选择性质和和最优子结构性质最优子结构性质最优子结构性质最优子结构性质。(1)(1)贪心选择性质贪心选择性质(2)(2)最优子结构性质最优子结构性质27274.5 单源最短路径给定带权有向

30、图给定带权有向图G =(V,E)G =(V,E)，其中每条边的权是非负实，其中每条边的权是非负实数。另外，还给定数。另外，还给定V V中的一个顶点，称为中的一个顶点，称为源源源源。现在要计算。现在要计算从源到所有其它各顶点的从源到所有其它各顶点的最短路长度最短路长度最短路长度最短路长度。这里路的长度是指。这里路的长度是指路上各边权之和。这个问题通常称为路上各边权之和。这个问题通常称为单源最短路径问题单源最短路径问题单源最短路径问题单源最短路径问题。1 1、算法基本思想、算法基本思想DijkstraDijkstra算法是解单源最短路径问题的贪心算法。算法是解单源最短路径问题的贪心算法。28284

31、.5 单源最短路径其其基本思想基本思想基本思想基本思想是，设置顶点集合是，设置顶点集合S S并不断地作并不断地作贪心选择贪心选择贪心选择贪心选择来扩充这个集合。一个顶点属于集合来扩充这个集合。一个顶点属于集合S S当且仅当从源到该当且仅当从源到该顶点的最短路径长度已知。顶点的最短路径长度已知。初始时，初始时，S S中仅含有源。设中仅含有源。设u u是是G G的某一个顶点，把从的某一个顶点，把从源到源到u u且中间只经过且中间只经过S S中顶点的路称为从源到中顶点的路称为从源到u u的特殊路径，的特殊路径，并用数组并用数组distdist记录当前每个顶点所对应的最短特殊路径长记录当前每个顶点所对

32、应的最短特殊路径长度。度。DijkstraDijkstra算法每次从算法每次从V-SV-S中取出具有最短特殊路长度中取出具有最短特殊路长度的顶点的顶点u u，将，将u u添加到添加到S S中，同时对数组中，同时对数组distdist作必要的修改。作必要的修改。一旦一旦S S包含了所有包含了所有V V中顶点，中顶点，distdist就记录了从源到所有其它就记录了从源到所有其它顶点之间的最短路径长度。顶点之间的最短路径长度。29294.5 单源最短路径例如例如例如例如，对右图中的，对右图中的有向图，应用有向图，应用DijkstraDijkstra算法计算从源顶点算法计算从源顶点1 1到其到其它顶点

33、间最短路径的过它顶点间最短路径的过程列在下页的表中。程列在下页的表中。30304.5 单源最短路径迭代迭代迭代迭代S S S Su u u udist2dist2dist2dist2 dist3dist3dist3dist3 dist4dist4dist4dist4 dist5dist5dist5dist5 初始初始初始初始11- -1010maxintmaxint30301001001 1 1 11,21,22 21010606030301001002 2 2 21,2,41,2,44 410105050303090903 3 3 31,2,4,31,2,4,33 3101050503030

34、60604 4 4 41,2,4,3,51,2,4,3,5 5 51010505030306060Dijkstra算法的迭代过程： 31314.5 单源最短路径2 2、算法的正确性和计算复杂性、算法的正确性和计算复杂性(1)(1)贪心选择性质贪心选择性质(2)(2)最优子结构性质最优子结构性质(3)(3)计算复杂性计算复杂性对于具有对于具有n n个顶点和个顶点和e e条边的带权有向图，如果用带权条边的带权有向图，如果用带权邻接矩阵表示这个图，那么邻接矩阵表示这个图，那么DijkstraDijkstra算法的主循环体需要算法的主循环体需要 时间。这个循环需要执行时间。这个循环需要执行n-1n-1

35、次，所以完成循环需要次，所以完成循环需要 时间。算法的其余部分所需要时间不超过时间。算法的其余部分所需要时间不超过 。32324.6 最小生成树 设设G =(V,E)G =(V,E)是无向连通带权图，即一个是无向连通带权图，即一个网络网络网络网络。E E中每中每条边条边(v,w)(v,w)的权为的权为cvwcvw。如果。如果G G的子图的子图GG是一棵包含是一棵包含G G的所有顶点的树，则称的所有顶点的树，则称GG为为G G的生成树。生成树上各边权的生成树。生成树上各边权的总和称为该生成树的的总和称为该生成树的耗费耗费耗费耗费。在。在G G的所有生成树中，耗费的所有生成树中，耗费最小的生成树称

36、为最小的生成树称为G G的的最小生成树最小生成树最小生成树最小生成树。网络的最小生成树在实际中有广泛应用。网络的最小生成树在实际中有广泛应用。例如例如例如例如，在设，在设计通信网络时，用图的顶点表示城市，用边计通信网络时，用图的顶点表示城市，用边(v,w)(v,w)的权的权cvwcvw表示建立城市表示建立城市v v和城市和城市w w之间的通信线路所需的费之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。用，则最小生成树就给出了建立通信网络的最经济的方案。 33334.6 最小生成树1 1、最小生成树性质、最小生成树性质用贪心算法设计策略可以设计出构造最小生成树用贪心算法

37、设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的的有效算法。本节介绍的构造最小生成树的PrimPrimPrimPrim算法算法算法算法和和KruskalKruskalKruskalKruskal算法算法算法算法都可以看作是应用贪心算法设计策略的都可以看作是应用贪心算法设计策略的例子。尽管这例子。尽管这2 2个算法做贪心选择的方式不同，它们都个算法做贪心选择的方式不同，它们都利用了下面的利用了下面的最小生成树性质最小生成树性质最小生成树性质最小生成树性质：设设G=(V,E)G=(V,E)是连通带权图，是连通带权图，U U是是V V的真子集。如果的真子集。如果(u,v)(u,

38、v) E E，且，且u u U U，v v V-UV-U，且在所有这样的边中，且在所有这样的边中，(u,v)(u,v)的权的权cuvcuv最小，那么一定存在最小，那么一定存在G G的一棵最小生的一棵最小生成树，它以成树，它以(u,v)(u,v)为其中一条边。这个性质有时也称为为其中一条边。这个性质有时也称为MSTMSTMSTMST性质性质性质性质。 34344.6 最小生成树2 2 2 2、PrimPrimPrimPrim算法算法算法算法 设设G=(V,E)G=(V,E)是连通带权图，是连通带权图，V=1,2,nV=1,2,n。构造构造G G的最小生成树的的最小生成树的PrimPrim算法的算

39、法的基本思想基本思想基本思想基本思想是：首先是：首先置置S=1S=1，然后，只要，然后，只要S S是是V V的真子集，就作如下的的真子集，就作如下的贪心选贪心选贪心选贪心选择择择择：选取满足条件选取满足条件i i S S，j j V-SV-S，且，且cijcij最小的边，最小的边，将顶点将顶点j j添加到添加到S S中。这个过程一直进行到中。这个过程一直进行到S=VS=V时为止。时为止。在这个过程中选取到的所有边恰好构成在这个过程中选取到的所有边恰好构成G G的一棵的一棵最小最小最小最小生成树生成树生成树生成树。 35354.6 最小生成树利用最小生成树性质利用最小生成树性质和数学归纳法容易证

40、明，和数学归纳法容易证明，上述算法中的上述算法中的边集合边集合边集合边集合T T T T始终始终始终始终包含包含包含包含G G G G的某棵最小生成树中的某棵最小生成树中的某棵最小生成树中的某棵最小生成树中的边的边的边的边。因此，在算法结束。因此，在算法结束时，时，T T中的所有边构成中的所有边构成G G的的一棵最小生成树。一棵最小生成树。 例如例如例如例如，对于右图中的，对于右图中的带权图，按带权图，按PrimPrimPrimPrim算法算法算法算法选取选取边的过程如下页图所示。边的过程如下页图所示。36364.6 最小生成树37374.6 最小生成树在上述在上述PrimPrim算法中，还应

41、当考虑算法中，还应当考虑如何有效地找出满如何有效地找出满如何有效地找出满如何有效地找出满足条件足条件足条件足条件i i i i S,jS,jS,jS,j V-SV-SV-SV-S，且权，且权，且权，且权cijcijcijcij最小的边最小的边最小的边最小的边(i,j)(i,j)(i,j)(i,j)。实现。实现这个目的的较简单的办法是设置这个目的的较简单的办法是设置2 2个数组个数组closestclosest和和lowcostlowcost。在在PrimPrim算法执行过程中，先找出算法执行过程中，先找出V-SV-S中使中使lowcostlowcost值值最小的顶点最小的顶点j j，然后根据数

42、组，然后根据数组closestclosest选取边选取边(j,closestj(j,closestj) )，最后将，最后将j j添加到添加到S S中，并对中，并对closestclosest和和lowcostlowcost作必要的修改。作必要的修改。用这个办法实现的用这个办法实现的PrimPrim算法所需的算法所需的计算时间计算时间计算时间计算时间为为 38384.6 最小生成树3 3、KruskalKruskal算法算法KruskalKruskal算法构造算法构造G G的最小生成树的的最小生成树的基本思想基本思想基本思想基本思想是，是，首先将首先将G G的的n n个顶点看成个顶点看成n n个

43、孤立的连通分支。将所有的个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接递增的顺序查看每一条边，并按下述方法连接2 2个不同个不同的连通分支：当查看到第的连通分支：当查看到第k k条边条边(v,w)(v,w)时，如果端点时，如果端点v v和和w w分别是当前分别是当前2 2个不同的连通分支个不同的连通分支T1T1和和T2T2中的顶点时，中的顶点时，就用边就用边(v,w)(v,w)将将T1T1和和T2T2连接成一个连通分支，然后继续连接成一个连通分支，然后继续查看第查看第k+1k+1条边

44、；如果端点条边；如果端点v v和和w w在当前的同一个连通分在当前的同一个连通分支中，就直接再查看第支中，就直接再查看第k+1k+1条边。这个过程一直进行到条边。这个过程一直进行到只剩下一个连通分支时为止。只剩下一个连通分支时为止。 39394.6 最小生成树例如，例如，例如，例如，对前面的连通带权图，按对前面的连通带权图，按KruskalKruskal算法顺序得到的算法顺序得到的最小生成树上的边如下图所示。最小生成树上的边如下图所示。40404.6 最小生成树关于关于集合的一些基本运算集合的一些基本运算集合的一些基本运算集合的一些基本运算可用于实现可用于实现KruskalKruskal算法。

45、算法。 按权的递增顺序查看等价于对按权的递增顺序查看等价于对优先队列优先队列优先队列优先队列执行执行removeMinremoveMinremoveMinremoveMin运算。可以用运算。可以用堆堆堆堆实现这个优先队列。实现这个优先队列。 对一个由连通分支组成的集合不断进行修改，需要用对一个由连通分支组成的集合不断进行修改，需要用到抽象数据类型到抽象数据类型并查集并查集并查集并查集UnionFindUnionFindUnionFindUnionFind所支持的基本运算。所支持的基本运算。当图的边数为当图的边数为e e时，时，KruskalKruskal算法所需的算法所需的计算时间计算时间计算

46、时间计算时间是是 。当。当 时，时，KruskalKruskal算法比算法比PrimPrim算法差，但当算法差，但当 时，时，KruskalKruskal算法却比算法却比PrimPrim算法好得多。算法好得多。41414.7 多机调度问题多机调度问题多机调度问题多机调度问题多机调度问题要求给出一种作业调度方案，使所给的要求给出一种作业调度方案，使所给的n n个作业在尽可能短的时间内由个作业在尽可能短的时间内由m m台机器加工处理完成。台机器加工处理完成。这个问题是这个问题是NPNPNPNP完全问题完全问题完全问题完全问题，到目前为止还没有有效的解，到目前为止还没有有效的解法。对于这一类问题法。

47、对于这一类问题, ,用用贪心选择策略贪心选择策略贪心选择策略贪心选择策略有时可以设计出较有时可以设计出较好的近似算法。好的近似算法。 约定，每个作业均可在任何一台机器上加工处理，但未约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。完工前不允许中断处理。作业不能拆分成更小的子作业。42424.7 多机调度问题采用采用最长处理时间作业优先最长处理时间作业优先最长处理时间作业优先最长处理时间作业优先的贪心选择策略可以设计的贪心选择策略可以设计出解多机调度问题的较好的近似算法。出解多机调度问题的较好的近似算法。按此策略，当按此策略，当 时，只要将机器时

48、，只要将机器i i的的0, 0, ti ti 时间区时间区间分配给作业间分配给作业i i即可，算法只需要即可，算法只需要O(1)O(1)时间。时间。当当 时，首先将时，首先将n n个作业依其所需的处理时间个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为算法所需的计算时间为O(nlognO(nlogn) )。43434.7 多机调度问题例如，例如，例如，例如，设设7 7个独立作业个独立作业1,2,3,4,5,6,71,2,3,4,5,6,7由由3 3台机器台机器M1M1，M2M2和和M3M3加工处

49、理。各作业所需的处理时间分别为加工处理。各作业所需的处理时间分别为2,14,4,16,6,5,32,14,4,16,6,5,3。按算法。按算法greedygreedygreedygreedy产生的作业调度如产生的作业调度如下图所示，所需的加工时间为下图所示，所需的加工时间为1717。 44444.8 贪心算法的理论基础借助于借助于拟阵拟阵拟阵拟阵工具，可建立关于贪心算法的较一般工具，可建立关于贪心算法的较一般的理论。这个理论对的理论。这个理论对确定何时使用贪心算法确定何时使用贪心算法确定何时使用贪心算法确定何时使用贪心算法可以得到可以得到问题的整体最优解十分有用。问题的整体最优解十分有用。1

50、1 1 1、拟阵、拟阵、拟阵、拟阵拟阵拟阵M M定义为满足下面定义为满足下面3 3个条件的有序对个条件的有序对(S,I)(S,I)：(1)S(1)S是非空有限集。是非空有限集。(2)I(2)I是是S S的一类具有遗传性质的独立子集族，即若的一类具有遗传性质的独立子集族，即若B B I I，则，则B B是是S S的独立子集，且的独立子集，且B B的任意子集也都是的任意子集也都是S S的独立的独立子集。空集子集。空集必为必为I I的成员。的成员。(3)I(3)I满足交换性质，即若满足交换性质，即若A A I,BI,B I I且且|A|B|A|0W(x)0，则称拟阵，则称拟阵M M为为带权拟阵带权拟

51、阵带权拟阵带权拟阵。依此权函数，。依此权函数，S S的任一子集的任一子集A A的权定义为的权定义为 。2 2 2 2、关于带权拟阵的贪心算法、关于带权拟阵的贪心算法、关于带权拟阵的贪心算法、关于带权拟阵的贪心算法许多可以用贪心算法求解的问题可以表示为求带权拟许多可以用贪心算法求解的问题可以表示为求带权拟阵的阵的最大权独立子集问题最大权独立子集问题最大权独立子集问题最大权独立子集问题。 47474.8 贪心算法的理论基础给定带权拟阵给定带权拟阵M=(S,I)M=(S,I)，确定，确定S S的独立子集的独立子集A A I I使得使得W(A)W(A)达到最大。这种使达到最大。这种使W(A)W(A)最

52、大的独立子集最大的独立子集A A称为拟阵称为拟阵M M的的最优子集最优子集最优子集最优子集。由于。由于S S中任一元素中任一元素x x的权的权W(x)W(x)是正的，因此，是正的，因此，最最最最优子集也一定是极大独立子集优子集也一定是极大独立子集优子集也一定是极大独立子集优子集也一定是极大独立子集。例如，例如，例如，例如，在最小生成树问题可以表示为确定带权拟阵在最小生成树问题可以表示为确定带权拟阵 的最优子集问题。求带权拟阵的最优子集的最优子集问题。求带权拟阵的最优子集A A的算法可用于的算法可用于解最小生成树问题。解最小生成树问题。下面给出求下面给出求带权拟阵最优子集带权拟阵最优子集带权拟阵

53、最优子集带权拟阵最优子集的贪心算法。该算法以的贪心算法。该算法以具有正权函数具有正权函数W W的带权拟阵的带权拟阵M=(S,I)M=(S,I)作为输入，经计算后输作为输入，经计算后输出出M M的最优子集的最优子集A A。48484.8 贪心算法的理论基础Set Set greedygreedygreedygreedy (M,W) (M,W)A=A=; ; 将将S S中元素依权值中元素依权值W W（大者优先）组成优先队列；（大者优先）组成优先队列； while (S!=while (S!=) ) S.removeMax(xS.removeMax(x);); if (Ax if (Ax I) A=

54、Ax;I) A=Ax; return A return A 49494.8 贪心算法的理论基础算法算法greedygreedygreedygreedy的计算时间复杂性为的计算时间复杂性为 。引理引理引理引理4.24.24.24.2( ( ( (拟阵的贪心选择性质拟阵的贪心选择性质拟阵的贪心选择性质拟阵的贪心选择性质) ) ) )设设M=(S,I)M=(S,I)是具有权函数是具有权函数W W的带权拟阵，且的带权拟阵，且S S中元素依中元素依权值从大到小排列。又设权值从大到小排列。又设x x S S是是S S中第一个使得中第一个使得xx是独立是独立子集的元素，则存在子集的元素，则存在S S的最优子

55、集的最优子集A A使得使得x x A A。算法算法greedygreedygreedygreedy在以贪心选择构造最优子集在以贪心选择构造最优子集A A时，首次选时，首次选入集合入集合A A中的元素中的元素x x是单元素独立集中具有最大权的元素。是单元素独立集中具有最大权的元素。此时可能已经舍弃了此时可能已经舍弃了S S中部分元素。可以证明这些被舍弃中部分元素。可以证明这些被舍弃的元素不可能用于构造最优子集。的元素不可能用于构造最优子集。50504.8 贪心算法的理论基础引理引理引理引理4.34.34.34.3：设设M=(S,I)M=(S,I)是拟阵。若是拟阵。若S S中元素中元素x x不是空

56、集不是空集的可的可扩展元素，则扩展元素，则x x也不可能是也不可能是S S中任一独立子集中任一独立子集A A的可扩展元的可扩展元素。素。引理引理引理引理4.4(4.4(4.4(4.4(拟阵的最优子结构性质拟阵的最优子结构性质拟阵的最优子结构性质拟阵的最优子结构性质) ) ) )设设x x是求带权拟阵是求带权拟阵M M(S(S，I)I)的最优子集的贪心算法的最优子集的贪心算法greedygreedygreedygreedy所选择的所选择的S S中的第一个元素。那么，原问题可简化中的第一个元素。那么，原问题可简化为求带权拟阵为求带权拟阵M=(S,I)M=(S,I)的的最优子集最优子集最优子集最优子

57、集问题，其中：问题，其中：S=y|yS=y|y S S且且x,y x,y III=B|BI=B|B S-xS-x且且Bx Bx IIMM的权函数是的权函数是M M的权函数在的权函数在SS上的限制上的限制( (称称MM为为M M关关于元素于元素x x的的收缩收缩收缩收缩) )。51514.8 贪心算法的理论基础定理定理定理定理4.5(4.5(4.5(4.5(带权拟阵贪心算法的正确性带权拟阵贪心算法的正确性带权拟阵贪心算法的正确性带权拟阵贪心算法的正确性) ) ) )设设M M(S,I)(S,I)是具有权函数是具有权函数W W的带权拟阵，算法的带权拟阵，算法greedygreedy返回返回M M的

58、最优子集。的最优子集。3 3、任务时间表问题、任务时间表问题给定一个给定一个单位时间任务单位时间任务单位时间任务单位时间任务的有限集的有限集S S。关于。关于S S的一个的一个时间表时间表时间表时间表用于描述用于描述S S中单位时间任务的执行次序。时间表中单位时间任务的执行次序。时间表中第中第1 1个任务从时间个任务从时间0 0开始执行直至时间开始执行直至时间1 1结束，第结束，第2 2个个任务从时间任务从时间1 1开始执行至时间开始执行至时间2 2结束，结束，第，第n n个任务从个任务从时间时间n-1n-1开始执行直至时间开始执行直至时间n n结束。结束。52524.8 贪心算法的理论基础具

59、有具有截止时间截止时间截止时间截止时间和和误时惩罚误时惩罚误时惩罚误时惩罚的单位时间任务时间表问题的单位时间任务时间表问题可描述如下。可描述如下。(1) n(1) n个单位时间任务的集合个单位时间任务的集合S=1,2,nS=1,2,n；(2) (2) 任务任务i i的截止时间的截止时间 ,1in,1 n,1in,1 n，即要求，即要求任务任务i i在时间在时间 之前结束；之前结束；(3) (3) 任务任务i i的误时惩罚的误时惩罚 ,1in,1in,即任务即任务i i未在时间未在时间 之前结束将招致的之前结束将招致的 惩罚；若按时完成则无惩罚。惩罚；若按时完成则无惩罚。任务时间表问题任务时间表

60、问题任务时间表问题任务时间表问题要求确定要求确定S S的一个时间表（最优时间的一个时间表（最优时间表）使得总误时惩罚达到最小。表）使得总误时惩罚达到最小。53534.8 贪心算法的理论基础这个问题看上去很复杂，然而借助于这个问题看上去很复杂，然而借助于拟阵拟阵拟阵拟阵，可以用，可以用带带带带权拟阵的贪心算法权拟阵的贪心算法权拟阵的贪心算法权拟阵的贪心算法有效求解。有效求解。对于一个给定的对于一个给定的S S的时间表，在截止时间之前完成的的时间表，在截止时间之前完成的任务称为任务称为及时任务及时任务及时任务及时任务，在截止时间之后完成的任务称为，在截止时间之后完成的任务称为误时误时误时误时任务任

61、务任务任务。S S的任一时间表可以调整成的任一时间表可以调整成及时优先形式及时优先形式及时优先形式及时优先形式，即其中所，即其中所有及时任务先于误时任务，而不影响原时间表中各任务的有及时任务先于误时任务，而不影响原时间表中各任务的及时或误时性质。及时或误时性质。类似地，还可将类似地，还可将S S的任一时间表调整成为的任一时间表调整成为规范形式规范形式规范形式规范形式，其中及时任务先于误时任务，且及时任务依其截止时间的其中及时任务先于误时任务，且及时任务依其截止时间的非减序排列。非减序排列。54544.8 贪心算法的理论基础首先可将时间表调整为及时优先形式，然后再进一步首先可将时间表调整为及时优

62、先形式，然后再进一步调整及时任务的次序。调整及时任务的次序。任务时间表问题任务时间表问题等价于等价于等价于等价于确定最优时间表中确定最优时间表中及时任务子及时任务子及时任务子及时任务子集集集集A A A A的问题。一旦确定了及时任务子集的问题。一旦确定了及时任务子集A A，将，将A A中各任务依中各任务依其截止时间的非减序列出，然后再以任意次序列出误时任其截止时间的非减序列出，然后再以任意次序列出误时任务，即务，即S-AS-A中各任务，由此产生中各任务，由此产生S S的一个规范的最优时间表。的一个规范的最优时间表。对时间对时间t=1,2,nt=1,2,n，设设设设 (A)(A)是任务子集是任务

63、子集A A中所有截止中所有截止时间是时间是t t或更早的任务数。考察任务子集或更早的任务数。考察任务子集A A的独立性。的独立性。55554.8 贪心算法的理论基础引理引理引理引理4.64.64.64.6：对于对于S S的任一任务子集的任一任务子集A A，下面的各命题是等价，下面的各命题是等价的。的。(1) (1) 任务子集任务子集A A是独立子集。是独立子集。(2) (2) 对于对于t=1,2,nt=1,2,n， (A)t(A)t。(3) (3) 若若A A中任务依其截止时间非减序排列，则中任务依其截止时间非减序排列，则A A中所有任务中所有任务都是及时的。都是及时的。任务时间表问题任务时间

64、表问题任务时间表问题任务时间表问题要求使总误时惩罚达到最小，这等价要求使总误时惩罚达到最小，这等价于使任务时间表中的及时任务的惩罚值之和达到最大。下于使任务时间表中的及时任务的惩罚值之和达到最大。下面的面的定理定理定理定理表明可用带权拟阵的贪心算法解任务时间表问题。表明可用带权拟阵的贪心算法解任务时间表问题。56564.8 贪心算法的理论基础定理定理定理定理4.74.74.74.7：设设S S是带有截止时间的单位时间任务集，是带有截止时间的单位时间任务集，I I是是S S的所有独立任务子集构成的集合。则有序对的所有独立任务子集构成的集合。则有序对(S,I)(S,I)是是拟阵。拟阵。由由定理定理

65、定理定理4.54.54.54.5可知，用带权拟阵的贪心算法可以求得最可知，用带权拟阵的贪心算法可以求得最大权大权( (惩罚惩罚) )独立任务子集独立任务子集A A，以，以A A作为最优时间表中的及作为最优时间表中的及时任务子集，容易构造最优时间表。时任务子集，容易构造最优时间表。任务时间表问题的贪心算法的任务时间表问题的贪心算法的计算时间复杂性计算时间复杂性计算时间复杂性计算时间复杂性是是 。其中。其中f(n)f(n)是用于检测任务子集是用于检测任务子集A A的独立性所需的时间。的独立性所需的时间。用引理用引理4.64.6中性质中性质(2)(2)容易设计一个容易设计一个 时间算法来检测任务子集

66、的独立性。因此，整个算法的时间算法来检测任务子集的独立性。因此，整个算法的计算时间计算时间计算时间计算时间为为 。具体算法。具体算法greedyJobgreedyJobgreedyJobgreedyJob可描述如可描述如P130P130。57574.8 贪心算法的理论基础用抽象数据类型并查集用抽象数据类型并查集UnionFindUnionFindUnionFindUnionFind可对上述算法作可对上述算法作进一步改进。如果不计预处理的时间，改进后的算法进一步改进。如果不计预处理的时间，改进后的算法fasterJobfasterJobfasterJobfasterJob所需的所需的计算时间计算时间计算时间计算时间为为 。 5858课后作业课后作业课后作业课后作业习题习题 4-14-1，4-44-4，4-244-24，4-254-25，4-264-26，4-274-27，4-284-28，4-314-31，4-324-3259596060