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:
# Razbiti problem na manje potprobleme.
# Rešiti date potprobleme koristeći ova tri koraka rekurzivno.
# 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 F3 = F1 + F2 i F4 = F2 + F3 - računanje svakog broja zahteva nalaženje F2. Kako su F3 i F4 potrebni za nalaženje F5, naivnim pristupom bi za računanje F5 bilo potrebno nalaženje F2 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:
# `fib(5)`
# `fib(4) + fib(3)`
# `(fib(3) + fib(2)) + (fib(2) + fib(1))`
# `((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))`
# `(((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  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  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 
* Tutorijal na TopCoder-u  
* Primeri za primenu dinamičkog programiranja u ekonomiji 

## Izvori
* Thomas Cormen, Charles Leiserson, Ronald Rivest i Clifford Stein, 2001. *Predstavljanje algoritama*, 2nd ed. MIT Press & McGraw-Hill. . 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. . Vols. 1 and 2.