资源描述：
《Dynamic programming》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、Chapter6DynamicprogrammingIntheprecedingchapterswehaveseensomeelegantdesignprinciples—suchasdivide-and-conquer,graphexploration,andgreedychoice—thatyielddenitivealgorithmsforavarietyofimportantcomputationaltasks.Thedrawbackofthesetoolsisthattheycanonlybeusedonverysp
2、ecictypesofproblems.Wenowturntothetwosledgehammersofthealgorithmscraft,dynamicprogrammingandlinearprogramming,techniquesofverybroadapplicabilitythatcanbeinvokedwhenmorespecializedmethodsfail.Predictably,thisgeneralityoftencomeswithacostinefciency.6.1Shortestpathsin
3、dags,revisitedAttheconclusionofourstudyofshortestpaths(Chapter4),weobservedthattheproblemisespeciallyeasyindirectedacyclicgraphs(dags).Let'srecapitulatethiscase,becauseitliesattheheartofdynamicprogramming.Thespecialdistinguishingfeatureofadagisthatitsnodescanbelinear
4、ized;thatis,theycanbearrangedonalinesothatalledgesgofromlefttoright(Figure6.1).Toseewhythishelpswithshortestpaths,supposewewanttogureoutdistancesfromnodeStotheothernodes.Forconcreteness,let'sfocusonnodeD.TheonlywaytogettoitisthroughitsFigure6.1Adaganditslinearizatio
5、n(topologicalordering).63AB1224611S41ESCABDE23112CD169170Algorithmspredecessors,BorC;sotondtheshortestpathtoD,weneedonlycomparethesetworoutes:dist(D)=minfdist(B)+1;dist(C)+3g:Asimilarrelationcanbewrittenforeverynode.Ifwecomputethesedistvaluesintheleft-to-rightordero
6、fFigure6.1,wecanalwaysbesurethatbythetimewegettoanodev,wealreadyhavealltheinformationweneedtocomputedist(v).Wearethereforeabletocomputealldistancesinasinglepass:initializealldist()valuesto1dist(s)=0foreachv2Vnfsg,inlinearizedorder:dist(v)=min(u;v)2Efdist(u)+l(u;v)gN
7、oticethatthisalgorithmissolvingacollectionofsubproblems,fdist(u):u2Vg.Westartwiththesmallestofthem,dist(s),sinceweimmediatelyknowitsanswertobe0.Wethenproceedwithprogressively“larger”subproblems—distancestoverticesthatarefurtherandfurtheralonginthelinearization—wherew
8、earethinkingofasubproblemaslargeifweneedtohavesolvedalotofothersubproblemsbeforewecangettoit.Thisisaverygeneraltechnique.Ateachnode
