资源描述：
《国外算法设计与分析课件14.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、GreedyAlgorithms(I)Greed,forlackofabetterword,isgood!Greedisright!Greedworks!-MichaelDouglas,U.S.actorintheroleofGordonGecko,inthefilmWallStreet,1987MaintopicsIdeaofthegreedyapproachChange-makingproblemMinimumspanningtreeproblemPrim’salgorithmKruskal’salgorithmPropertiesofminimumspanningtree(addi
2、tivepart)Bottleneckspanningtree(additivepart)ExpectedOutcomesStudentshouldbeabletosummarizetheideaofthegreedytechniquelistseveralapplicationsofthegreedytechniqueapplythegreedytechniquetochange-makingproblemdefinetheminimumspanningtreeproblemdescribeideasofPrimandKruskal’salgorithmsforcomputingmin
3、imumspanningtreeprovethecorrectnessofthetwoalgorithmsanalyzethetimecomplexitiesofthetwoalgorithmsunderdifferentdatastructuresprovethevariouspropertiesofminimumspanningtreeGlossaryGreedy:贪婪的Change-makingproblem:找零钱问题Cashier:收银员Denomination:货币单位，面额Quarter,dime,nickel,penny:2角5分，1角，5分，1分（美国硬币单位）Irre
4、vocable：不可取消的，不可逆的Spanningtree:生成树，支撑树AnticipatorySet: ChangeMakingProblemHowtomake48centsofchangeusingcoinsofdenominationsof25(1quartercoin),10(1dimecoin),5(1nickelcoin),and1(1pennycoin)sothatthetotalnumberofcoinsisthesmallest?Theidea:Takethecoinwithlargestdenominationwithoutexceedingtheremainin
5、gamountofcents,makethelocallybestchoiceateachstep.Isthesolutionoptimal?Yes,theproofisleftasexercise.GeneralChange-MakingProblemGivenunlimitedamountsofcoinsofdenominationsd1>…>dm,givechangeforamountnwiththeleastnumberofcoins.Doesthegreedyalgorithmalwaysgiveanoptimalsolutionforthegeneralchange-maki
6、ngproblem?Wegivethefollowingexample,Example:d1=7c,d2=5c,d3=1c,andn=10c,notalwaysproducesanoptimalsolution.infact,forsomeinstances,theproblemmaynothaveasolutionatall!considerinstanced1=7c,d2=5c,d3=3c,andn=11c.But,thisproblemcanbesolvedbydynamicprogramming,pleasetrytodesignanalgorithmforthegeneralc
7、hange-makingproblemafterclass.GreedyAlgorithmsAgreedyalgorithmmakesalocallyoptimalchoicestepbystepinthehopethatthischoicewillleadtoagloballyoptimalsolution.Thechoicemadeateachstepmustbe:FeasibleSatisfytheproblem’sconst
