算法设计与分析双语课chapter 5 -1gready algorithm

《算法设计与分析双语课chapter 5 -1gready algorithm》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析NorthChinaElectricPowerUniversityAlgorithmsDesign&Analysis华北电力大学计算机科学与技术学院SchoolofComputerScience&TechnologyofNorthChinaElectricPowerUniversityNorthChinaElectricPowerUniversityChapter5GreedyAlgorithm1.Introduction2.Fractionalknapsackproblem3.Theshortestpathproblem4.Minimumspanningtreesprobl

2、em5.找钱问题6.汽车加油问题7.Anactivity-selectionproblemNorthChinaElectricPowerUniversity§1IntroductionTypically,inoptimizationproblemsthealgorithmneedstomakeaseriesofchoiceswhoseoveralleffectistominimizethetotalcost,ormaximizethetotalbenefit,ofsomesystem.Thegreedymethodconsistsofmakingthechoicesinsequencesu

3、chthateachindividualchoiceisbestaccordingtosomelimited“short-term”criterionthatisnottooexpensivetoevaluate.Onceachoiceismade,itcan’tbeundown,evenifitbecomesevidentlaterthatitwasapoorchoice.Forthisreason,greedyalgorithmdon’tnecessarilyfindtheexactoptimumsolutionformanyproblems.Unlikedynamicprogramm

4、ingalgorithms,greedyalgorithmstypicallyconsistofaniterativeprocedurethattriestofindalocaloptimalsolution.Agreedyalgorithmmakesacorrectguessonthebasisoflittlecalculationwithoutworryingaboutthefuture.Thusitbuildsasolutionstepbystep.Eachstepincreasesthesizeofthepartialsolutionandisbasedonlocaloptimiz

5、ation.Thechoicemadeisthatwhichproducesthelargestimmediategainwhilemaintainingfeasibility.NorthChinaElectricPowerUniversitySinceeachstepconsistsoflittleworkbasedonasmallamountofinformation,theresultingalgorithmsaretypicallyefficient.Thehardpartinthedesignofagreedyalgorithmisprovingthatthealgorithmd

6、oesindeedsolvetheproblemitisdesignedfor.Thisiscontrastedwithrecursivealgorithmsthathavesimpleinductiveproofs.Howcanonetellifagreedyalgorithmwillsolveaparticularoptimizationproblem?Thereisnowayingeneral.Ifwecandemonstratethefollowingproperties,thenitisprobabletousegreedyalgorithm:Whengreedyalgorith

7、mworks?NorthChinaElectricPowerUniversity1.Greedy-choiceProperty2.OptimalSubstructure(thesamewiththatofdynamicprogramming)propertyGreedychoicepropertyAglobaloptimalsolutioncanbearrivedatbymakingalocallyoptimalgree