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( ).To seewhythishelpswithshortestpaths, supposewewantto gureoutdistancesfromnodeStotheothernodes . Forconcreteness, let's focusonnodeD. Theonlyway togettoit is daganditslinearization(topologicalorderi ng).

2 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. Westartwiththesmallestofthem,dist(s), sinceweimmediatelyknowitsanswertobe0. Wethenproceedwithprogressively larger subproblems distancestoverticesthatarefurtherandfurt heralonginthelinearization wherewearethinkingof a subproblemaslargeif weneedtohavesolveda lotof verygeneraltechnique. Ateach node, wecomputesomefunctionofthevaluesofthenod e's predecessors.

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

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

5 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. ThecomputationofL(j)thentakestimeproport ionaltotheindegreeofj, givinganoverallrunningtimelinearinjEj. Thisis atmostO(n2), themaximumbeingwhentheinputarray is sortedinincreasingorder. Thusthedynamicprogrammingsolutionis bothsimpleandef onelastissuetobeclearedup:theL-valuesonl ytellusthelengthoftheoptimalsubsequence, sohowdowerecoverthesubsequenceitself?

6 Thisis (j), weshouldalsonotedownprev(j), thenext-to-lastnodeonthelongestpathtoj. Dasgupta, , Vazirani173 Recursion?No, :theformulaforL(j)alsosuggestsanalternat ive, 'tthatbeevensimpler?Actually, recursionis a verybadidea:theresultingprocedurewouldre quireexponentialtime!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).

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

8 Thecostofanalignmentis thenumberof columnsinwhich thelettersdiffer. costof 3?Editdistanceissonamedbecauseit canalsobethoughtofastheminimumnumberofed its insertions, deletions, andsubstitutionsofcharacters neededtotransformthe , thealignmentshownontheleftcorrespondstot hreeedits:insertU, substituteO!N, ,therearesomanypossiblealignmentsbetween twostringsthatit wouldbeterriblyinef cienttosearch throughallof themforthebestone. 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]?

9 CallthissubproblemE(i;j)( ).Our nalobjective,then,is tocomputeE(m;n).Forthistowork,weneedtoso mehowexpressE(i;j) 's see whatdoweknowaboutthebestalignmentbetween x[1 i]andy[1 j]? Well,itsrightmostcolumncanonlybeoneof threethings:x[i] or y[j]orx[i]y[j]The rstcaseincursa costof1forthisparticularcolumn,andit remainstoalignx[1 i 1]withy[1 j]. Butthisis exactlythesubproblemE(i 1;j)! We , alsowithcost1, westillneedtoalignx[1 i]withy[1 j 1]. Thisisagainanothersubproblem,E(i;j 1). Andinthe nalcase, which eithercosts1(ifx[i]6=y[j])or0(ifx[i] =y[j]), what's leftis thesubproblemE(i 1;j 1). Inshort,wehaveexpressedE(i;j)intermsof threesmallersubproblemsE(i 1;j),E(i;j 1),E(i 1;j 1). We havenoideawhich of themis therightone, soweneedtotrythemallandpick thebest:E(i;j) =minf1 +E(i 1;j);1 +E(i;j 1);diff(i;j) +E(i 1;j 1)gwhereforconveniencediff(i;j)is de nedtobe0ifx[i] =y[j] , incomputingtheeditdistancebetweenEXPONEN TIALandPOLYNOMIAL,subproblemE(4;3)corres pondstothepre xesEXPOandPOL.

10 Therightmostcolumnoftheirbestalignmentmu stbeoneof thefollowing:O or LorOLThus,E(4;3) = minf1 +E(3;3);1 +E(4;2);1 +E(3;2) (i;j)forma two-dimensionaltable, ne, aslongasE(i 1;j),E(i;j 1), andE(i 1;j 1)arehandledbeforeE(i;j). Forinstance, wecould llinthetableonerowata time, fromtoprowtobottomrow, andmovinglefttorightacrosseach row. Oralternatively, wecould llit particulartableentry, alltheotherentriesweneedarealready (a)Thetableof subproblems. EntriesE(i 1;j 1),E(i 1;j), andE(i;j 1)areneededto llinE(i;j). (b)The naltableof valuesfoundbydynamicprogramming.(a)ij 1ji 1mGOALn(b)POLYNOMIAL012345678910E1123456 78910X222345678910P323345678910O43234556 789N54334456789E65444556789N76555456789T 87666556789I98777666678A109888777767L111 0989888876 Withboththesubproblemsandtheorderingspec i ed,wearealmostdone. Therejustremainthe basecases ofthedynamicprogramming, theverysmallestsubproblems. Inthepresentsituation,theseareE(0; )andE( ;0), bothofwhich (0;j)is theeditdistancebetweenthe0-lengthpre xofx, namelytheemptystring, andthe rstjlettersofy: clearly,j.