资源描述：
《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}accordingtotheirbenefit-costratio:picking3,forexample,increasesthesizeofthesetby1(benefit)whileincreasingthesumby3(cost),sowewouldassignitabenefit-c
4、ostratioof1.Choosingelementsaccordingtothisschemegivestheset3{1,3,7,9}.IKruskal’sminimumspanningtreealgorithmisanotherexampleofagreedyalgorithm:ateachstepitchoosestheedgewithminimumcost,withoutthinkingaheadastohowthatmightaffectfuturedecisions.GreedyalgorithmsIIIGreedyalgorithmsonlyrarelygiveopti
5、malanswers.Surprisinglyoftentheygive“reasonably-good”answers;forexample,greedyalgorithmsareonemethodofobtainingapproximatesolutionstoNP-hardoptimizationproblems.IThereisagreedyalgorithmforconstructingaprefix-freecodethatyieldsanoptimalcode,calledaHuffmancode.IRecallthattheentropyofadiscretedistrib
6、utiononasetofsymbolsSisgivenbyXH(µ)=−µ(si)logµ(si)s∈SAnd,fromShannon’snoiselesscodingtheorem,weknowthereexistsaprefixcodeachievinganaveragecodelengthofc≤H(µ)+1.IHuffman’salgorithmusesagreedymethodtoconstructanoptimalcode:GreedyalgorithmsIII1.Startwithacollectionofsingletontrees,oneforeachsymbol.Fo
7、reachtreewekeeptrackofitsprobability;initiallyeachsingletontreehastheprobabilityofitssymbol.2.Whilethereismorethanonetree,2.1Choosetwotreeswithleastprobabilities;2.2Combinethetwotreesintoonebymakinganewrootwhoseleftchildison
