Dynamic programming - People

1 Chapter6 DynamicprogrammingIntheprecedingchapters wehaveseensomeelegantdesignprinciples such asdivide-and-conquer, graphexploration,andgreedychoice thatyieldde nitivealgorithmsfora varietyofimportantcomputationaltasks. Thedrawback ofthesetoolsis thattheycanonlybeusedonveryspeci ctypesofproblems. We nowturntothetwosledgehammersofthealgorit hmscraft,dynamicprogrammingandlinearprog ramming, techniquesof , thisgeneralityoftencomeswitha costinef ,revisitedAttheconclusionofourstudyofsho rtestpaths(Chapter4),weobservedthatthepr oblemisespeciallyeasyindirectedacyclicgr aphs(dags).

2 Let's recapitulatethiscase, becauseit liesattheheartof a dagis thatitsnodescanbelinearized; thatis, theycanbearrangedona linesothatalledgesgofromlefttoright( ).To seewhythishelpswithshortestpaths, supposewewantto gureoutdistancesfromnodeStotheothernodes . Forconcreteness, let's focusonnodeD. Theonlyway togettoit is daganditslinearization(topologicalorderi ng).BDCASE12416312 SCABDE46312112169170 Algorithmspredecessors,BorC; soto ndtheshortestpathtoD, weneedonlycomparethesetworoutes:dist(D) = minfdist(B) + 1;dist(C) + 3g:Asimilarrelationcanbewrittenforeveryn ode.

3 ,wecanalwaysbesurethatbythetimewegettoa nodev,wealreadyhavealltheinformationwene edtocomputedist(v). We arethereforeabletocomputealldistancesina singlepass:initializeall dist( )valuesto1dist(s) = 0for eachv2 Vnfsg, in linearizedorder:dist(v) = min(u;v)2 Efdist(u) +l(u;v)gNoticethatthisalgorithmissolving a collectionofsubproblems,fdist(u) :u2Vg. Westartwiththesmallestofthem,dist(s), sinceweimmediatelyknowitsanswertobe0. Wethenproceedwithprogressively larger subproblems distancestoverticesthatarefurtherandfurt heralonginthelinearization wherewearethinkingof a subproblemaslargeif weneedtohavesolveda lotof verygeneraltechnique.

4 Ateach node, wecomputesomefunctionofthevaluesofthenod e's predecessors. It sohappensthatourparticularfunctionis a minimumofsums,butwecouldjustaswellmakeit amaximum, inwhich casewewouldgetlongestpathsinthedag. Orwecouldusea productinsteadofa suminsidethebrackets, inwhich casewewouldendupcomputingthepathwiththes mallestproductof verypowerfulalgorithmicparadigminwhich a problemissolvedbyidentifyinga collectionof subproblemsandtacklingthemonebyone, smallest rst,usingtheanswerstosmallproblemstohelp gureoutlargerones, untilthewholelotof themis dag;thedagisimplicit.

5 Itsnodesarethesubproblemswede ne, anditsedgesarethedependenciesbetweenthes ubproblems:iftosolvesubproblemBweneedthe answertosubproblemA, thenthereis a (conceptual)edgefromAtoB. Inthiscase,Ais thoughtof asa smallersubproblemthanB andit willalwaysbesmaller, 's timewesaw ,theinputis a sequenceofnumbersa1;:::; anysubsetof thesenumberstakeninorder, of theformai1;ai2;:::;aikwhere1 i1< i2< < ik n, andanincreasingsubsequenceis oneinwhich thenumbersaregettingstrictlylarger. Thetaskis to , thelongestincreasingsubsequenceof5;2;8;6 ;3;6;9;7is2;3;6;9:52863697S. Dasgupta, , , , tobetterunderstandthesolutionspace, let's createa graphofallpermissibletransitions:establi sha nodeiforeach elementai, andadddirectededges(i;j)wheneverit is possibleforaiandajtobeconsecutiveelement sinanincreasingsubsequence,thatis, wheneveri < jandai< aj( ).

6 Noticethat(1)thisgraphG= (V;E)isa dag, sincealledges(i;j)havei < j, and(2)thereis a , ourgoalis simplyto ndthelongestpathinthedag!Hereis thealgorithm:forj= 1;2;::: ;n:L(j) = 1 + maxfL(i) : (i;j)2 EgreturnmaxjL(j)L(j)is thelengthofthelongestpath thelongestincreasingsubsequence endingatj(plus1, sincestrictlyspeakingweneedtocountnodeso nthepath,notedges).Byreasoninginthesamew ay aswedidforshortestpaths, weseethatanypathtonodejmustpassthroughon eof itspredecessors, andthereforeL(j)is1plusthemaximumL( )valueof therearenoedgesintoj, wetakethemaximumovertheemptyset,zero.

7 Andthe nalansweris thelargestL(j), sinceanyendingpositionis dynamicprogramming. Inordertosolveouroriginalproblem,wehaved e nedacollectionofsubproblemsfL(j) : 1 j ngwiththefollowingkeypropertythatallowst hemtobesolvedina singlepass:(*)Thereis anorderingonthesubproblems, anda relationthatshowshowtosolvea subproblemgiventheanswersto smaller subproblems, thatis, , each subproblemis solvedusingtherelationL(j) = 1 + maxfL(i) : (i;j)2Eg;172 Algorithmsanexpressionwhich involvesonlysmallersubproblems. Howlongdoesthissteptake?Itrequiresthepre decessorsofjtobeknown;forthistheadjacenc ylistof thereversegraphGR,constructibleinlineart ime( ),is handy.

8 ThecomputationofL(j)thentakestimeproport ionaltotheindegreeofj, givinganoverallrunningtimelinearinjEj. Thisis atmostO(n2), themaximumbeingwhentheinputarray is sortedinincreasingorder. Thusthedynamicprogrammingsolutionis bothsimpleandef onelastissuetobeclearedup:theL-valuesonl ytellusthelengthoftheoptimalsubsequence, sohowdowerecoverthesubsequenceitself?Thi sis (j), weshouldalsonotedownprev(j), thenext-to-lastnodeonthelongestpathtoj. Dasgupta, , Vazirani173 Recursion?No, :theformulaforL(j)alsosuggestsanalternat ive, 'tthatbeevensimpler?Actually, recursionis a verybadidea:theresultingprocedurewouldre quireexponentialtime!

9 To seewhy, supposethatthedagcontainsedges(i;j)foral li < j thatis, thegivensequenceofnumbersa1;a2;:::; , theformulaforsubproblemL(j)becomesL(j) = 1 + maxfL(1);L(2);::: ;L(j 1)g:Thefollowing gureunravelstherecursionforL(5). Noticethatthesamesubproblemsgetsolvedove randoveragain!L(2)L(1)L(1)L(2)L(1)L(2)L( 1)L(1)L(1)L(2)L(1)L(3)L(1)L(3)L(4)L(5)Fo rL(n)thistreehasexponentiallymanynodes(c anyouboundit?),andsoa recursivesolutionis thatindivide-and-conquer, a problemis expressedintermsofsubproblemsthataresubs tantiallysmaller, say halfthesize. Forinstance,mergesortsortsanarray ofsizenbyrecursivelysortingtwosubarrayso fsizen= , thefullrecursiontreehasonlylogarithmicde pthanda polynomialnumberof ,ina typicaldynamicprogrammingformulation,a problemisreducedtosubproblemsthatareonly slightlysmaller forinstance,L(j)reliesonL(j 1).

10 , it turnsoutthatmostofthesenodesarerepeats, ciencyis Itwas rstcoinedbyRichardBellmaninthe1950s, a timewhencomputerprogrammingwasanesoteric activitypracticedbysofewpeopleastonoteve nmerita name. Back thenprogrammingmeant planning, and dynamicprogramming wasconceivedtooptimallyplanmultistagepro cesses. Thedagof asdescribingthepossiblewaysinwhich such a processcanevolve:each nodedenotesa state, theleftmostnodeis thestartingpoint,andtheedgesleavinga staterepresentpossibleactions, leadingtodifferentstatesinthenextunitof , thesubjectof Chapter7, is spellcheckerencountersa possiblemisspelling, it looksinitsdictionaryforotherwordsthatare closeby.