1、Copyright Li Zimao 2007-2008-1 SCUECGreedy Algorithms(I)Greed,for lack of a better word,is good!Greed is right!Greed works!-Michael Douglas,U.S.actor in the role of Gordon Gecko,in the film Wall Street,1987Main topicsnIdea of the greedy approachnChange-making problemnMinimum spanning tree problemnPr
2、ims algorithmnKruskals algorithmnProperties of minimum spanning tree(additive part)nBottleneck spanning tree(additive part)Expected OutcomesnStudent should be able tonsummarize the idea of the greedy techniquenlist several applications of the greedy techniquenapply the greedy technique to change-mak
3、ing problemndefine the minimum spanning tree problemndescribe ideas of Prim and Kruskals algorithms 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 min
4、imum spanning treeGlossarynGreedy:贪婪的nChange-making problem:找零钱问题nCashier:收银员nDenomination:货币单位，面额nQuarter,dime,nickel,penny:2角5分，1角，5分，1分（美国硬币单位）nIrrevocable：不可取消的，不可逆的 nSpanning tree:生成树，支撑树Anticipatory Set:Change Making ProblemnHow to make 48 cents of change using coins of denominations of 25(1 q
5、uarter coin),10(1 dime coin),5(1 nickel coin),and 1(1 penny coin)so that the total number of coins is the smallest?nThe idea:nTake the coin with largest denomination without exceeding the remaining amount of cents,nmake the locally best choice at each step.nIs the solution optimal?Yes,the proof is l
6、eft as exercise.General Change-Making ProblemGiven unlimited amounts of coins of denominations d1 dm,give change for amount n with the least number of coins.Does the greedy algorithm always give an optimal solution for the general change-making problem?We give the following example,Example:d1=7c,d2=
7、5c,d3=1c,and n=10c,not always produces an optimal solution.in fact,for some instances,the problem may not have a solution at all!consider instance d1=7c,d2=5c,d3=3c,and n=11c.But,this problem can be solved by dynamic programming,please try to design an algorithm for the general change-making problem
8、 after class.Greedy 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 constraintsnlocally optimalnBe the best local choice among all feasi
9、ble choicesnIrrevocablenOnce made,the choice cant be changed on subsequent steps.nDo greedy algorithms always yield optimal solutions?nExample:change making problem with a denomination set of 7,5 and 1,and n=10?Applications of the Greedy StrategynOptimal solutions:nsome instances of change makingnMi
10、nimum Spanning Tree(MST)nSingle-source shortest paths nHuffman codesnApproximations:nTraveling Salesman Problem(TSP)nKnapsack problemnother optimization problemsMinimum Spanning Tree(MST)nSpanning tree of a connected graph G is a connected acyclic subgraph(tree)of G that includes all of Gs vertices.
11、nNote:a 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:MST ProblemnGiven a connected,undirected,weighted graph G=(V,E),find a minimum spanning tree for it.nCompute MST through Brute F
12、orce?nKruskal:1956,Prim:1957Brute 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)The Prims AlgorithmnIdea of the Prims algorithmnPseudo-code of the algorithmnCorrectne
13、ss of the algorithm(important)nTime complexity of the algorithmIdea 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 treenIntermediate solution is always a subtree of some minimum spanning tree
14、.Prims 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 connecting a vertex in tree(Ti-1)to a vertex not yet in the treenth
15、is is the“greedy”step!nAlgorithm stops when all vertices are includedPseudocode 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 edges composing a minimum spanning tree of GVT v0 /v0 can be arbitrarily
16、 selectedET 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 ETAn exampleaedcb1524637The Prims algorithm is greedy!nThe choice of edges added to current subtree satisfying the three properties of greedy algor
17、ithms.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 nIrrevocable,once an edge is added to the tree,it is not r
18、emoved in subsequent steps.Correctness of PrimnProve by induction that this construction process actually yields MST.nT0 is a subset of all MSTsnSuppose that Ti-1 is a subset of some MST T,we should prove that Ti which is generated from Ti-1 is also a subset of some MST.nBy contradiction,assume that
19、 Ti does not belong to any MST.nLet ei=(u,v)be the minimum weight edge from a vertex in Ti-1 to a vertex not in Ti-1 used by Prims algorithm to expanding Ti-1 to Ti,according to our assumption,ei can not belong to MST T.nAdding ei to T results in a cycle containing another edge e=(u,v)connecting a v
20、ertex u in Ti-1 to a vertex v not in it,and w(e)w(ei)according to the greedy Prims algorithm.nRemoving e from T and adding ei to T results in another spanning tree T with weight w(T)w(T),indicating that T is a minimum spanning tree including Ti which contradict to assumption that Ti does not belong
21、to any MST.Correctness of PrimImplementation of PrimnHow to implement the steps in the Prims algorithm?nFirst idea,label each vertex with either 0 or 1,1 represents the vertex in VT,and 0 otherwise.nTraverse the edge set to find an minimum weight edge whose endpoints have different labels.nTime comp
22、lexity:O(VE)if adjacency linked list and O(V3)for adjacency matrixnFor sparse graphs,use adjacency linked listnAny improvement?NotationsnT:the expanding subtree.nQ:the remaining vertices.At each stage,the key point of expanding the current subtree T is to nDetermine which vertex in Q is the nearest
23、vertex to T.nQ can be thought of as a priority queue:nThe key(priority)of each vertex,keyv,means the minimum weight edge from v to a vertex in T.Keyv is if v is not linked to any vertex in T.nThe major operation is to to find and delete the nearest vertex(v,for which keyv is the smallest among all t
24、he vertices)nRemove the nearest vertex v from Q and add it and the corresponding edge to T.nWith the occurrence of that action,the key of vs neighbors will be changed.To remember the edges of the MST,an array is introduced to record the parent of each vertex.That is v is the vertex in the expanding
25、subtree T that is closest to v not in T.Advanced Prims Algorithm ALGORITHM MST-PRIM(G,w,r)/w:weight;r:root,the starting vertexnfor each u VGn do keyu n u NIL/u:the parent of unkeyr 0nQ VG/Now the priority queue,Q,has been built.nwhile Q n do u Extract-Min(Q)/remove the nearest vertex from Qn for eac
26、h v Adju /update the key for each of vs adjacent nodes.n do if v Q and w(u,v)keyvn then v u1.keyv w(u,v)Time Complexity of Prims algorithmnNeed priority queue for locating the nearest vertexnUse unordered array to store the priority queue:Efficiency:(n2)nUse binary min-heap to store the priority que
27、ueEfficiency:For graph with n vertices and m edges:O(m log n)nUse Fibonacci-heap to store the priority queue:Efficiency:For graph with n vertices and m edges:O(n log n+m)Kruskals MST AlgorithmnEdges are initially sorted by increasing weightnStart with an empty forest F0n“grow”MST one edge at a time
28、through a series of expanding forests F1,F2,Fn-1nintermediate stages usually have forest of trees(not connected)nat each stage add minimum weight edge among those not yet used that does not create a cycle nneed efficient way of detecting/avoiding cyclesnalgorithm stops when all vertices are included
29、Correctness of KruskalnSimilar to the proof of PrimnProve by induction on the construction process actually generate a MSTnConsider F0,F1,Fn-1Basic Kruskals AlgorithmALGORITHM Kruscal(G)/Input:A weighted connected graph G =/Output:ET,the set of edges composing a minimum spanning tree of G.Sort E in
30、nondecreasing order of the edge weights w(ei1)=w(ei|E|)ET ;ecounter 0/initialize the set of tree edges and its sizek 0 while encounter w(e),which also indicates that the weight of e is greater than that of any edges in T.Removing e from T disconnects T into two subtrees T1 and T2,there must exist an edge f in T connecting T1 and T2,otherwise,T is not connected.T1T2 f forms a new tree T with w(T)=w(T)-w(e)+w(f)w(T),A contradiction to the fact that T is MST,thus,A MST is also a BST.
