Lecture09 Greedy Algorithms (1)

1、 1Chapt09 Greedy Algorithms (1) 2review ch08 DP1.Definition :dynamic programming2.Definition :principle of optimality3.Two principles : principle of optimality and subporblems4.Four steps of solution by dynamic programming5.In Common and difference between dynamic programming and divide-and-conquer6

2、.Three examples (Fibonacci,BC,LCS, Knapsack Problem ) 3Main topics of this chapternIdea of the greedy approachnDifference between DP and GAnChange-making problemnActivity arrangementn0-1 Knapsack problem and Knapsack problemnMulti machine scheduling problemnMinimum spanning tree problemnPrims algori

3、thmnKruskals algorithmnHuffman T 4Expected OutcomesnYou should be able tonsummarize the idea of the greedy techniquenlist several applications of the greedy techniquenapply the greedy technique to change-making problemndefine the minimum spanning tree problemndesofcribe ideas Prim and Kruskals algor

4、ithms for computing minimum spanning tree nprove the correctness of the two algorithmsnanalyze the time complexities of the two algorithms under different data structuresnprove the various properties of minimum spanning 5For example : Change Making ProblemnThe idea:nTake the coin with largest denomi

5、nation without exceeding the remaining amount of cents, nmake the locally best choice at each step.每步都是当前最优ngive change for amount n with the least number of coins达到最后使用的硬币数最少nd1 = 7c, d2 =5c, d3 = 1c, and pay 20c, n=？ 6For example :Change-making problem: n当前有面值分别为2角5分，1角，5分，1分的硬币，请给出找n分钱的最佳方案 7Gene

6、ral Change-Making ProblemDoes the greedy algorithm always give an optimal solution for the general change-making problem?贪心算法总能得到最优解吗Examplenot always produces an optimal solution : d1 = 7c, d2 =5c, d3 = 1c, and pay=10c, n =? 7c*1+1c*3 4个 5C*2not have a solution at all ：d1 = 7c, d2 =5c, d3 = 3c, and

7、 pay=11c, n =? 4C不是最优解，甚至无解! 特点？ 8Greedy AlgorithmsnA greedy algorithm makes a locally optimal choice step by step in the hope that this choice will lead to a globally optimal solution. The choice made at each step must be:nFeasiblenSatisfy the problems constraints 满足问题要求nlocally optimalnBe the best

8、 local choice among all feasible choices 具有局部最优nIrrevocablenOnce made, the choice cant be changed on subsequent steps.不可逆转nThat is, it makes a locally optimal choice in the hope that this choice will lead to a globally optimal 9Two basic properties of the greedy algorithmnKnow whether the available

9、greedy algorithm for solving it? - Difficult to answer.nHowever, you can see from the many you can use the greedy algorithm for solving the problems they generally have two important properties:ngreedy choose and optimal substructure 贪心选择性质和最优子结构性质。 10greedy choose propertyn所求问题的整体最优解可以通过局部最优的选择（贪心选

10、择），而达到整体最优。n贪心选择: 依赖于以往作过的选择，不依赖于将来所作的选择，也不依赖于子问题的解。自项向下的方式进行，将所求问题简化为一个规模更小的子问题。n对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。-如何证明？数学归纳法 11optimal substructure propertyn当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质。n这是问题能用贪心算法求解地一个关键特征。对于一些问题，可通过局部最优会导致整体最优！ 12Difference between DP and GAnDP：两个性质：最

11、优子结构，重叠子问题；nGA：两个性质：最优子结构，贪心选择；n相同点：都要求有最优子结构，都是一种递推算法n不同点： GA最终解依赖于以往解的选择，不nDP算法： 1.可求得全局最优解，需要记录之前的所有最优解 。2. 通过局部最优解来推导全局最优解 ,依赖所有子问题的求解，n GA 1. 不能保证求得的最后解是最佳的； 2. 只依赖以往的求解，不依赖子问题的求解，也不依赖将来所做的选择； 13Applications of the Greedy StrategynOptimal solutions:nsome instances of change makingnActivity arra

12、ngementnKnapsack problemnNext week:nMinimum Spanning Tree (MST)nSingle-source shortest paths nHuffman codesnTraveling Salesman Problem (TSP) 14 Question1: Activity arrangement 活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。 15Question1:

13、 Activity arrangement 设有n个活动的集合E=1,2,n，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si fi 。如果选择了活动i，则它在半开时间区间si, fi)内占用资源。若区间si, fi)与区间sj, fj)不相交，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。 16Question1: Activity arrangementntemplatenvoid GreedySelector(int n, Type s, T

14、ype f, bool A)nn A1=true;n int j=1;n for (int i=2;i=fj) Ai=true; j=i; n else Ai=false;n n活动安排问题的贪心算法GreedySelectorGreedySelector :各活动的起始时间和结束各活动的起始时间和结束时间存储于数组时间存储于数组s s和和f f中且中且按结束时间的非减序排列按结束时间的非减序排列 1717Activity arrangement 由于输入的活动以其完成时间的非减序非减序排列，所以算法greedySelectorgreedySelector每次总是选择具有最早完成时具有最早完成

15、时间间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时使剩余的可安排时间段极大化间段极大化，以便安排尽可能多的相容活动。 算法greedySelectorgreedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)O(nlogn)的时间重排。 1818 例：例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：Activity 1919 算法

16、算法greedySelector greedySelector 的的计算过程计算过程如左图所示。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。Activity 2020 若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中。 贪心算法并不总能求得问题的整体最优解整体最优解。但对于活动安排问题，贪心算法greedySelector却总能求得的整体最优解，即它最终所确定的相容活动集合A的规模最大。这个结论可以用数学归纳法证明。Question1: Activity 212

17、1共同点：贪心算法和动态规划算法都要求问题具有最优子结构性质。 但是，对于具有最优子结构最优子结构的问题应该选用贪心算法还是动态规划算法求解?是否能用动态规划算法求解的问题也能用贪心算法求解? 下面研究2个经典的组合优化问题组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。Difference between DP and GA from0-1knapsack 22220-1 Knapsack problemn给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品在选择装入

18、背包的物品时，对每种物品i i只有只有2 2种选择，即种选择，即装入背包或不装入背包。不能将物品装入背包或不装入背包。不能将物品i i装入背包多次，也不能只装入背包多次，也不能只装入部分的物品装入部分的物品i i。 23Question: 0-1 Knapsack problemnReview dynamic programming第i个物品重量价值1212211033204215最大承重量W=5求最大价值V =？Greedy: V3+V4=35 是否每次包含最优解? 物品 2424Knapsack problem n与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品可以选择

19、物品i i的一部分的一部分，而不一定要全部装入背包，1in。 这2类问题都具有最优子结构最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。 2525Steps of Knapsack problem 首先计算每种物品单位重量的价值Vi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。 具体算法可描述如下页： 2626Knapsack problem nvoid Kn

20、apsack(int n,float M,float v,float w,float x)nn Sort(n,v,w);n int i;n for (i=1;i=n;i+) xi=0;n float c=M;n for (i=1;ic) break;n xi=1;n c-=wi;n n if (i=n) xi=c/wi;n 算法算法knapsackknapsack的主要计算时间在的主要计算时间在于将各种物品依其于将各种物品依其单位重量的价值从单位重量的价值从大到小排序。因此，大到小排序。因此，算法的计算时间上算法的计算时间上界为界为O O（nlognnlogn）。）。为了证明算法的正为了证明算

21、法的正确性，还必须证明确性，还必须证明背包问题具有贪心背包问题具有贪心选择性质选择性质。 27Question: Knapsack problem第i个物品重量价值单位价值12126211010332020/3421515/2W=5,V =？Greedy: V2 =10 , V4=15, V3=40/3 2828 多机调度问题多机调度问题多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由m台机器加工处理完成。这个问题是NPNP完全问题完全问题，到目前为止还没有有效的解法。对于这一类问题,用贪心选择策略贪心选择策略有时可以设计出较好的近似算法。 约定，每个作业均可在任何一

22、台机器上加工处理，但未约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业。完工前不允许中断处理。作业不能拆分成更小的子作业。 2929多机调度问题采用最长处理时间作业优先最长处理时间作业优先的贪心选择策略可以设计出解多机调度问题的较好的近似算法。按此策略，当 时，只要将机器i的0, ti时间区间分配给作业i即可，算法只需要O(1)时间。当 时，首先将n个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所需的计算时间为O(nlogn)。将最大机器时间优先分配给最长作业则先分配M1,M2,M3给作业：4，2，5mn mn

23、3030多机调度问题例如，例如，设7个独立作业1,2,3,4,5,6,7由3台机器M1，M2和M3加工处理。各作业所需的处理时间分别为2,14,4,16,6,5,3。按算法greedygreedy产生的作业调度如下图所示，所需的加工时间为17。 31QuestionnDefinition Greedy algorithmnWhat are two basic properties of greedy algorithm?nWhat are the differences between Greedy algorithm and dynamic programming?n编程：n1.用贪心算法实

24、现找零问题，观察是否能得到最优解？n2.贪心算法实现0-1背包问题和背包问题，并比较.n3.用贪心算法实现活动安排问题 32用贪心算法 求解0/1背包问题和背包问题n一、实验内容：n用贪心算法 求解0/1背包问题和背包问题。n二、所用算法的基本思想及复杂度分析：n求解0/1背包问题基本思想及复杂度分析n求解背包问题基本思想及复杂度分析n三、程序伪码：n四、源程序及注释：n五、运行输出结果： n六、调试和运行程序过程中产生的问题、采取的措施及获得的相关经验教训： 33Chapt09 Greedy Algorithms (2) 34 Greedy Algorithms -2nMinimum spa

25、nning tree problemnPrims algorithmnKruskals algorithmnProperties of minimum spanning tree (additive part)nBottleneck spanning tree (additive part) 35Minimum Spanning Tree (MST)nSpanning tree of a connected graph G is a connected acyclic subgraph (tree) of G that includes all of Gs vertices.nNote: a

26、spanning tree with n vertices has exactly n-1 edges.nMinimum Spanning Tree of a weighted, connected graph G is a spanning tree of G of minimum total weight.nExample: 36MST ProblemnGiven a connected, undirected, weighted graph G= (V, E), find a minimum spanning tree for it. nCompute MST through Brute

27、 Force?Brute forceGenerate all possible spanning trees for the given graph.Find the one with minimum total weight.Feasibility of Brute forcePossible too many trees (exponential for dense graphs) 37The Prims AlgorithmnIdea of the Prims algorithmnPseudo-code of the algorithmnTime complexity of the 38I

28、dea of PrimnGrow a single tree by repeatedly adding the least cost edge (greedy step) that connects a vertex in the existing tree to a vertex not in the existing tree 每次选择一个权重最小的边PrimPrim算法算法 设G=(V,E)是连通带权图，V=1,2,n。构造G的最小生成树的Prim算法的基本思想基本思想是：首先置S=1，然后，只要S是V的真子集，就作如下的贪心选择贪心选择：选取满足条件iS，jV-S，且cij最小的边，将

29、顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树最小生成树。 39Prims MST algorithmnStart with a tree , T0 ,consisting of one vertexn“Grow” tree one vertex/edge at a time Construct a series of expanding subtrees T1, T2, Tn-1. .At each stage construct Ti from Ti-1 by nadding the minimum weight edge that

30、connecting a vertex in tree (Ti-1) to a vertex not yet in the treenthis is the “greedy” step!nAlgorithm stops when all vertices are 40Pseudocode of the PrimALGORITHM Prim(G)/Prims algorithm for constructing a minimum spanning tree/Input: A weighted connected graph G = (V, E)/Output: ET, the set of e

31、dges composing a minimum spanning tree of GVT v0 /v0 任意顶点来初始化ET for i 1 to |V|-1 do find a minimum-weight edge e* = (v*, u*) among all the edges (v, u) such that v is in VT and u is in V-VT /求权重最小边 VT VT u* ET ET e*return ET 41The Prims algorithm is greedy!nThe choice of edges added to current subtr

32、ee satisfying the three properties of greedy algorithms.nFeasible, each edge added to the tree does not result in a cycle, guarantee that the final ET is a spanning treenLocal optimal, each edge selected to the tree is always the one with minimum weight among all the edges crossing VT and V-VT nIrre

33、vocable, once an edge is added to the tree, it is not removed in subsequent 42Advanced Prims Algorithm ALGORITHM MST-PRIM( G, w, r ) /w: weight; r: root, the starting vertex1.for each u VG2. do keyu 3. u NIL/ u : the parent of u4.keyr 05.Q VG /Now the priority queue, Q, has been built.6.while Q 7. d

34、o u Extract-Min(Q) /remove the nearest vertex from Q8. for each v Adju / update the key for each of vs adjacent nodes.9. do if v Q and w(u,v) keyv10. then v u11. keyv w(u,v) 44Class question:求用Prim求最小生成生树对于右图中的带权图，按PrimPrim算法算法选取边的过程设初始顶点V0为 46Kruskals MST AlgorithmnEdges are initially sorted by increasing weightnStart with an empty forest F0n“grow” MST one edge at a time through a series of expanding forests F1, F2, , Fn-1nintermediate stages usually have forest of trees (not connected) nat each stage add