Dinamičko programiranje

Dinamičko programiranje je metoda optimizacije algoritama kojom se, uz povećano memorijsko zauzeće, smanjuje vreme izvršavanja.

Ne mogu se svi problemi rešiti metodom dinamičkog programiranja, ali, možemo to učiniti ukoliko je početni problem moguće rastaviti na potprobleme (koji se ponavljaju), pri čemu rezultate izračunavanja za date potprobleme možemo zapisati i naknadno koristiti.

Za probleme kod kojih je navedeni pristup moguć, kažemo da imaju optimalnu podstrukturu, a proces zapisivanja izračunatih rezultata potproblema naziva se memoizacija.

Da bismo sve ovo bolje razumeli, razmotrićemo jedan od najpoznatijih problema dinamičkog programiranja - problem pronalaženja najdužeg zajedničkog podniza (razmotrićemo prvo neefikasni, "naivni" algoritam, a potom ćemo demonstrirati prednosti upotrebe metode dinamičkog programiranja).

Problem najdužeg zajedničkog podniza

Za dva niza, potrebno je pronaći dužinu najdužeg zajedničkog podniza i ispisati elemente koji čine taj podniz.

Uzećemo za primer dva niza celobrojnih vrednosti: niz a[] {4, 3, 1, 2, 1, 5, 8, 9} i niz b[] {1, 4, 5, 3, 2, 8}.

Najduzi zajednicki podniz - naivno rešenje - korak 01
Slika 1. - Nizovi za koje ćemo tražiti najduži zajednički podniz.

Letimičnim pregledom, u ovom jednostavnom primeru, neće nam biti teško da uvidimo da najduži zajednički podniz formiraju podnizovi {4, 3, 2, 8}, ili {4, 3, 2, 1}. Naravno, ovde to lako možemo uvideti pošto je uzorak koji posmatramo mali. Ljudi imaju sposobnost ovakvog sagledavanja (na manjim uzorcima), dok računari nemaju taj kapacitet. U slučaju velikih nizova (dovoljno je da se nizovi sastoje iz par desetina elemenata) i mi kao ljudi bismo morali pribeći nekoj drugoj metodi sagledavanja.

Naivno rešenje

Naivno rešenje ovog problema izgledalo bi otprilike ovako:

Biramo prvi element niza b (4), tražimo ga u nizu a ....

Najduzi zajednicki podniz - naivno rešenje - korak 02
Slika 2. - Naivno rešenje - korak 1.

.... i pronalazimo ga na 1. poziciji.

Najduzi zajednicki podniz - naivno rešenje - korak 03
Slika 3. - Naivno rešenje - korak 2. - Pronašli smo prvo poklapanje (dužina NZP - 1).

Pamtimo da je dužina najdužeg zajedničkog podniza 1 i prelazimo na sledeći element niza b i tražimo ga na pozicijama koje slede poziciju na kojoj smo pronašli prvo poklapanje ....

Najduzi zajednicki podniz - naivno rešenje - korak 04
Slika 4. - Naivno rešenje - korak 3.

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

Najduzi zajednicki podniz - naivno rešenje - korak 05
Slika 5. - Naivno rešenje - korak 4. - U ovom slučaju nema poklapanja.

Prelazimo na sledeći element niza b ....

Najduzi zajednicki podniz - naivno rešenje - korak 06
Slika 6. - Naivno rešenje - korak 5.

.... pronalazimo ga na 2. poziciji i pamtimo da je dužina najvećeg zajedničkog podniza 2 ....

Najduzi zajednicki podniz - naivno rešenje - korak 07
Slika 7. - Naivno rešenje - korak 6. - Pronašli smo poklapanje (dužina NZP - 2).

.... a potom prelazimo na sledeći element niza b i ponavljamo postupak sve dok ne pronađemo podniz "najveće dužine" ....

Najduzi zajednicki podniz - naivno rešenje - korak 08
Slika 8. - Naivno rešenje - korak 7.

Element 2 pronalazimo na 4. poziciji u nizu a (dužina najdužeg zajedničkog podniza je 3).

Najduzi zajednicki podniz - naivno rešenje - korak 09
Slika 9. - Naivno rešenje - korak 8. - Pronašli smo poklapanje (dužina NZP - 3).

Element 8 ....

Najduzi zajednicki podniz - naivno rešenje - korak 10
Slika 10. - Naivno rešenje - korak 9.

.... pronalazimo na 7. poziciji (dužina najdužeg zajedničkog podniza je 4).

Najduzi zajednicki podniz - naivno rešenje - korak 11
Slika 11. - Naivno rešenje - korak 10. - Pronašli smo poklapanje (dužina NZP - 4).

Element 1 ....

Najduzi zajednicki podniz - naivno rešenje - korak 12
Slika 12. - Naivno rešenje - korak 11.

.... ne pronalazimo nigde ....

Najduzi zajednicki podniz - naivno rešenje - korak 13
Slika 13. - Naivno rešenje - korak 12. - Nema poklapanja.

.... tako da je trenutno pronađeni najduži zajednički podniz onaj koji smo pronašli u pretposlednjem koraku pretrage i njegova dužina je 4:

Najduzi zajednicki podniz - naivno rešenje - korak 14
Slika 14. - Naivno rešenje - konačan rezultat - dužina NZP-a je 4, ali - ovo je samo prvo od mogućih NZP-ova!

Međutim .... Na ovaj način pronašli smo samo jedan zajednički podniz (setimo de da postoji i podniz 4, 3, 2, 1 - iste dužine), onaj koji počinje prvim elementom niza b koji se poklopio sa nekim elementom niza a. Šta ako to nije najduži podniz (u našem slučaju jeste - tako smo udesili zared jednostavnosti i preglednosti - ali, u nekom drugom slučaju, prvi podniz koji pronađemo, verovatno neće biti i najduži)? To ćemo ustanoviti tek kada pronađemo sve zajedničke podnizove, počevši od sledećeg odgovarajućeg početnog elementa niza b, pri čemu ćemo porediti njegove sledbenike sa sledbenicima elementa niza a sa kojim se ovaj element poklopio.

Prosto rečeno, ovakav postupak "ume da potraje" i, takođe (što je još veći problem), posle svih "muka", znaćemo samo dužinu najdužeg podniza, ali, nećemo imati zabeležene elemente koji čine ovaj podniz!

Najduži zajednički podniz - 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 tih zapisanih rešenja (nasuprot ponovnom računanju, koje je vremenski "skupo", odnosno dugotrajno).

U slučaju problema najdužeg zajedničkog podniza, potrebno je kreirati matricu čiji broj vrsta (redova) odgovara broju elemenata kraćeg niza, uvećanom za jedan, dok broj kolona odgovara broju elemenata većeg niza (koji takođe uvećavamo za jedan).

Radi preglednosti, nizove a i b ćemo ovoga puta popuniti znakovima alfabeta koji odgovaraju brojevima koje smo u prethodnom razmatranju koristili, te će sada naši nizovi izgledati ovako ....

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 1
Slika 15. - Nizovi koje ćemo porediti korišćenjem metode dinamičkog programiranja. Ovoga puta, to će biti niske karaktera.

.... a matrica koju ćemo koristiti za beleženje međurešenja, imaće sledeći oblik i početno stanje:

Najduzi zajednicki 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 na vrednost 0, ali ovde to, zbog preglednosti, nismo prikazali).

I ovoga puta, vršićemo direktno poređenje znakova, ali, sa jednom velikom razlikom - nećemo se vraćati na ispitivanje onoga što smo već ispitali!

Prvi element niza b pronalazimo na prvoj poziciji u nizu a ....

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 3
Slika 17. - Poredimo prvi element niza b sa prvim elementom niza a.

.... i to beležimo u matricu:

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 4
Slika 18. - Pronalazimo poklapanje i upisujemo odgovarajuću vrednost u matricu.

Ali takođe, za sve naredne pozicije u prvom redu matrice, takođe beležimo (prenosimo) vrednost 1.

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 5
Slika 19. - Takođe, prenostimo vrednost 1 i u ostatak reda (kako tačno to radimo, pojasnićemo u nastavku teksta).

Prenete jedinice označavaju da, kada pogledamo bilo koji element niza a, posle drugog, i prvi element niza b, najduži zajednički podstring ima dužinu jedan (sam algoritam prenosa biće detaljno objašnjen na kraju članka).

Potom, uzimamo u obzir sledeći element niza b (znak g) i tražimo ga u nizu a ....

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 6
Slika 20. - Poredimo drugi element niza sa elementima niza a, ali ne pronalazimo ni jedno poklapanje.

Pošto ga ne pronalazimo nigde u nizu a, u polja matrice prenećemo direktno vrednosti iz gornjeg reda.

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 7
Slika 21. - Budući da u poslednjem koraku pretrage nismo našli ni jedno poklapanje, prenećemo vrednosti iz gornjeg reda.

U sledećm koraku, tražimo treći element niza a (znak c) u nizu b ....

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 8
Slika 22. - Poredimo treči element niza b sa elementima niza a i nalazimo poklapanje na 2. mestu.

Pošto smo ga pronašli na 2. poziciji deluje da u dato polje matrice treba upisati vrednost 2. Međutim ....

Kako ćemo ovo rešiti algoritamski (kako naći "opravdanje")? Pogledaćemo poziciju koja se nalazi dijagonalno u odnosu na polje koje upisujemo (levo-gore) ....

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 9
Slika 23. - Da bismo upisali odgovarajuću vrednost u polje matrice, pogledaćemo polje koje se nalazi dijagonalno, levo-gore i uvećati pronađenu vrednost za 1.

Tamo je već upisan broj poklapanja koja su prethodila poklapanja koje trenutno posmatramo i upravo to je lepota dinamičkog programiranja!

Koju god pozicu da posmatramo možemo reći sledeće: prethodna poklapanja su potproblemi (najduži zajednički podniz za delove nizova a i b), a rešenja tih problema su zapisana u pomoćnu matricu i možemo ih koristiti tako što broj iz gornjeg levog polja uvećaćemo za jedan (i takođe, ostatak reda ćemo popuniti vrednošću dva).

Kako znamo da (u ovom slučaju) smemo da prenesemo dvojku u ostala polja? Jednostavno, znak c se ne pojavljuje ni na kojoj od sledećih pozicija u nizu a (napomenimo još jednom da će algoritam prenosa biti detaljno objašnjen na kraju ovog članka).

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 10
Slika 24. - Ostatak reda ćemo takođe popuniti vrednošću 2.

Sledeća vrednost koju posmatramo je znak b ....

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 11
Slika 25. - Poredimo četvrti element niza b sa elementima niza a i pronalazimo poklapanje na 4. mestu.

Pronalazimo poklapanje sa 4. znakom niza a i, po istom principu od malopre, uzimamo u obzir vrednost iz gornjeg levog polja, uvećavamo je za jedan, upisujemo u matricu i prenosimo datu vrednost u ostala polja u redu.

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 12
Slika 26. - Vrednost za upis je 3. I ovoga puta, prenećemo datu vrednost u ostatak reda.

Nastavljamo dalje i tražimo znak h u nizu a ....

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 13
Slika 27. - Poredimo peti element niza b sa elementima niza a i nalazimo poklapanje na pretposlednjem mestu.

Pronalazimo ga na 7. poziciji i beležimo u odgovarajuće polje matrice vrednost 4 (koju takođe prenosimo i u ostatak reda).

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 14
Slika 28. - Vrednost za upis je 4. I ovoga puta, prenostimo datu vrednost u ostatak reda.

I za kraju, pogledajmo slučaj koji prikazuje na koji način korišćenje pomoćne matrice (u okviru metode dinamičkog programiranja) obuhvata celokupnu situaciju i beleži sve informacije.

Znak 'a' pojavljuje se u nizu a dvaput. Prvi put na 3. mestu ....

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 15
Slika 29. - Poredimo poslednji element niza b sa elementima niza a. Prvo poklapanje pronalazimo na 3. mestu.

Uredno ćemo ubeležiti vrednost 3 u odgovarajuće polje matrice (podniz koji odgovara ovoj dužini je: d, c, a).

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 16
Slika 30. - Vrednost za upis je 3, ali ćemo je ovoga puta preneti samo do prvog sledećeg mesta na kome se dešava poklapanje. Takođe, uskoro ćemo se detaljno upoznati sa algoritmom koji važi za sva polja preko koga "znamo" da li i dokle smemo da prenosimo vrednosti.

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

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 17
Slika 31. - Sledeće poklapanje pronalazimo na 5. poziciji u nizu a.

.... te ćemo u polje matrice uredno ubeležiti vrednost 4.

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 18
Slika 32. - Upisaćemo vrednost a i preneti je u ostatak reda.

Matrica sada ima svoj konačni oblik:

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 19
Slika 33. - Matrica sada ima svoj konačni oblik 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 to nam ne ukazuje na konkretne pozicije na kojima se nizovi poklapaju. Da bismo ovo pronašli, moramo obići polja matrice unazad. Međutim, nisu sva polja bitna i takođe, moramo se odlučiti za neku konkretnu kombinaciju. U našem slučaju, tražićemo prvi podniz najveće dužine.

Da bismo pronašli prvi podniz dužine 4, moramo (krećući se na gore) pronaći prvi red u kome se pojavljuje vrednost 4. Vrednost 4 pojavljuje se u pretposlednjem redu. Potom, krećući se ulevo, pronalazimo i kolonu (odnosno konkretno polje) u kojoj se vrednost 4 prvi put pojavljuje.

Na ovaj način pronašli smo prvu "četvorku". Da bismo pronašli prvu trojku, preći ćemo sa polja koje sadrži prvu četvorku na polje koje se nalazi jedno mesto gore i jedno mesto levo, a potom ćemo sa tog polja tražiti prvu trojku na isti način kako smo pronašli prvu četvorku (prvo, krećući se na gore, tražimo prvi red u kome se trojka pojavljuje, a onda, krećući se ulevo, tražimo i kolonu)

Postupak ponavljamo dok ne pronađemo i prvu dvojku i prvu jedinicu (pozicije na kojima se prvi put pojavljuju poklapanja označene su na slici).

Najduzi zajednicki podniz - rešenje metodom dinamičkog programiranja - korak 20
Slika 34. - Da bismo pronašli pozicije na kojima se dešavaju poklapanja koja obrazuju NZP, primenićemo sledeću roceduru: prvo ćemo pronaći na kom mestu se prvi put pojavljuje vrednost iz donjeg desnog polja matrice (4), zatim ćemo posetiti to polje, sa tog polja preći ćemo na gornje polje i tražiti gde se prvi put pojavljuje vrednost tog polja (3) i tako redom, dok ne pronađemo prvu pojavu broja 1 u matrici koja odgovara prvoj pojavi broja 2 (koja je odgovarala prvoj pojavi broja tri, koji smo prethodno već pronašli).

Detaljno objašnjenje algoritma za upis vrednosti u polje matrice

U prvih pet redova smo, posle poklapanja, pronađenu vrednost ("nekako") prenosili u sva polja do kraja reda, a u poslednjem redu smo to radili "delimično". Nismo vas nigde prevarili, niti smo upisivanje vršili nasumično, ali smo detaljno objašnjenje o tome kako prenos funkcioniše ipak ostavili za sam kraj, te ćemo ovde objasniti formulu po kojoj se zapravo upisuje vrednost u neko od polja matrice.

Postupak je (srećom) krajnje jednostavan.

Elementi nizova koje poredimo se poklapaju ili ne poklapaju. Ako se poklapaju, vrednost koju upisujemo u odgovarajuće polje matrice dobija se (kao što smo već videli) uvećanjem vrednosti iz gornjeg-levog polja za jedan. Ako se elementi nizova ne poklapaju, posmatraćemo u matrici vrednosti koje se nalaze direktno iznad i levo u odnosu na polje koje upisujemo i izabrati veću od te dve vrednosti.

									
	// a - duzi 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 (i redovima matrice)
	// j - brojač koji se poklapa sa nizom a (i kolonama matrice)
									
	if(b[i - 1] == a[j - 1]) // Ako se dva elementa unutar nizova poklapaju ....
	{
		// .... u matricu se upisuje vrednost iz gornjeg levog polja,
		// uvećana za jedan
		m[i][j] = m[i - 1][j - 1] + 1;
	}
	else                     // .... a, ako se elementi ne poklapaju
	{
		// 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 35. - Algoritam za upisivanje vrednosti u polja pomoćne matrice.

Ovaj postupak, naravno, ponavlja se za svako polje i, u praktičnom smislu, daje iste rezultate koje smo dobijali u primerima koje smo koristili.

Učenicima koji su skloni "avanturizmu", prepuštamo 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: