資源描述：
《Greedy Algorithms and Dynamic Programming》由會員上傳分享，免費在線閱讀，更多相關內容在學術論文-天天文庫。
1、ECE750-TXBLecture19:GreedyAlgorithmsandDynamicProgrammingToddL.Veldhuizentveldhui@acm.orgElectrical&ComputerEngineeringUniversityofWaterlooCanadaMarch15,2007Multi-stageDecisionProblemsIIAmulti-stagedecisionproblemisonewherewecanthinkoftheproblemashavingatreestructure:eachtreenoderepresentsadecis
2、ionpoint,andeachdecisionleadsustoanotherdecisiontobemade.IForexample:chooseasmanyelementsoftheset{1,3,7,9,13}aspossiblewithoutexceeeding21.Wecanviewthisasatree:{}{1}{3}{7}{9}{13}{1,3}{1,7}{1,9}{1,13}Herewehavedecidedtoinclude1intheset,whichopensupafurthersetofchoices.GreedyalgorithmsIIAgreedyalg
3、orithmalwayschoosesthemostattractiveoptionavailabletoit:eachdecisionismadebasedonitsimmediatereward.IForexample,wemightpickelementsoftheset{1,3,7,9,13}accordingtotheirbene?t-costratio:picking3,forexample,increasesthesizeofthesetby1(bene?t)whileincreasingthesumby3(cost),sowewouldassignitabene?t-c
4、ostratioof1.Choosingelementsaccordingtothisschemegivestheset3{1,3,7,9}.IKruskal’sminimumspanningtreealgorithmisanotherexampleofagreedyalgorithm:ateachstepitchoosestheedgewithminimumcost,withoutthinkingaheadastohowthatmighta?ectfuturedecisions.GreedyalgorithmsIIIGreedyalgorithmsonlyrarelygiveopti
5、malanswers.Surprisinglyoftentheygive“reasonably-good”answers;forexample,greedyalgorithmsareonemethodofobtainingapproximatesolutionstoNP-hardoptimizationproblems.IThereisagreedyalgorithmforconstructingapre?x-freecodethatyieldsanoptimalcode,calledaHu?mancode.IRecallthattheentropyofadiscretedistrib
6、utiononasetofsymbolsSisgivenbyXH(μ)=?μ(si)logμ(si)s∈SAnd,fromShannon’snoiselesscodingtheorem,weknowthereexistsapre?xcodeachievinganaveragecodelengthofc≤H(μ)+1.IHu?man’salgorithmusesagreedymethodtoconstructanoptimalcode:GreedyalgorithmsIII1.Startwithacollectionofsingletontrees,oneforeachsymbol.Fo
7、reachtreewekeeptrackofitsprobability;initiallyeachsingletontreehastheprobabilityofitssymbol.2.Whilethereismorethanonetree,2.1Choosetwotreeswithleastprobabilities;2.2Combinethetwotreesintoonebymakinganewrootwhoseleftchildison
