Evo da probam da kažem nešto na zadatu temu.
Najpre u vezi s dinamičkim programiranjem. Slažem se da je naziv pomalo nesrećan, pošto je jelte svaki program posledica programiranja; što bi sad pa to dinamičko bilo posebnije od svih ostalih? Ne bih se složio sa onima koji kažu da je dinamičko programiranje korišćenje rekurzije, jer se zapravo
svaki program može izraziti rekurzivno. O tome govori ta, u par navrata pominjana, Čerčova teza.
Kada pišete program, rekurzije se obično izravnaju da bi cela stvar bila manji zalogaj za računar, pa se zato u samim sorsovima pojavljuju retko. Ali rekurzivni programi su neverovatno važni kada se algoritam
izmišlja. To je zato što svaki rekurzivni program možemo da izrazimo preko samo tri bitna sastojka: početnog uslova, induktivne hipoteze i induktivnog koraka. To su jedine tri stvari koje treba zapamtiti.
Dosta često ljudi o programima razmišljaju tako što pokušavaju u glavi da izvrše sve instrukcije, korak po korak, vodeći računa o međurezultatima. Upoznao sam nekoliko ljudi koji mogu da isprate program do u neverovatnu dubinu, ali IMHO to je rasipanje resursa. Gde bi im bio kraj da tu metodologiju zamene samo sa tri gorepomenute stvari; definišite ih i pustite da indukcija odradi ostatak posla za vas.
Naravno da je problem nabosti pravu induktivnu hipotezu, i induktivni korak da bi se sve razmotalo kako treba (obično početni uslov nije glavobolja), ali jednom kad ste to uradili, prepevavanje na jezik petlji i uslova je čista nizbrdica. (Ovde ću malo da se ponovim pa da kažem da Udi Manber u svojoj knjizi Introduction to Algorithms: a creative approach objašnjava isto ali mnogo tačnije, bolje i lepše; pogledajte ako možete, nećete se razočarati:)
Evo jedan bez veze primer koji (kao) objašnjava onaj deo sa rekurzijama. Treba da se napiše program koji štampa sve brojeve od 1 do 10. Retko ko bi trepnuo dvaput pre nego što bi smislio nešto poput:
Code:
for(int i=1; i =10; i++)
printf("%dn", i);
Ajde sad da probamo da isto to napravimo, samo rekurzivno. Ideja je da se napravi funkcija koja uradi parčence posla a ostatak svede na sebe, samo malo manju. Ovde nije preterano teško da se sredi ispis. Brojeve od 1 do 10 ispisaćemo tako što ispišemo prvo 1, a zatim ispišemo sve ostale (od 2 do 10). Kada ova dva koraka posmatramo zajedno, treba da dobijemo funkciju koja je ista kao drugi korak, samo malo „veća“. Nije teško da se vidi da je ta funkcija nešto kao: ispisi(int i). Ona treba da ispiše sve brojeve od i do 10.
Nezgodan deo je u tome što naša funkcija ispisi() nekako lebdi u vazduhu. Poziva se na samu sebe, deluje malo kao baron Minhauzen koji pokušava da se izvuče iz živog blata vukući se za čizme. Da bismo rešili ovaj „konflikt“ moramo da funkciju zakačimo za nešto realno. Kazaćemo da funkcija ispisi(10) ispisuje samo 10 i završava sa radom.
Ovim smo našli sva tri bitna sastojka odozgo: početni uslov (to je poziv ispisi(10)), induktivnu hipotezu (imamo funkciju ispisi(i) koja ispisuje sve brojeve od i do 10) i induktivni korak (ispisi(i) se može izraziti kao ispisivanje broja i i zatim pozivanje funkcije ispisi(i+1)). Kad ove tri stvari objedinimo u program, dobijamo:
Code:
void ispisi(int i) {
printf("%dn", i);
if (i 10)
ispisi(i+1); // ispisi sve brojeve od i+1 do 10
}
E sad nadam se da nećete da mi se mnogo smejete zbog ovog ekstra glupog primera. Dabome da niko pri zdravoj pameti ne bi ovako napisao program koji broji od 1 do 10. Probajte da sagledate obrt: šta se dešava kada probamo da razumemo šta radi prvi primer? Nema mnogo pomoći nego da sagledamo svaku iteraciju ponaosob. Pošto petlja ide od 1 do 10 i telo je prilično jednostavno, neće biti problem da se isprati. Šta međutim kada je gornja granica 10000? Šta ako u telu petlje imamo nešto više od printfa? Ko će to sve da zapamti? (U stvari ispravan način za razumevanje petlje svodi se na to da se „vaskrsne“ rekurzija iz iteracije pa onda opet „podmiti“ indukcija da odradi prljavi posao, o tome je zamalo bilo reči pre neki dan u forumu C/C++.)
S druge strane, rekurzivna varijanta je „otporna“ na sva pomeranja granice. Razumevanje programa se ne menja sa promenom one desetke s početka: stavite 10000 umesto 10 ali ćete i dalje da koristite samo tri sastojka da biste razumeli funkciju.
Dakle, svaki program je bio rekurzija kad je bio mali, bez obzira da li je tu korišćeno „dinamičko programiranje“ ili nekakvo drugo.
Otkud onda dinamičko programiranje? Izraz verovatno dolazi iz vremena pre pravog „kompjuterskog“ programiranja. Slično kao što linearno programiranje nema posebne veze sa programskim jezicima itd, već je valjda neka matematička zezalica. Evo i zašto to mislim: jednom sam tako čitao neku knjigu iz automatike. U jednom delu se govori o nekakvom sistemu koga treba prevesti iz jednog stanja u drugo, uz minimalan utrošak energije (dakle recimo uz najmanju potrošnju struje ili tako nečeg sličnog, valjda je otud jasno što se inženjeri cimaju oko toga). Gle čuda, metoda za to zove se upravo dinamičko programiranje. (a još uvek smo negde na početku 20. veka, dakle nema nikakve šanse da je izmišljator metode imao računare na umu!)
Tamo je objašnjeno otprilike da dinamičko programiranje koristi nekakav „princip optimalnosti“ koji kaže: ako između početnog i krajnjeg stanja postoji najbolja putanja, ako se sistem jednom nađe na najboljoj putanji (bez obzira kako je dotle došao), od te tačke na dalje, mora da se kreće po njoj da bi i ceo put bio najbolji mogući. Štos koji se koristi da se reši stvar će verovatno da vam se učini poznat: krene se od
krajnje tačke putanje i nekako, na mišiće, izračuna sam kraj te optimalne putanje. Zatim se izmaknemo još malo unazad i opet na mišiće izračunamo, ali samo deo putanje koji nas od te tačke vodi do malopre izračunate među-tačke. Princip optimalnosti se brine da, kad jednom izađemo na pravi put, sve ostalo klizi kako treba. Malo po malo, računajući parče po parče puta i krećući se unazad sve vreme i koristeći „princip optimalnosti“, na kraju dolazimo do početne tačke. Put kog smo (unazad) ocrtali od cilja do starta je ta najbolja putanja.
E sad, programi koji koriste sličnu ideju su (kao) to dinamičko programiranje. Dakle ima tu rekurzije (pošto je jelte ima u svakom programu), ali ima i još malo više. Sad, da li je ime nesrećno ili ne, ne raspravljam, po knjigama se dobro ukopalo i teško da će skoro neko uspeti da ga odatle pomeri.
I napokon da se vratimo na zadatak posle ove digresije.
Rekoh već da nam za rešenje trebaju samo tri elementa. Mali problem je što na početku pojma nemam kako će ta tri elementa da izgledaju. Zato ću probati da stvar rešim postavljajući (nadam se prava) pitanja u nadi da ću nekako uspeti da napipam koji su pravi početni uslov, induktivna hipoteza i induktivni korak.
Glavni zadatak teroriste (jeste bez veze postavka, šta ćemo...) jeste zapravo da sruši sprat broj 1 na najjeftiniji mogući način.
Da vidimo prvo kako da se sruši sprat i po kojoj ceni, posle ćemo da vidimo šta je sa najjeftinijim rušenjem. Postoje tri načina:
- da se izminira sam sprat, u kom slučaju rušenje košta Ci;
- da se sa gornjih spratova dopremi dovoljno vode;
- da se uradi i jedno i drugo.
Treća varijanta otpada pošto sigurno košta više od primene bilo varijante 1 ili varijante 2 ponaosob.
Što se tiče varijante 2, ona košta najmanje onoliko kolika je ukupna najmanja cena rušenja svih spratova iznad ovog, a koji u zbiru imaju dovoljno vode da sruše ovaj sprat. Ako je ta cena manja od Ci, onda ovaj sprat ne miniramo, već samo čekamo da se voda sruči. Cena miniranja ovog sprata onda postaje 0. Prosto biramo između varijanti 1 i 2 onu koja manje košta. Pošto postoje samo dve mogućnosti za rušenje sprata, ako izaberemo jevtiniju, sigurno smo izabrali minimalnu.
Primetite da se ovde upravo pojavio jedan deo induktivne hipoteze: da bismo izračunali najmanju cenu za miniranje ovog sprata, potrebno nam je da nekako znamo najmanje cene za miniranje gornjih spratova.
Međutim, da bismo to sračunali uveli smo još par pretpostavki koje nam sad štrče, a to je da znamo
koliko spratova iznad moramo da imamo srušene (bez obzira na koji način, dovoljno je da znamo da se sprat „minimalno“ srušio, metod 1 ili 2 nebitno je!) kao i da znamo koliki je zbir cena rušenja tih spratova kao i da znamo koliko vode ukupno ima u njima.
Dakle u principu smo rešili minimalno rušenje sprata, sad još treba da sredimo ove novouvedene stvari. I one mogu da se reše rekurzivno, a njihove induktivne hipoteze ćemo da sastavimo sa početnom. To se zove ojačavanje (
strengthening) induktivne hipoteze (vidite gorepomenutu knjigu od Manbera). Prosto rečeno: moramo u jednoj petlji da sračunamo više od jedne stvari.
Negde gore ste primetili da nam na par mesta trebaju zbirovi nekakvih veličina od sprata a do sprata b (cena i količina vode će se računati na taj način). Ovaj podproblem se lako reši ako ubacimo induktivnu hipotezu da znamo koliki je zbir recimo svih količina vode od sprata x do sprata N. Neka je to recimo V(x). Količinu vode od sprata a do sprata b ćemo onda lako da sračunamo kao V(b) - V(a), ako je b a. Slično uradimo i sa cenom; obe stvari pomerimo u induktivnu hipotezu.
Inventar:
Induktivna hipoteza:
Za sprat i N znamo:
- zbir minimalnih cena rušenja svih spratova od i+1 do N
- zbir količina vode svih spratova od i+1 do N
Početni uslov:
za sprat N znamo:
- minimalna cena rušenja svih spratova iznad je 0 (jer iznad nema ničega)
- ukupan zbir količina vode svih spratova iznad je 0 (jer iznad nema ničega)
Da bismo sastavili ceo algoritam treba nam još da napravimo induktivni korak. On mora da bude takav da, pošto se izvrši, saznamo:
- zbir minimalnih cena rušenja svih spratova od i do N
- zbir količina vode svih spratova od i do N
Induktivni korak:
Drugi deo lako računamo sabirajući zbir voda sa svih spratova od i+1 do N sa Wi. To je O(1).
Prvi deo je malo nezgodan, jer treba da lociramo najbliži sprat j iznad, takav da kada se saberu količine vode na spratovima između i+1 i j, to sve bude veće od limita Li na ovom spratu. Pošto je zbir količina vode od i+1 ka N monotono rastući, ovaj sprat može da se pronađe binarnom pretragom. Pošto zbir količina vode može direktno da se pronađe kao razlika zbirova količine voda, onda nam za to treba samo O(1), dobili smo to vrlo jeftino. Ostaje samo složenost binarne pretrage, O(log(N-i)) = O(logN).
Kada smo našli taj sprat iznad, uporedimo cenu rušenja sprata i sa cenom „urušavanja“ sprata pomoću vode. Na osnovu toga izaberemo varijantu rušenja 1 ili 2, zavisno koja je jeftinija.
Time smo završili induktivni korak i opisali sva tri bitna elementa programa. Nije zgoreg još jedna provera da sve pasuje (nisam proveravao, slobodno me izrešetajte ako sam nešto omanuo!).
Dakle, ako sa izvršavanjem algoritma krenemo od sprata N ka spratu 1, kada stignemo do 1 i završimo, znaćemo:
- zbir minimalnih cena rušenja svih spratova od i do N
- zbir količina vode svih spratova od i do N
Za minimalnu cenu nam treba samo da oduzmemo min. ukupne cene rušenja od 2 do N od min ukupne cene rušenja od 1 do N.
Na kraju, procena složenosti:
- induktivni korak se izvšava N puta, jednom za svaki od N spratova.
- složenost induktivnog koraka zavisi od i, ali nije veća od složenosti koraka za sprat 1, gde je otprilike O(logN): većina operacija je O(1) pošto smo koristili induktivnu hipotezu da svedemo sva računanja na minimum; jedini korak koji „iskače“ je ona binarna pretraga koja je O(logN). Kada saberemo tih par O-ova dobijamo samo O(logN).
- dakle, ukupna složenost je manja od N O(logN), što je ukupno O(NlogN).
Nadam se da nisam baš mnogo lupio...
f
