Bez obzira na kojem ste stupnju usavrsavanja programerske vjestine prva nelogicnost namece se sama od sebe. Primjerice, koristeci dinamicko programiranje u stvarnom zivotu da bismo saznali kolika je udaljenost izmedju nas i zida prema kojem hodamo morali bi prvo spoznati sve tajne svemira, unutar njih i zakone fizike pa temeljem poznatih spoznaja jednostavno zakljuciti da se radi o metru i pol.

U praksi, dovoljno je pogledati zid i sve nam je jasno bez da se zamaramo s tajnama svemira. Problem je, u ovom slucaju, rijesila intuicija. Obzirom da je to jedan od psiholoskih fenomena karakteristicniji za zene koje su pak manjinski dio programerske populacije, ne mozemo se u potpunosti pouzdati u takav nacin rjesavanja ovog naizgled banalnog problema. Srecom, mozemo se posluziti i fizikom, medjutim, ono sto danas slovi za siguran metar i pol, mozda vec sutra, nakon sto zadjemo dublje u tajne svemira, dobije jos koji centimetar nakon sto uzmemo u obzir i opseg potprostornih vakuola koje deformiraju prostor. Ukratko, kako god okrenemo jedino pouzdano rjesenje je doista upoznati sve tajne svemira i potom zakljuciti kako je udaljenost ipak metar i pol.

Oni koji citaju Asimova sad mogu isto to primjeniti na izgradnju elektronske pumpe.

One kojima pak nije jasno zasto sam morao zakomplicirate nesto sto samo po sebi nije dovoljno jasno moram razocarati cinjenicom da se ovdje doista radi o navedenom nacinu razmisljanja, a Sedgewick princip prilicno jasno objasnjava na tri karakteristicna primjera - problem ruksaka, mnozenje matrica i pretrazivanje binarnih stabala.

Ova tri problema naizgled nemaju nista zajednicko. U prvom se postavlja pitanje kako odabrati optimalnu kombinaciju stvari koje cemo potrpati u ruksak, a svaka od njih je razlicite velicine i razlicite vrijednosti. Problem mnozenja matrica je matematicke prirode i svodi se na utjecaj komutativnosti prilikom mnozenja na broj izvrsenih matematickih operacija koje vode do konacnog rjesenja. Pretrazivanje binarnih stabala najkonkretniji je informaticki problem i tice se optimizacije pretrazivanja kako bi se u sto manje koraka doslo do trazene informacije.

Ono sto ih povezuje je cinjenica da niti jedan ne karakterizira jedinstveno rjesenje, a trazenje pravog rjesenja obicno se svodi na trazenje najboljeg rjesenja nakon sto su pronadjena sva. Dakle, na rjesavanje svih mogucih pojedinih problema da bi se medju njima naslo neko koje odgovara nasem konkretnom problemu, a ujedno je prethodno zakljuceno da se radi o optimalnom rjesenju.

Ako i dalje nista nije jasno, probajte se opustiti i primjetiti da sam protekla cetiri odlomka zapoceo pokaznom zamjenicom.

Dinamicko programiranje krase dva osnovna problema. Prvi kaze da nije uvijek moguce pronaci konacno rjesenje kombiniranjem parcijalnih rjesenja. Drugim rijecima, ako imate dva auta od kojih jedan manje trosi, a drugi ide brze, nije moguce pronaci auto koji dovoljno brzo ide i dovoljno malo trosi jer oba rjesenja zadovoljavaju samo jedan uvjet. Drugi problem tice se relativnosti vremena i ukazuje na tuznu cinjenicu da ponekad moze postojati nebrojeno malih problema ili barem toliko puno da ih nije moguce rijesiti u razumnom roku (pa makar govorili o eonima).

Do dana danasnjeg nitko nije precizno definirao koji je tip problema najbolje rjesavati dinamickim programiranjem. Teorija se uglavnom svodi na to da se dinamickim programiranjem mogu rjesavati oni problemi koji su rjesivi dinamickim programiranjem.

Spomenuta tri primjera ne samo da su rjesiva dinamickim programiranjem nego se svaki surogat takvog rjesenja prije ili kasnije svede na dinamicko programiranje pa nema potrebe otkrivati toplu vodu.

Procitajte za svaki slucaj jos jednom prethodni odlomak. Dinamicko programiranje nije nesto sto cete obilato koristiti na natjecanjima, a ni u svakidasnjoj praksi (osim ako ne krcate brodove na terminalima). Moja osobna definicija dinamickog programiranja glasi "...najpametniji nacin za rjesavanje STATICKIH problema" i dalje spremno tvrdim da mu je to jedina primjena. Naime, ponekad (naglasak na ponekad) problem koji vapi za rjesavanjem dinamickim programiranjem morat cete rjesavati zaobilizanim putem iz jednostavnog razloga sto necete imati dovoljno vremena pronaci sva rjesenja. Ovo se odnosi na natjecanje uz standardni disclaimer da ce onaj tko vodi racuna o zadatku vjerojatno voditi racuna i o tome da vam da dovoljno vremena za pronaci sve rjesenja i odrediti najbolja, medjutim u sadasnjem sustavu natjecanja doci ce do toga da cete za svaki test primjer ponovo traziti vec pronadjena rjesenja.

A sad malo o konkretnim problemima.

PROBLEM RUKSAKA Sedgewick donosi kroz pricu o lopovu koji krece u pljacku s ruksakom velicine M (kubnih jedinica), a nailazi na veci plijen nego sto moze ponijeti. Plijen su nekakve komponente (N) koje krasi razlicita velicina (volumen, izrazen u onim istim kubnim jedinicama) i vrijednost. Lopov dolazi u dilemu - kako napuniti ruksak predmetima koji mu donose najvecu dobit? Ne treba ni spominjati da nije dovoljno inteligentan da neki od viskova potrpa u dzep.

Nas hi-tech lopov nosi notebook sa sobom, vadi ga iz ruksaka (usput napravi jos malo mjesta za plijen), pise program i za cas dolazi do optimalne kombinacije - uzima najveci dijamant, a ostatak krca zlatnom prasinom. Kasnije ga uhite jer su na notebooku koji je ostavio za sobom pronadjeni registrirani Windowsi pod njegovim imenom. Posten lopov.

Postavlja se pitanje kako je lopov rijesio problem? Jednostavno, po obicaju - izvrtio je dvije petlje od kojih u jednoj povecava broj razlicitih predmeta koji su mu na raspolaganju (N), a u drugoj raspolozivu velicinu ruksaka (M). Ovo bi trebalo biti sasvim dosta prosjecnom genijalcu za napisati program. Za one koji ce to tek postati, kod izgleda ovako nekako (Pascal):

for j:=1 to N do
 begin
 for i:=1 to M do
  if i-size[j]>=0 then
   if cost[i]<(cost[i-size[j]]+val[j]) then
    begin
    cost[i]:=cost[i-size[j]]+val[j];
    best[i]:=j
    end;
 end;

Kolicna koda ne samo da je za pohvalu (no, no... sto drugo ocekivati od profesora s Princetona?) nego cemo kasnije, kod problema s matricama, doci do zakljucka da je algoritam takodjer stvoren dinamickim programiranjem obzirom da bilo kakva promjena u slijedu provjera ili petlji unutar koda dodatno (i potpuno nepotrebno) produzava vrijeme izvodjenja programa.

Nakon sto program zavrsi s radom cost[i] sadrzi najvecu vrijednost koju mozemo posteci trpajuci predmete u ruksak kapaceta "i", a best[i] pamti zadnji predmet koji je dodan da bismo postigli trazeni maksimum.

Obzirom da su rjesenja sadrzana u nizu, a ne u varijabli, kao sto je to obicno slucaj, "i", odnosno zadanu velicinu ruksaka moguce je mijenjati (otuda DINAMICKO!) nakon sto smo izracunali sve vrijednosti i pronaci vec izracunati optimum bilo koje druge kombinacije.

Najljepse od svega je sto niz best[i] zapravo pamti sadrzaj ruksaka odnosno omogucava njegovu rekonstrukciju.

Pretpostavimo da imamo 5 predmeta (A-E) i parametre koji slijede:

velicina (size)         3       4       7       8       9
vrijednost (value)      4       5       10      11      13
naziv (name)            A       B       C       D       E

Prvo kalkuliramo najbolju kombinaciju za samo jedan predmet (A). Uz pretpostavku da je kapacitet ruksaka 17 (velicina), zakljucujemo da nam stane 5 predmeta A cija je ukupna vrijednost 20. Potom trazimo optimalnu kombinaciju sa A i B, a trazenje optimuma svode se na racunanje cost[i]. Pretpostavimo da je predmet "j" odabran za ruksak: najvisa ukupna vrijednost tada je val[j] (njegova vrijednost) plus cost[i-size[j]] (cime popunjavamo ostatak ruksaka). Ako dobivena vrijednost prelazi najvisu vrijednost koju mozemo postici bez dodavanja predmeta "j", azuriramo cost[i] i best[i], a u protivnom ih ne diramo.

Sadrzaj ruksaka pri optimalnom rjesenju moguce je pronaci koristeci niz "best". Po definiciji, best[M] je uvijek u ruksaku, a ostatak je isti kao za ruksak kapaciteta M-size[best[M]], odnosno best[M-size[best[M]]] je takodjer u ruksaku i tako redom.

Za trazenje svih rjesenja koriste se dvije petlje pa je tako vrijeme racunanja fiksno odredjeno i iznosi M*N. Time dolazimo do dva problema - ponekad je vrijeme racunanja neprihvatljimo i moramo traziti pametnije rjesenje (spomenuti zaobilazni put, ma kroz sto god on vodio). Drugi problem je puno veci, a tice se tipa varijabli koje se koriste u ovakvim kalkulacijama - algoritam radi samo s integerima! Ne samo da se ne zna rjesenje tog problema nego eminentni strucnjaci vjeruju da ni ne postoji. Sto nas, po jednoj od zabavnijih definicija, dovodi do zakljucka da to zapravo nije ni problem vec cinjenica.

DOMACA ZADACA je napisati konkretan program koji rjesava problem sa zadanim parametrima i pronaci optimalna rjesenja ako je broj raspolozivih predmeta 1, 2, 3, 4 i 5 (prema gornjoj tablici), odnosno sadrzaj ruksaka u svakom od spomenutih pet slucajeva. [DZ]

LANCANI PRODUKT MATRICA nije tako jednostavan za objasniti ako nemate pojma o matricama. Pod pretpostavkom da ste barem jednom vidjeli matricu (matematicku!) i da vam je poznato kako se ista sastoji od M redaka, odnosno N stupaca (najcesce) omedjenih uglatim zagradama morate jos samo znati nacin mnozenja matrica koji nam omogucava mnozenje samo onih matrica koje imaju medjusobno jednak broj stupaca i redaka. Kod kvadratnih matrica (M=N) to je jasno i njih mnozimo bez problema, medjutim matricu A koja ima dimenzije 2x3 moguce je mnoziti samo s matricom koja ima dimenzije ili Mx2 ili 3xN.

Mnozenja matrica je prica za sebe. Ako matricu velicine 2x3 mnozimo matricom 3x2 rezultat je matrica velicine 4x3, nakon 24 skalarnih produkata. Primjetite promjenu velicine dobivene matrice. Kada bi lanac matrica koje mnozimo cinilo 6 matrica (u primjeru kojeg Sedgewick navodi) i kada bi ih povecali sa 3 na 300 elemenata, mnozenje s lijeva na desno svelo bi se na nekih 6.000 skalarnih produkata, a s desna na lijevo na astronomskih 275.000!

U praksi matrice velicine 300x300 nisu tako rijetke kao sto bi se moglo pomisliti bez obzira sto nam u srednjoj skoli treba vjecnost za izracunati nesto konkretno sa 5x5. Vjerojatno je to bilo sasvim dovoljno nekome za razviti algoritam koji trazi najbolji slijed mnozenja matrica. Dakle, ne program koji mnozi konkretne matrice vec program koji jednostavno odredjuje hoce li se mnoziti (A*B)*C ili A*(B*C).

Vjerovali ili ne, postoji cak i matematicka formula koja daje priblizan broj ukupnih nacina na koji se moze "zagraditi" pojedini matematicki izraz sa N varijabli, a glasi 4^(N-1)/N*sqrt(PI*N). To je ujedno i ukupan broj mogucih kombinacija na koji mozemo mnoziti nase matrice.

Algoritam koji rjesava taj problem dan je u nastavku:

for i:=1 to N do
 for j:=i+1 to N do cost[i,j]:=maxint;
for i:=1 to N do cost[i,i]:=0;
for j:=1 to N-1 do
 for i:=1 to N-j do
  for k:=i+1 to i+j do
   begin
   t:=cost[i,k-1]+cost[k,i+j]+r[i]*r[k]*r[i+j+1];
   if t < cost[i,i+j] then
    begin
    cost[i,i+j]:=t;
    best[i,i+j]:=k
    end;
   end;

Kao sto vidimo (vidimo li?), problem je ponovo rijesen trazenjem svih mogucih kombinacija mnozenja matrica. Postoji samo jedan nacin za pomnoziti M1xM2 odnosno M2xM3 itd. Izracunamo te vrijednosti, pohranimo ih i trazimo umnoske umnozaka sa iducom matricom u nizu i tako dok ne iscrpimo sve kombinacije. Kao i kod ruksaka, u best[] pamtimo optimalne kombinacije kako bi mogli rekonstruirati kompletan postupak. Procedura u nastavku radi upravo to.

procedure order(i,j:integer);
 begin
 if i=j then write(name(i)) else
  begin
  write('(');
  order(i,best[i,j]-1); write('*'); order(best[i,j],j);
  write(')');
  end
 end;

OPTIMALNO PRETRAZIVANJE BINARNOG STABLA problem je izrazito informaticke prirode. Kod pretrazivanja binarnih stabala pozeljno je znati frekvenciju pojavljivanja odredjenog podatka kako bi ga se moglo smjestiti sto blize "vrhu" i tako skratiti vrijeme pristupa. Primjerice, kada bi pisali spellchecker za hrvatski jezik, pri vrhu stabla bi imali veznike i priloge, a tek negdje na dnu rijeci kao sto je otorinolaringologija. Nije bitna duzina rijeci nego njezina ucestalost u svakodnevnom govoru sto znaci da bi na samom dnu naseg stabla zavrsile rijeci koje se vode kao arhaizmi.

Obzirom da se problem pretrazivanja binarnih stabala vrlo detaljno proucio tijekom istrazivanja kompresije podataka, a posebice od strane Huffmana koji je definirao najbrze nacine kretanja kroz stablo, ta grana informatike pokazala se izrazito plodnim tlom za koristenje dinamickog programiranja. Naime, kao sto se u prethodnom primjeru nije radilo o mnozenju konkretnih matrica tako se ni ovdje ne radi o pretrazivanju konkretnog stabla vec o njegovom formiranju kako bi ga se potom moglo najucinkovitije pretrazivati. Upravo u tome lezi snaga, ali i statike dinamickog programiranja. Ne postoji njegova dinamicka primjena (u navedenim problemima, recimo), ali se pokazalo kao najpametnije rjesenje za onaj staticki dio koji prethodi konkretnoj operaciji i time je optimizira.

Konkretno, pretpostavimo da je zadan skup kljuceva za pretrazivanje stabla (K1 Time se bavi ovaj algoritam:

for i:=1 to N do
 for j:=i+1 to N+1 do cost[i,j]:=maxint;
for i:=1 to N do cost[i,i]:=f[i];
for i:=1 to N+1 do cost[i,i-1]:=0;
for j:=1 to N-1 do
 for i:=1 to N-j do
  begin
  for k:=i to i+j do
   begin
   t:=cost[i,k-1]+cost[k+1,i+j];
   if t <cost[i,i+j] then
    begin cost[i,i+j]:=t; best[i,i+j]:=k end;
   end;
  t:=0; for k:=i to i+j do t:=t+f[k];
  cost[i,i+j]:=cost[i,i+j]+t;
  end;

Naveo sam sva tri primjera iako problem ruksaka najjasnije objasnjava problematiku i uvodi nas u svijet dinamickog programiranja. Na ovaj nacin isplati se rjesavati sve varijacije na temu trgovackog putnika ili bilo kakve optimizacije koristenja resursa (prostora/vremena) bio to ruksak ili prekooceanski brod. Tu je i problem rezanja maksimalnog broja zmajeva iz jednog papira pa svima koji imaju volje preporucam da i njega pokusaju svladati ovim nacinom. Najzabavnije od svega je sto uvijek dobivamo gomilu optimiziranih rezultata s kojima se mozemo dalje igrati. Primjerice, Sedgewickov lopov, prije nego krene u harac mora nabaviti odgovarajuci ruksak cime bi se i prethodno fiksno definirana velicina ruksaka uzimala u obzir dodatno komplicirajuci algoritam, ali kreirajuci i daleko veci broj rjesenja. Zasigurno postoji slucaj u kojem lopov ne bi mogao iskoristiti sav kapacitet ruksaka, a prethodno se mora odluciti ruksak koje velicine ukrasti uz odgovarajuci rizik koji raste proporcionalno velicini ruksaka...

(c) 18/04/1999 Goran Paulin