Uvod u dinamičko programiranje
Uvod
Dinamičko programiranje je metoda optimizacije algoritama koja podrazumeva: raščlanjivanje glavnog problema na potprobleme koji se ponavljaju, i (potom) - računanje i pamćenje međurešenja.
Potproblemi se rešavaju jednom, a zapamćena međurešenja se mogu koristiti naknadno.
Ne mogu se, doduše, u svim problemima prepoznati potproblemi koji se ponavljaju, * ali, za probleme kod kojih to jeste moguće, u opštem smislu važi da imaju optimalnu podstrukturu (a sam proces zapisivanja izračunatih rešenja potproblema, naziva se memoizacija).
Upotrebom tehnika dinamičkog programiranja, znatno se smanjuje vremenska složenost algoritama (tipično, od eksponencijalne do polinomne), odnosno, u najpraktičnijem smislu: uz povećano memorijsko zauzeće, veoma primetno se smanjuje vreme izvršavanja programa.
Da bismo sve navedeno bolje razumeli, razmotrićemo jedan od najpoznatijih problema dinamičkog programiranja - problem pronalaženja najdužeg zajedničkog podniza (pri čemu ćemo prvo prikazati postupak rešavanja problema preko neefikasnog, "naivnog" algoritma, a potom ćemo demonstrirati prednosti upotrebe metoda dinamičkog programiranja).
Problem najdužeg zajedničkog podniza
Početni problem je sledeći: za dva niza, potrebno je pronaći dužinu najdužeg zajedničkog podniza i ispisati elemente koji čine takav podniz.
Ako za primer uzmemo dva niza celobrojnih vrednosti: a[] = { 4, 3, 1, 2, 1, 5, 8, 9 } i b[] = { 4, 7, 3, 2, 8, 1 } ....
.... letimičnim pregledom (u ovakvom jednostavnom primeru), nije teško uvideti da rešenje predstavlja bilo koji od sledeća dva podniza: { 4, 3, 2, 8 } ili { 4, 3, 2, 1 } .
Naravno, to smo lako uvideli pošto je uzorak koji posmatramo vrlo mali, i zato što (kao ljudi) imamo određenu sposobnost neposrednog sagledavanja "šire slike" na uzorcima "ne-baš-velikog" obima, međutim, računari takve sposobnosti nemaju uopšte (čak ni u slučaju izrazito malih nizova), a u slučaju većih nizova (pri čemu niz ne mora biti 'prevelik'; dovoljno je da se sastoji od svega nekoliko desetina elemenata), ljudi takođe moraju pribeći drugačijoj metodi sagledavanja, koja je (manje-više), ista onakva kakvu računari moraju koristiti u bilo kojim okolnostima.
Naivno rešenje
Za prethodno navedeni problem sa dva niza, naivno rešenje (pojam poznat od ranije), može se izvesti na sledeći način:
U prvom koraku, vrednost prvog elementa niza b (4), pretražuje se među elementima niza a ....
.... pri čemu se prvo poklapanje pojavljuje već na 1. poziciji.
Dužina najdužeg zajedničkog podniza (1), pamti se 'za kasnije', i potom se prelazi na sledeći element niza b.
U sledećem koraku, vrednost drugog (to jest, sledećeg) elementa niza b (7), traži se na pozicijama u nizu a koje slede posle pozicije na kojoj je pronađeno prvo poklapanje ....
.... međutim, u ovom slučaju element 7 ne nalazi se ni na jednoj poziciji u nizu a ....
Pretraga se usmerava na sledeći element niza b (3) ....
.... koji se poklapa sa 2. elementom niza a.
Pamti se nova najveća (pronađena) dužina najdužeg zajedničkog podniza (2) i potom se prelazi na sledeći element niza b (i naravno, sličan postupak se ponavlja, sve dok se ne pronađe podniz "najveće dužine") ....
Četvrti element niza b (2) ....
.... poklapa se sa 4. elementom niza a (dužina najdužeg zajedničkog podniza je 3).
Sledeći element niza b (8) ....
.... poklapa se sa 7. elementom niza a (dužina najdužeg zajedničkog podniza je 4).
Poslednji element niza b (1) ....
.... ne poklapa se ni sa jednim elementom niza a (koji sledi posle pozicije na kojoj je pronađeno poslednje poklapanje) ....
.... i stoga je najduži zajednički podniz ('za koji trenutno znamo') - podniz koji je pronađen u pretposlednjem koraku pretrage, a dužina podniza je 4:
Kratka analiza
Prikazani postupak ima nekoliko nedostatka.
Prvi (i najbitniji) nedostatak je sledeći: uvek postoji mogućnost da (prvi) podniz koji je pronađen - uopšte nije najduži zajednički podniz?!
Da li prvi pronađeni najduži podniz, jeste i najduži mogući - moguće je ustanoviti tek pošto se pronađu i ispitaju svi zajednički podnizovi (u sledećoj "etapi", "jednoj od mnogih", ponovo bi bilo potrebno porediti sledbenike iz niza b sa sledbenicima niza a, koji dolaze posle elemenata koji su se poklopili u prvom prolasku (npr. u prvom sledećem poređenju, u obzir se uzimaju elementi b[2] i a[1], nakon čega se porede elementi b[2] i a[2], a posle toga slede i ostala poređenja)).
Prosto rečeno, navedeni postupak "ume da potraje" (u pitanju je algoritam eksponencijalne složenosti).
Međutim, postoji i drugi problem: posle svih "muka", znali bismo samo dužinu * najdužeg podniza, ali, ne bismo imali zabeležene elemente koji čine podniz.
Budući da je potrebno iznaći postupak preko koga se pronalazi (i) spisak elemenata koji čine najduži zajednički podniz, a preko postupka koji smo prethodno prikazali - uspeli smo da pronađemo samo dužinu prvog "najdužeg" zajedničkog podniza, pri čemu su zanemareni ostali "potencijalni" najduži zajednički podnizovi (setimo se da u konkretnom primeru postoji i podniz 4, 3, 2, 1, iste dužine, a u drugim primerima može biti i mnogo više od dva podniza koji zadovoljavaju uslov zadatka) - jasno je da moramo "tražiti dalje".
Korišćenjem tehnika dinamičkog programiranja, moguće je rešiti prethodno navedene probleme ....
Rešenje korišćenjem metode dinamičkog programiranja.
Spomenuli smo na početku da dinamičko programiranje podrazumeva zapisivanje rešenja potproblema i korišćenje zapisanih (među)rešenja - nasuprot ponovnom računanju (koje je vremenski "skupo", odnosno dugotrajno).
Međutim, prvo je potrebno prepoznati da li u određenom problemu (uopšte) postoji "optimalna podstruktura" (koju smo takođe pomenuli na početku).
U slučaju problema najdužeg zajedničkog podniza, optimalna podstruktura ogleda se u sledećem: za svaku kombinaciju pozicija unutar niski a i b, moguće je odrediti - i zapisati - dužinu najdužeg zajedničkog podniza koji odgovara kombinaciji (i moguće je, po potrebi, očitati konkretne znakove koji tvore takav niz).
Što se tiče "tehnikalija" (koje su neophodne za rešavanje problema), za početak je potrebno kreirati matricu čiji broj vrsta (tj. redova) odgovara broju elemenata kraćeg niza, dok broj kolona odgovara broju elemenata dužeg niza (s tim da ćemo obe dimenzije uvećati za 1 - videćemo u nastavku zašto).
Zarad bolje preglednosti, nizove a i b ćemo ovoga puta popuniti znakovima alfabeta koji odgovaraju brojevima koje smo u prethodnom razmatranju koristili, i stoga nizovi (koji su praktično postali niske, odnosno stringovi), sada imaju sledeću strukturu ....
.... a matrica koja se koristi za beleženje međurešenja, ima sledeći oblik i početno stanje (uz napomenu da su tamno siva polja sa znakovima iz niski dodata samo zarad preglednosti (tj. "efekta"), i ne postoje u implementaciji):
I ovoga puta postoje pojedinačni koraci koji se tiču direktnog poređenja znakova, * ali, sa jednom (velikom) razlikom - nema ponovnog ispitivanja za pozicije koje su već ispitane!
Prvi element niza b poklapa se sa prvim elementom niza a ....
.... što će biti uredno zabeleženo u odgovarajuće polje matrice:
Što se tiče prvog poklapanja, u sve naredne pozicije u prvom redu matrice, takođe se može preneti vrednost 1.
Prenete jedinice imaju sledeće značenje: kada pogledamo bilo koji element niza a - posle drugog elementa, i prvi element niza b, najduži zajednički podstring ima dužinu jedan (kao što smo nagovestili, algoritam prenosa biće detaljno objašnjen na kraju članka).
Pretraga se nastavlja ....
U obzir se uzima sledeći element niza b, to jest, znak 'g' ....
.... ali, pošto ne postoji (nijedno) poklapanje, u polja matrice direktno se prenose vrednosti iz gornjeg reda.
U sledećem koraku, ispituje se poklapanje trećeg elementa niza b (znak 'c'), sa elementima niza a ....
Pošto je znak 'c' pronađen na 2. poziciji u nizu a, "deluje" kao da bi trebalo upisati vrednost 2 u obeleženo polje matrice, međutim - kako to rešiti algoritamski (to jest, kako naći "opravdanje")?
Broj prethodnih (tj. "dotadašnjih") poklapanja, zapisan je u polju matrice koje se nalazi (jedno mesto) gore-levo u odnosu na polje u koje treba ubeležiti informaciju o trenutnom poklapanju.
U konkretnom primeru, polje "gore-levo" sadrži vrednost 1.
Pronađenu vrednost samo treba uvećati za 1, to jest, treba - "baš kao što je delovalo" - upisati vrednost 2 (u polje koje se tiče trenutnog poklapanja).
Već posle nekoliko koraka, možemo videti 'lepotu i smisao' dinamičkog programiranja na delu: ne moraju se ponovo 'prebrojavati poklapanja' za prethodne korake (koji, da se podsetimo, praktično predstavljaju potprobleme).
Rešenja za prethodne korake - već su izračunata i zapisana.
Drugo pitanje je: kako možemo znati (u ovom slučaju), da se dvojka sme preneti u ostala polja (u redu)?
Jednostavno: znak 'c' se ne pojavljuje ni na jednoj od sledećih pozicija u nizu a (to smo, za sada, utvrdili vizuelnom metodom, a pravi algoritam prenosa, kao što smo već naveli, biće detaljno objašnjen na kraju članka i, što je najlepše od svega - zapravo je prilično jednostavan). :)
Sledeći znak koji se poredi je znak 'b' ....
Pronađeno je poklapanje sa 4. znakom niza a i, po istom algoritmu koji je korišćen u prethodnim koracima: u obzir se uzima vrednost iz gornjeg levog polja, uvećava se za jedan, a rezultat se upisuje u odgovarajuće polje matrice (pri čemu se broj 3 prenosi i u ostala polja u redu).
U sledećem koraku, znak 'h' traži se među elementima niza a ....
Znak 'h' iz niza b, poklapa se sa 7. elementom niza a (i stoga se u odgovarajuće polje matrice beleži vrednost 4, koja se takođe prenosi i u ostatak reda).
Na kraju, pogledajmo i složeniju situaciju u kojoj se znak iz niske b dvaput pojavljuje u niski a.
Znak 'a', prvi put se u nizu a pojavljuje na 3. mestu ....
Shodno ranije utvrđenim pravilima, u odgovarajuće polje matrice uredno će biti ubeležena vrednost 3 (pri čemu ubeležena vrednost praktično predstavlja podniz 'd', 'c', 'a'):
Sledeća pojava znaka 'a' je na 5. mestu ....
U polje matrice (koje odgovara poklapanju), beleži se vrednost 4 ....
.... i vidimo da pojava prvog znaka 'a' u nizu a - ni na koji način nije poremetila algoritam.
Za svako od poklapanja u poslednjem redu postoji "objašnjenje i pokriće" (i podaci zabeleženi u okolnim poljima matrice).
Nedoumice se otklanjaju lako, a moguće je pronaći i pojedinačna poklapanja (koja odgovaraju upisanoj dužini podniske).
Matrica je sada 'kompletirana':
Pronalaženje pozicija
U donjem desnom polju matrice upisana je vrednost koja predstavlja dužinu najdužeg zajedničkog podniza, ali, ta informacija, sama po sebi, ne ukazuje na konkretne pozicije na kojima se nizovi poklapaju.
Srećom (sve) pozicije su već upisane u matricu (na donekle posredan način) - i potrebno je samo pronaći ih (obilaskom matrice 'unazad').
Zarad pronalaženja polja u kome je zabeleženo prvo poklapanje dužine 4, potrebno je prvo (krećući se od donjeg desnog polja matrice nagore), pronaći prvi red u kome se pojavljuje vrednost 4 (u primeru koji koristimo, vrednost 4 pojavljuje se u pretposlednjem redu).
Potom, "kretanjem ulevo", pronalazi se i kolona, odnosno - konkretno polje, u kome se vrednost 4 prvi put pojavljuje ("prva četvorka" označena je na slici zelenom bojom).
Za pronalaženje 'prve trojke', treba preći sa polja koje sadrži 'prvu četvorku', na polje koje se nalazi jedno mesto gore i jedno mesto levo (trojka sa kružićem na donjoj slici), a potom se sa tog polja traži prva trojka - na isti način kako je pronađena 'prva četvorka':
- prvo je potrebno, 'krećući se nagore', pronaći prvi red u kome se trojka pojavljuje (program uvek mora pokušati da pređe u gornji red, ali, ovoga puta ostaje u istom redu)
- nakon pronalaženja odgovarajućeg reda, "kretanjem ulevo" pronalazi se i odgovarajuća kolona
Postupak se ponavlja sve dok se ne pronađu i "prva dvojka" i "prva jedinica" (sve pozicije na kojima se prvi put pojavljuju poklapanja, označene su na slici).
Algoritam za upis vrednosti u polje matrice
U primerima koje smo prikazali, vrednosti su posle poklapanja "nekako" prenošene u sva polja do kraja reda (s tim da smo pojasnili zašto u poslednjem redu prvo poklapanje nije odmah preneto i u ostala polja).
Nismo vas nigde 'prevarili' (niti je upisivanje vršeno nasumično), ali, detaljno objašnjenje o tome kako prenos funkcioniše, ipak smo ostavili za sam kraj (i kao što smo ranije naveli, postupak ni iz daleka nije komplikovan). :)
Elementi nizova koji se porede, poklapaju se, ili se ne poklapaju:
- ako se elementi poklapaju, u trenutno polje upisuje se vrednost koja je za 1 veća od vrednosti iz 'gornjeg-levog' polja pomoćne matrice (pri čemu (naravno) mislimo na polje
m[i - 1][j - 1], a ne na poljem[0][0]) - ako se elementi nizova ne poklapaju, potrebno je sagledati 'susedne vrednosti', koje se u matrici nalaze: jedno polje iznad i jedno polje levo (u odnosu na trenutno polje), nakon čega se upisuje veća od dve vrednosti
// a - duži niz, čija dužina odgovara broju kolona
// b - kraći niz, čija dužina odgovara broju redova
// m - pomoćna matrica
// i - brojač koji se poklapa sa nizom b
// (tj. sa redovima matrice)
// j - brojač koji se poklapa sa nizom a
// (tj. sa kolonama matrice)
// Ako se dva elementa unutar
// nizova poklapaju ....
if (b[i - 1] == a[j - 1]) {
m[i][j] = m[i - 1][j - 1] + 1;
// .... u matricu se upisuje
// vrednost iz 'gornjeg levog' polja,
// uvećana za jedan, a ako se
} // elementi ne poklapaju ....
else {
// Posmatraju se: levo polje (m[i][j - 1])
// i gornje polje polje matrice (m[i - 1][j]),
// i bira se veća od dve vrednosti
// (obično je gornja vrednost veća)
m[i][j] = (m[i][j - 1] >= m[i - 1][j])?
m[i][j - 1] :
m[i - 1][j];
}
Prikazani postupak se (naravno) ponavlja za svako polje, i (u praktičnom smislu), daje iste rezultate koje smo prikazali u primerima koje smo razmatrali.
Čitaocima koji su skloni "avanturizmu", prepuštamo (za vežbu), da samostalno osmisle algoritam koji ispisuje sve najduže zajedničke podnizove! :)