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).Let's recapitulatethiscase, becauseit liesattheheartof a dagis thatitsnodescanbelinearized; thatis, theycanbearrangedona linesothatalledgesgofromlefttoright( ).

2 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. ,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.

3 Westartwiththesmallestofthem,dist(s), sinceweimmediatelyknowitsanswertobe0. Wethenproceedwithprogressively larger subproblems distancestoverticesthatarefurtherandfurt heralonginthelinearization wherewearethinkingof a subproblemaslargeif weneedtohavesolveda lotof verygeneraltechnique. 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.

4 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( ).

5 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. 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.

6 Howlongdoesthissteptake?Itrequiresthepre decessorsofjtobeknown;forthistheadjacenc ylistof thereversegraphGR,constructibleinlineart ime( ),is handy. 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!

7 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).

8 , 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. Whatis theappropriatenotionof closenessinthiscase?

9 A naturalmeasureofthedistancebetweentwostr ingsis theextenttowhich theycanbealigned, ormatchedup. Technically, analignmentis simplya way ofwritingthestringsoneabovetheother. Forinstance, herearetwopossiblealignmentsofSNOWYandSU NNY:S N O W YS U N N YCost:3 S N O W YS U N N YCost:5 The indicatesa gap ;anynumberofthesecanbeplacedineitherstri ng. Thecostofanalignmentis thenumberof columnsinwhich thelettersdiffer. costof 3?Editdistanceissonamedbecauseit canalsobethoughtofastheminimumnumberofed its insertions, deletions, andsubstitutionsofcharacters neededtotransformthe , thealignmentshownontheleftcorrespondstot hreeedits:insertU, substituteO!N, ,therearesomanypossiblealignmentsbetween twostringsthatit wouldbeterriblyinef cienttosearch throughallof themforthebestone.

10 DynamicprogrammingsolutionWhensolvinga problembydynamicprogramming, themostcrucialquestionis,Whatarethesubpr oblems?Aslongastheyarechosensoastohaveth eproperty(*) is aneasymattertowritedownthealgorithm:iter ativelysolveonesubproblemaftertheother, inorderof to ndtheeditdistancebetweentwostringsx[1 m]andy[1 n]. Whatis agoodsubproblem?Well,it shouldgopartof theway towardsolvingthewholeproblem;sohowS. Dasgupta, , (7;5).PLYNOMALIOPONNLAXEETI aboutlookingattheeditdistancebetweensome pre xofthe rststring,x[1 i], andsomepre xof thesecond,y[1 j]? CallthissubproblemE(i;j)( ).Our nalobjective,then,is tocomputeE(m;n).Forthistowork,weneedtoso mehowexpressE(i;j) 's see whatdoweknowaboutthebestalignmentbetween x[1 i]andy[1 j]?