国外算法设计与分析课件14.ppt

1、GreedyAlgorithms(I),Greed,forlackofabetterword,isgood!Greedisright!Greedworks!-MichaelDouglas,U.S.actorintheroleofGordonGecko,inthefilmWallStreet,1987,Maintopics,IdeaofthegreedyapproachChange-makingproblemMinimumspanningtreeproblemPrimsalgorithmKruskalsalgorithmPropertiesofminimumspanningtree(additi

2、vepart)Bottleneckspanningtree(additivepart),ExpectedOutcomes,Studentshouldbeabletosummarizetheideaofthegreedytechniquelistseveralapplicationsofthegreedytechniqueapplythegreedytechniquetochange-makingproblemdefinetheminimumspanningtreeproblemdescribeideasofPrimandKruskalsalgorithmsforcomputingminimum

3、spanningtreeprovethecorrectnessofthetwoalgorithmsanalyzethetimecomplexitiesofthetwoalgorithmsunderdifferentdatastructuresprovethevariouspropertiesofminimumspanningtree,Glossary,Greedy:贪婪的Change-makingproblem:找零钱问题Cashier:收银员Denomination:货币单位，面额Quarter,dime,nickel,penny:2角5分，1角，5分，1分（美国硬币单位）Irrevocab

4、le：不可取消的，不可逆的Spanningtree:生成树，支撑树,AnticipatorySet:ChangeMakingProblem,Howtomake48centsofchangeusingcoinsofdenominationsof25(1quartercoin),10(1dimecoin),5(1nickelcoin),and1(1pennycoin)sothatthetotalnumberofcoinsisthesmallest?Theidea:Takethecoinwithlargestdenominationwithoutexceedingtheremainingamount

5、ofcents,makethelocallybestchoiceateachstep.Isthesolutionoptimal?Yes,theproofisleftasexercise.,GeneralChange-MakingProblem,Givenunlimitedamountsofcoinsofdenominationsd1dm,givechangeforamountnwiththeleastnumberofcoins.Doesthegreedyalgorithmalwaysgiveanoptimalsolutionforthegeneralchange-makingproblem?W

6、egivethefollowingexample,Example:d1=7c,d2=5c,d3=1c,andn=10c,notalwaysproducesanoptimalsolution.infact,forsomeinstances,theproblemmaynothaveasolutionatall!considerinstanced1=7c,d2=5c,d3=3c,andn=11c.But,thisproblemcanbesolvedbydynamicprogramming,pleasetrytodesignanalgorithmforthegeneralchange-makingpr

7、oblemafterclass.,GreedyAlgorithms,Agreedyalgorithmmakesalocallyoptimalchoicestepbystepinthehopethatthischoicewillleadtoagloballyoptimalsolution.Thechoicemadeateachstepmustbe:FeasibleSatisfytheproblemsconstraintslocallyoptimalBethebestlocalchoiceamongallfeasiblechoicesIrrevocableOncemade,thechoicecan

8、tbechangedonsubsequentsteps.Dogreedyalgorithmsalwaysyieldoptimalsolutions?Example:changemakingproblemwithadenominationsetof7,5and1,andn=10?,ApplicationsoftheGreedyStrategy,Optimalsolutions:someinstancesofchangemakingMinimumSpanningTree(MST)Single-sourceshortestpathsHuffmancodesApproximations:Traveli

9、ngSalesmanProblem(TSP)Knapsackproblemotheroptimizationproblems,Forsomeproblems,yieldsanoptimalsolutionforeveryinstance.Formost,doesnotbutcanbeusefulforfastapproximations.,MinimumSpanningTree(MST),SpanningtreeofaconnectedgraphGisaconnectedacyclicsubgraph(tree)ofGthatincludesallofGsvertices.Note:aspan

10、ningtreewithnverticeshasexactlyn-1edges.MinimumSpanningTreeofaweighted,connectedgraphGisaspanningtreeofGofminimumtotalweight.Example:,MSTProblem,Givenaconnected,undirected,weightedgraphG=(V,E),findaminimumspanningtreeforit.ComputeMSTthroughBruteForce?Kruskal:1956,Prim:1957,BruteforceGenerateallpossi

11、blespanningtreesforthegivengraph.Findtheonewithminimumtotalweight.FeasibilityofBruteforcePossibletoomanytrees(exponentialfordensegraphs),ThePrimsAlgorithm,IdeaofthePrimsalgorithmPseudo-codeofthealgorithmCorrectnessofthealgorithm(important)Timecomplexityofthealgorithm,IdeaofPrim,Growasingletreebyrepe

12、atedlyaddingtheleastcostedge(greedystep)thatconnectsavertexintheexistingtreetoavertexnotintheexistingtreeIntermediatesolutionisalwaysasubtreeofsomeminimumspanningtree.,PrimsMSTalgorithm,Startwithatree,T0,consistingofonevertex“Grow”treeonevertex/edgeatatimeConstructaseriesofexpandingsubtreesT1,T2,Tn-

13、1.AteachstageconstructTifromTi-1byaddingtheminimumweightedgethatconnectingavertexintree(Ti-1)toavertexnotyetinthetreethisisthe“greedy”step!Algorithmstopswhenallverticesareincluded,PseudocodeofthePrim,ALGORITHMPrim(G)/Primsalgorithmforconstructingaminimumspanningtree/Input:AweightedconnectedgraphG=(V

14、,E)/Output:ET,thesetofedgescomposingaminimumspanningtreeofGVTv0/v0canbearbitrarilyselectedETfori1to|V|-1dofindaminimum-weightedgee*=(v*,u*)amongalltheedges(v,u)suchthatvisinVTanduisinV-VTVTVTu*ETETe*returnET,Anexample,ThePrimsalgorithmisgreedy!,Thechoiceofedgesaddedtocurrentsubtreesatisfyingthethree

15、propertiesofgreedyalgorithms.Feasible,eachedgeaddedtothetreedoesnotresultinacycle,guaranteethatthefinalETisaspanningtreeLocaloptimal,eachedgeselectedtothetreeisalwaystheonewithminimumweightamongalltheedgescrossingVTandV-VTIrrevocable,onceanedgeisaddedtothetree,itisnotremovedinsubsequentsteps.,Correc

16、tnessofPrim,ProvebyinductionthatthisconstructionprocessactuallyyieldsMST.T0isasubsetofallMSTsSupposethatTi-1isasubsetofsomeMSTT,weshouldprovethatTiwhichisgeneratedfromTi-1isalsoasubsetofsomeMST.Bycontradiction,assumethatTidoesnotbelongtoanyMST.Letei=(u,v)betheminimumweightedgefromavertexinTi-1toaver

17、texnotinTi-1usedbyPrimsalgorithmtoexpandingTi-1toTi,accordingtoourassumption,eicannotbelongtoMSTT.AddingeitoTresultsinacyclecontaininganotheredgee=(u,v)connectingavertexuinTi-1toavertexvnotinit,andw(e)w(ei)accordingtothegreedyPrimsalgorithm.RemovingefromTandaddingeitoTresultsinanotherspanningtreeTwi

18、thweightw(T)w(T),indicatingthatTisaminimumspanningtreeincludingTiwhichcontradicttoassumptionthatTidoesnotbelongtoanyMST.,CorrectnessofPrim,ImplementationofPrim,HowtoimplementthestepsinthePrimsalgorithm?Firstidea,labeleachvertexwitheither0or1,1representsthevertexinVT,and0otherwise.Traversetheedgesett

19、ofindanminimumweightedgewhoseendpointshavedifferentlabels.Timecomplexity:O(VE)ifadjacencylinkedlistandO(V3)foradjacencymatrixForsparsegraphs,useadjacencylinkedlistAnyimprovement?,Notations,T:theexpandingsubtree.Q:theremainingvertices.Ateachstage,thekeypointofexpandingthecurrentsubtreeTistoDeterminew

20、hichvertexinQisthenearestvertextoT.Qcanbethoughtofasapriorityqueue:Thekey(priority)ofeachvertex,keyv,meanstheminimumweightedgefromvtoavertexinT.KeyvisifvisnotlinkedtoanyvertexinT.Themajoroperationistotofindanddeletethenearestvertex(v,forwhichkeyvisthesmallestamongallthevertices)Removethenearestverte

21、xvfromQandadditandthecorrespondingedgetoT.Withtheoccurrenceofthataction,thekeyofvsneighborswillbechanged.,ToremembertheedgesoftheMST,anarrayisintroducedtorecordtheparentofeachvertex.ThatisvisthevertexintheexpandingsubtreeTthatisclosesttovnotinT.,AdvancedPrimsAlgorithm,ALGORITHMMST-PRIM(G,w,r)/w:weig

22、ht;r:root,thestartingvertexforeachuVGdokeyuuNIL/u:theparentofukeyr0QVG/Nowthepriorityqueue,Q,hasbeenbuilt.whileQdouExtract-Min(Q)/removethenearestvertexfromQforeachvAdju/updatethekeyforeachofvsadjacentnodes.doifvQandw(u,v)keyvthenvukeyvw(u,v),TimeComplexityofPrimsalgorithm,Needpriorityqueueforlocati

23、ngthenearestvertexUseunorderedarraytostorethepriorityqueue:Efficiency:(n2)Usebinarymin-heaptostorethepriorityqueueEfficiency:Forgraphwithnverticesandmedges:O(mlogn)UseFibonacci-heaptostorethepriorityqueue:Efficiency:Forgraphwithnverticesandmedges:O(nlogn+m),KruskalsMSTAlgorithm,EdgesareinitiallysortedbyincreasingweightStartwithanemptyforestF0“grow”MSToneedgeatatimethroughaseriesofexpandingforestsF1,F2,Fn-1intermediatestagesusuallyhaveforestoftrees(notconnected)ateachstageaddminimumweightedgeamo