Dinamičko programiranje

Dinamičko programiranje je metod kojim se smanjuje vreme izvršavanja onih problema u kojima se zahteva traženje optimalne podstrukture i koji imaju potprobleme koji se ponavljaju, kao što će biti opisano u nastavku. Ovaj pojam je uveo matematičar Ričard Belman 1953. godine.

Pregled

Pojam optimalna podstruktura označava traženje optimalnih rešenja potproblema i njihovo korišćenje u cilju traženja optimalnog rešenja celokupnog problema. Na primer, najkraći put do datog čvora (označimo ga kao krajnji) od proizvoljnog čvora u acikličnom grafu, može se izračunati tako što se najpre izračuna najkraći put od krajnjeg čvora do njegovih susednih, zatim isti princip primenimo na njegove susede, itd. Dakle, problem koji ima optimalnu podstrukturu se može rešiti u sledeća tri koraka:

1. Razbiti problem na manje potprobleme.
2. Rešiti date potprobleme koristeći ova tri koraka rekurzivno.
3. Iskoristiti pronađena optimalna rešenja potproblema kako bi se našlo optimalno rešenje glavnog problema.

Potprobleme je potrebno deliti na pot-probleme, sve dok se ne dođe do jednostavnih slučaja koje je jednostavno rešiti.

Za razliku od nekih algoritama u kojima se pojavljuju potproblemi koji se ponavljaju, kod dinamičkog programiranja, jedan potproblem se rešava samo jednom. Na primer, u Fibonačijevom nizu F₃ = F₁ + F₂ i F₄ = F₂ + F₃ - računanje svakog broja zahteva nalaženje F₂. Kako su F₃ i F₄ potrebni za nalaženje F₅, naivnim pristupom bi za računanje F₅ bilo potrebno nalaženje F₂ nekoliko puta. Kada se potproblemi ponavljaju više puta, naivnim pristupom se često izgubi dosta vremena na traženje njihovih optimalnih rešenja, koji su već rešeni.

Kako bi se ovo izbeglo, potrebno je sačuvati rešenja onih problema koji su već rešeni, kako bi se mogli kasnije iskoristiti. Ovo se još naziva i memoizacija. Ukoliko je očigledno da rešeni potproblemi nisu više potrebni, mogu se odbaciti kako bi se sačuvao memorijski prostor.

Dinamičko programiranje se koristi kod:

• Potproblema koji se ponavljaju
• Optimalne podstrukture
• Memoizacije.

Ovaj algoritam koristi najčešće jedan od sledeća dva pristupa:

• Odozgo nadole: Problem se rastavi na potprobleme, potproblemi se reše i pamte se njihova rešenja, u slučaju njihove kasnije upotrebe. Ovaj pristup predstavlja kombinovanje rekurzije i memoizacije.
• Odozdo nagore: Svi potproblemi se redom rešavaju i koriste za nalaženje većih. Ovaj pristup je bolji zbog čuvanja memorijskog prostora na steku, ali je ponekad teško odrediti koji su sve potproblemi potrebni za traženje datog.

Primeri

Fibonačijev niz

Naivna implementacija funkcije za traženje n-tog člana Fibonačijevog niza se bazira direktno na matematičkoj definiciji:

   function fib(n)
       if n = 0 or n = 1
           return n
       else
           return fib(n − 1) + fib(n − 2)

Treba primetiti da, ako se pozove funkcija fib(5), manje funkcije se pozivaju veći broj puta, što raste eksponencijalno:

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

Ako se iskoristi pristup odozgo nadole, tj. primeni memoizacija, tada se potproblemi rešavaju tačno jednom, jer se njihove vrednosti pamte:

   var m := map(0 → 1, 1 → 1)
   function fib(n)
       if n not in keys(m)
           m[n] := fib(n − 1) + fib(n − 2)
       return m[n]

Međutim, koristeći pristup odozdo nagore, linearna prostorna složenost se može preobraziti u konstantnu:

   function fib(n)
       var previousFib := 1, currentFib := 1
       repeat n − 1 times
           var newFib := previousFib + currentFib
           previousFib := currentFib
           currentFib  := newFib
       return currentFib

U oba poslednja slučaja, samo se jednom računa fib(2), da bi se zatim iskoristio za nalaženje fib(4) i fib(3), umesto što bi se računao svaki put kada se pozove nova funkcija.

Šahovska tabla

Neka je data šahovska tabla dimenzija n × n i funkcija c(i, j) koja vraća određenu vrednost za dato polje i,j (i označava red, a j kolonu). Uzmimo, na primer, da je n = 5.

  +---+---+---+---+---+
5 | 6 | 7 | 4 | 7 | 8 |
  +---|---|---|---|---+
4 | 7 | 6 | 1 | 1 | 4 |
  +---|---|---|---|---+
3 | 3 | 5 | 7 | 8 | 2 |
  +---|---|---|---|---+
2 | 2 | 6 | 7 | 0 | 2 |
  +---|---|---|---|---+
1 | 7 | 3 | 5 | 6 | 1 |
  +---+---+---+---+---+
    1   2   3   4   5

Dakle, c(1, 3) = 5.

Neka se u donjoj koloni nalazi kralj koji treba da stigne do gornje kolone, tako što će preći najkraći put (suma kvadrata na putu do gornje kolone treba da bude najmanja). Pod pretpostavkom da se kralj može pomerati samo napred, dijagonalno levo ili dijagonalno desno, on iz polja (1,3) može preći na (2,2), (2,3) ili (2,4).

  +---+---+---+---+---+
5 |   |   |   |   |   |
  +---|---|---|---|---+
4 |   |   |   |   |   |
  +---|---|---|---|---+
3 |   |   |   |   |   |
  +---|---|---|---|---+
2 |   | x | x | x |   |
  +---|---|---|---|---+
1 |   |   | O |   |   |
  +---+---+---+---+---+
    1   2   3   4   5

Ovaj problem zahteva traženje optimalne podstrukture, odnosno rešavanje celokupnog problema se zasniva na traženju njegovih potproblema. Neka je funkcija q(i, j) definisana na sledeći način:

q(i, j) = najkraći put do polja (i, j).

Lako se uočava da je vrednost funkcije q(i, j) jednaka minimalnoj vrednosti od tri polja ispod datog (to su polja sa kojih se jedino do njega može i stići) plus c(i, j). Na primer:

  +---+---+---+---+---+
5 |   |   |   |   |   |
  +---|---|---|---|---+
4 |   |   | A |   |   |
  +---|---|---|---|---+
3 |   | B | C | D |   |
  +---|---|---|---|---+
2 |   |   |   |   |   |
  +---|---|---|---|---+
1 |   |   |   |   |   |
  +---+---+---+---+---+
    1   2   3   4   5

$q(A)=\min(q(B),\;q(C),\;q(D))\;+\;c(A)$

Sada, q(i, j) se može definisati kao:

$q(i,j)=\left\{{\begin{matrix}\infty &j<1{\mbox{ ili }}j>n\\c(i,j)&i=1\\\min(q(i-1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j)&{\mbox{inace}}\end{matrix}}\right.$

Ovo se može predstaviti pseudokodom:

function minCost(i, j)
    if j < 1 or j > n
        return infinity
    else if i = 1
        return c(i, j)
    else    
        return min(minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1)) + c(i, j)

Lako se uočava da navedena funkcija ne određuje najkraći put, već samo njegovu vrednost. Najpre, može se primeniti pristup odozdo nagore i iskoristiti dvodimenzionalni niz q[i, j] umesto funkcije. Zatim, korišćenjem još jednog niza p[i, j], za pamćenje otkuda trenutni najkraći put dolazi, može se odrediti i najkraći put. To se može prikazati kodom na sledeći način:

 function computeShortestPathArrays()
     for x from 1 to n
         q[1, x] := c(1, x)
     for y from 1 to n
         q[y, 0]     := infinity
         q[y, n + 1] := infinity
     for y from 2 to n
         for x from 1 to n
             m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
             q[y, x] := m + c(y, x) 
             if m = q[y-1, x-1]
                 p[y, x] := -1
             else if m = q[y-1, x]
                 p[y, x] :=  0
             else
                 p[y, x] :=  1

Sada je lako naći minimum i ispisati najkraći put.

 function computeShortestPath()
     computeShortestPathArrays()
     minIndex := 1
     min := q[n, 1] 
     for i from 2 to n 
         if q[n, i] < min
             minIndex := i
             min := q[n, i]
     printPath(n, minIndex)

 function printPath(y, x)
     print(x)
     print("<-")
     if y = 2
         print(x + p[y, x])
     else
         printPath(y-1, x + p[y, x])

Algoritmi koji koriste dinamičko programiranje

• Najduži zajednički podniz
• CYK algoritam
• Belman-Fordov algoritam
• Flojd-Voršalov algoritam
• Problem ranca
• Množenje matrica
• Najduži rastući podniz

Literatura

• Thomas Cormen, Charles Leiserson, Ronald Rivest i Clifford Stein, 2001. Predstavljanje algoritama, 2nd ed. MIT Press & McGraw-Hill. ISBN 978-0-262-03293-3. Especially chpt. 15: 323-69.
• Nancy Stokey, Robert Lucas i Edward Prescott, 1989. Rekurzivne metode. Harvard University Press.
• Dimitri P. Bertsekas, 2000. Dinamičko programiranje i optimalno kontrolisanje, 2nd ed. Athena Scientific. ISBN 978-1-886529-09-0. Vols. 1 and 2.

Spoljašnje veze

• Dinamičko programiranje
• Dinamičko programiranje - tutorijal Arhivirano na sajtu Wayback Machine (7. februar 2006)
• Primeri
• Primena dinamičkog programiranja na polju makroekonomije
• Tutorijal na TopCoder-u
• Primeri za primenu dinamičkog programiranja u ekonomiji Arhivirano na sajtu Wayback Machine (5. decembar 2008)