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 otpimalnih 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-potrobleme, sve dok se ne dođe do jednostavnih slučaja koje je jednostavno rešiti.

Za razliku od nekih algoritama u kojima se pojavaljuju 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 otimalnih 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 na dole: 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 na gore: 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 na dole, 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 na gore, 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 funckija 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 funcije 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 preudokodom:

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 na gore 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

Vanjske veze

• Dinamičko programiranje
• Dinamičko programiranje - tutorijal
• Primeri
• Primena dinamičkog programiranja na polju makroekonomije Arhivirano 2006-06-14 na Wayback Machine-u
• Tutorijal na TopCoder-u
• Primeri za primenu dinamičkog programiranja u ekonomiji Arhivirano 2008-12-05 na Wayback Machine-u

Izvori

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