Dünaamiline planeerimine/programmeerimine lihtsaks tehtud

Dünaamilise programmeerimise algoritmid on enamus suhteliselt keerulised algajale ja neist arusaamine võib võtta üsna kaua aega. Kui võtta ette tuimalt LCS algoritm ja proovida sellest midagi aru saada, siis on üsna kahtlane, kas saad ikka aru või mitte.

DP on tegelikult suur mõiste ja neid algoritme on tõesti palju erineva keerukusega. Vahest on lihtsalt väga raske jõuda mingi “algse” algoritmi juurde, mille põhjal need keerulisemad on ehitatud.

Üks selline algoritm õppimiseks on Manhattan Tourist Problem, mis on üllatavalt hea sissejuhatuslik ülesanne. Probleemi sisu on leida pikim tee maatriksis(tegelikult ka graaf), millel on lisaks “kaalud”, e. weighted matrix. “Turistid” võivad liikuda ainult lõuna ja ida suunas. Teekond algab [0,0], ja lõppeb[n,m] positsioonil.  See on palju lihtsam lahendada kui keerukamad lüheima tee jms. algoritmid, kuid põhimõte on sama.

Hea pilt probleemi visualiseerimiseks on siin http://southernblot.blogspot.com.ee/2014/03/manhattan-tourist-problem.html , kus tuleb vasakult ülevalt alla paremale jõuda liikudes ainult paremale ja alla. Kusjuures leida tuleb pikim tee.

Põhimõte on nagu paljudel DP algoritmidel lahendada “üldisem” probleem e. leida pikim tee algpunktist suvalise teise punktini. Ehk lahendada probleem, mis esialgu tundub keerulisem – leida teed kõikidesse punktidesse.

Leida algpunkist a a[0,j] (0<=j<=m) tähendab, et turist saab liikuda ainult itta, seega need väärtused ja a[i,0] (0<=i<n) on samuti lihtsalt leitavad. Edasi saab arvutada a[1,1] olemasolevate andmete järgi, sest esimene rida ja esimene veerg on leitud. a[1,1] saab jõuda ainult kahte moodi ja on samuti lihtne arvutada. Edasi a[2,1] ja a[3,1] jne. sama loogikaga. Näiteks a[1,2] =

max(a[1,1] + “kaal” [1,1] ja [1,2] vahel, a[0,2] + “kaal” [0,2] ja [1,2] vahel).

Ma ei tea, kas mu seletusvõime on piisav, aga soovitan soojalt uurida seda probleemi enne kui midagi keerulisemat ette võtta. Edasi võib lahendada graafi versioone sellest algoritmist. DP massiive on võimalik täita mitut erinevat moodi, zig-zag, rida realt jne. aga põhimõte jääb ikka samaks.

Leidsin huvitava ülesande, kus tuleb LCS lahendada n log n ajaga. Kusjuures ei ole kunagi tõestatud, et sellist algoritmi ei saa olemas olla. Tegelikult üsna kerge leida see algoritm, kui antud ridades ükski täht(number või misiganes) ei kordu, seega täiesti teostatav. LCS erijuhte pidi veel olema SO järgi.

LCS on samaväärne näiteks ka suunatud graafil, mis läheb sourceist sinki(ing k) longest increasing subsequencei leidmisega. Mis on sarnane kõikvõimalike alignmentitega. Mis kõik on sarnased Manhattan Tourist probleemiga.

Hea eestikeelne link vikisse https://et.wikipedia.org/wiki/D%C3%BCnaamiline_programmeerimine

Advertisements