Uvod u dinamičko programiranje

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 praktičnom smislu: uz povećano memorijsko zauzeće, veoma primetno se smanjuje i 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 } ....

Najduži zajednički podniz - naivno rešenje - korak 01
Slika 1. - Nizovi za koje se traži najduži zajednički podniz.

.... 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 sagledavanja "šire slike" na uzorcima ne-preterano-velikog obima.

Međutim, računari takvu sposobnost nemaju uopšte (čak ni u slučaju izrazito malih nizova), a u slučaju većih nizova (pri čemu niz ne mora biti izrazito velik; dovoljno je da se sastoji iz 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 ....

Najduži zajednički podniz - naivno rešenje - korak 02
Slika 2. - Naivno rešenje - korak 1.

.... pri čemu se prvo poklapanje pojavljuje već na 1. poziciji.

Najduži zajednički podniz - naivno rešenje - korak 03
Slika 3. - Naivno rešenje - korak 2. - Pronađeno je prvo poklapanje (dužina NZP - 1).

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 kojima je pronađeno prvo poklapanje ....

Najduži zajednički podniz - naivno rešenje - korak 04
Slika 4. - Naivno rešenje - korak 3.

.... međutim, u ovom slučaju, element (7) ne nalazi se ni na jednoj poziciji u nizu a ....

Najduži zajednički podniz - naivno rešenje - korak 05
Slika 5. - Naivno rešenje - korak 4. - U ovom slučaju nema poklapanja.

Pretraga se usmerava na sledeći element niza b (3) ....

Najduži zajednički podniz - naivno rešenje - korak 06
Slika 6. - Naivno rešenje - korak 5.

.... koji se poklapa sa 2. elementom niza a.

Najduži zajednički podniz - naivno rešenje - korak 07
Slika 7. - Naivno rešenje - korak 6. - Pronađeno je poklapanje (dužina NZP - 2).

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

Najduži zajednički podniz - naivno rešenje - korak 08
Slika 8. - Naivno rešenje - korak 7.

.... poklapa se sa 4. elementom niza a (dužina najdužeg zajedničkog podniza je 3).

Najduži zajednički podniz - naivno rešenje - korak 09
Slika 9. - Naivno rešenje - korak 8. - Pronađeno je poklapanje (dužina NZP - 3).

Sledeći element niza b (8) ....

Najduži zajednički podniz - naivno rešenje - korak 10
Slika 10. - Naivno rešenje - korak 9.

.... poklapa se sa 7. elementom niza a (dužina najdužeg zajedničkog podniza je 4).

Najduži zajednički podniz - naivno rešenje - korak 11
Slika 11. - Naivno rešenje - korak 10. - Pronađeno je poklapanje (dužina NZP - 4).

Poslednji element niza b (1) ....

Najduži zajednički podniz - naivno rešenje - korak 12
Slika 12. - Naivno rešenje - korak 11.

.... ne poklapa se ni sa jednim elemtnom niza a (koji sledi posle pozicije na kojoj je pronađeno poslednje poklapanje) ....

Najduži zajednički podniz - naivno rešenje - korak 13
Slika 13. - Naivno rešenje - korak 12. - Nema poklapanja.

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

Najduži zajednički podniz - naivno rešenje - korak 14
Slika 14. - Naivno rešenje - konačni rezultat prvog prolaska - dužina NZP-a je 4, ali - u pitanju je samo prvi NZP koji je pronađen - koji ne mora predstavljati konačno rešenje!

Kratka analiza

Prikazani postupak ima nekoliko nedostatka.

Prvi nedostatak (najbitniji): 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 ako se pronađu i ispitaju svi zajednički podnizovi (u sledećoj "etapi", "jednoj od mnogih", počevši od sledećeg odgovarajućeg početnog elementa niza b koji se poklapa sa nekim od početnih elemenata niza a - na primer b[2] i a[1] - ponovo bi bilo potrebno porediti sledbenike iz niza b sa sledbenicima iz niza a, koji dolaze posle elemenata koji su se poklopili).

Prosto rečeno, takav 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 sve 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, 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).

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

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 1
Slika 15. - Nizovi za koje se traži NZP, metodom dinamičkog programiranja (ovoga puta, koristićemo nizove znakova).

.... 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/"efekta", i ne postoje u implementaciji):

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 2
Slika 16. - Pomoćna matrica - početno stanje (u implementaciji, potrebno je da sva polja budu inicijalizovana vrednošću 0, što nije prikazano na slici, zarad preglednosti).

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 (umesto ponovnog računanja, koriste se zapamćeni rezultati prethodnih ispitivanja)!

Prvi element niza b poklapa se sa prvim elementom niza a ....

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 3
Slika 17. - Prvi element niza b poredi se sa prvim elementom niza a.

.... što će biti uredno zabeleženo u odgovarajuće polje matrice:

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 4
Slika 18. - Algoritam pronalazi poklapanje i odgovarajuća vrednost se upisuje u matricu.

Što se tiče prvog poklapanja, u sve naredne pozicije u prvom redu matrice, takođe se može preneti vrednost 1.

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 5
Slika 19. - Takođe, vrednost 1 prenosi se u ostatak reda (u nastavku teksta, pojasnićemo kako tačno se obavlja prenos).

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, sam 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' ....

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 6
Slika 20. - Drugi element niza b poredi se sa elementima niza a, ali, nema nijednog poklapanja.

.... ali, pošto ne postoji (nijedno) poklapanje, u polja matrice direktno se prenose vrednosti iz gornjeg reda.

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 7
Slika 21. - Budući da u poslednjem koraku pretrage nije pronađeno nijedno poklapanje, u ostala polja u redu, prenose se vrednosti iz gornjeg reda.

U sledećem koraku, ispituje se poklapanje trećeg elementa niza b (znak 'c'), sa elementima niza a ....

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 8
Slika 22. - Treći element niza b poredi se sa elementima niza a i pojavljuje se poklapanje na 2. mestu.

Pošto je znak 'c' pronađen na 2. poziciji u nizu a, "deluje" kao da treba 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 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).

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 9
Slika 23. - Zarad pronalaženja vrednost za upis, potrebno je osvrnuti se na polje koje se nalazi dijagonalno (levo-gore), i upisati vrednost koja je veća za 1 od pronađene vrednosti.

Već posle nekoliko koraka, možemo videti lepotu dinamičkog programiranja na delu: ne moraju se ponovo računati rešenja za prethodne korake (koji, da se podsetimo, praktično predstavljaju potprobleme), jer - 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)?

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 10
Slika 24. - Ostatak reda takođe se popunjava vrednošću 2.

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

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 11
Slika 25. - Četvrti element niza b poredi se sa elementima niza a i pojavljuje se poklapanje na 4. mestu.

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

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 12
Slika 26. - Vrednost za upis je 3 (i ovoga puta, vrednost se prenosi u ostatak reda).

U sledećem koraku, znak 'h' traži se među elementima niza a ....

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 13
Slika 27. - Peti element niza b poredi se sa elementima niza a i pojavljuje se poklapanje na pretposlednjem mestu.

.... i, ovoga puta, 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).

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 14
Slika 28. - Vrednost za upis je 4 (i ovoga puta, vrednost se prenosi 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 ....

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 15
Slika 29. - Poslednji element niza b poredi se sa elementima niza a (prvo poklapanje pojavljuje se 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'):

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 16
Slika 30. - Vrednost za upis je 3, ali, ovoga puta vrednost se prenosi samo do prvog sledećeg mesta na kome dolazi do poklapanja (uskoro ćemo se detaljno upoznati sa univerzalnim algoritmom, koji važi u svim situacijama).

Sledeća pojava znaka 'a' je na 5. mestu ....

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 17
Slika 31. - Sledeće poklapanje pojavljuje se na 5. poziciji u nizu a.

.... a u polje matrice (koje odgovara poklapanju), beleži se vrednost 4 ....

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 18
Slika 32. - Vrednost za upis je 4 (ovoga puta, vrednost se prenosi u ostatak reda).

.... 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 - ukoliko postoji potreba - mogu se pronaći i pojedinačna poklapanja (koja odgovaraju upisanoj dužini podniske).

Matrica je sada 'kompletirana':

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 19
Slika 33. - Matrica je popunjena i dužina najdužeg zajedničkog podniza je upisana u donje desno polje matrice

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

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 20
Slika 34. - Pronalaženje polja u kome je zabeleženo prvo poklapanje dužine 4.

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), 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), a nakon pronalaženja odgovarajućeg reda, "kretanjem ulevo" pronalazi se i odgovarajuća kolona.

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 21
Slika 35. - Pronalaženje polja u kome je zabeleženo prvo poklapanje dužine 3.

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

Najduži zajednički podniz - rešenje metodom dinamičkog programiranja - korak 22
Slika 36. - Pronalaženje ostalih poklapanja.

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 stoga ćemo se osvrnuti na algoritam za upis vrednosti u polja matrice (i, kao što smo već naveli, algoritam je sasvim jednostavan). :)

Elementi nizova koji se porede, poklapaju se, ili se ne poklapaju:

  • ako se elementi poklapaju, vrednost koja se upisuje u trenutno polje dobija se (kao što smo već videli), uvećanjem vrednosti iz gornjeg-levog polja za jedan
  • ako se elementi nizova ne poklapaju, potrebno je sagledati vrednosti (tj. 'susede'), koji se u matrici nalaze: jedno polje iznad i jedno polje levo (u odnosu na trenutno polje) - i zatim izabrati veću 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 (redovima matrice)
// j - brojač koji se poklapa sa nizom a (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 (m[i][j - ])
	// i gornje (m[i - 1][j]) polje matrice
	// 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];
}
		
	
Slika 37. - Algoritam za upisivanje vrednosti u polja pomoćne matrice.

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! :)

Napomena: Tekstovi i slike na sajtu www.skola-programiranja.rs (osim u slučajevima pojedinih fotografija, gde je drugačije navedeno) predstavljaju intelektualnu svojinu autora sajta www.skola-programiranja.rs i zabranjeno je njihovo korišćenje na drugim sajtovima i štampanim medijima, kao i bilo kakvo korišćenje u komercijalne svrhe, bez eksplicitnog odobrenja autora i Računarskog centra SystemPro. ©SystemPro d.o.o. novembar 2019.
Autor članka Nikola Vukićević Za web portal www.skola-programiranja.rs Preuzeto sa sajta www.codeblog.rs uz odobrenje autora
Podelite sa prijateljima: