Динамичко програмирање

Динамичко програмирање је метод којим се смањује време извршавања оних проблема у којима се захтева тражење оптималне подструктуре и који имају потпроблеме који се понављају, као што ће бити описано у наставку. Овај појам је увео математичар Ричард Белман 1953. године.

Појам оптимална подструктура означава тражење оптималних решења потпроблема и њихово коришћење у циљу тражења оптималног решења целокупног проблема. На пример, најкраћи пут до датог чвора (означимо га као крајњи) од произвољног чвора у ацикличном графу, може се израчунати тако што се најпре израчуна најкраћи пут од крајњег чвора до његових суседних, затим исти принцип применимо на његове суседе, итд. Дакле, проблем који има оптималну подструктуру се може решити у следећа три корака:

1. Разбити проблем на мање потпроблеме.
2. Решити дате потпроблеме користећи ова три корака рекурзивно.
3. Искористити пронађена оптимална решења потпроблема како би се нашло оптимално решење главног проблема.

Потпроблеме је потребно делити на пот-проблеме, све док се не дође до једноставних случаја које је једноставно решити.

За разлику од неких алгоритама у којима се појављују потпроблеми који се понављају, код динамичког програмирања, један потпроблем се решава само једном. На пример, у Фибоначијевом низу F₃ = F₁ + F₂ и F₄ = F₂ + F₃ - рачунање сваког броја захтева налажење F₂. Како су F₃ и F₄ потребни за налажење F₅, наивним приступом би за рачунање F₅ било потребно налажење F₂ неколико пута. Када се потпроблеми понављају више пута, наивним приступом се често изгуби доста времена на тражење њихових оптималних решења, који су већ решени.

Како би се ово избегло, потребно је сачувати решења оних проблема који су већ решени, како би се могли касније искористити. Ово се још назива и мемоизација. Уколико је очигледно да решени потпроблеми нису више потребни, могу се одбацити како би се сачувао меморијски простор.

Динамичко програмирање се користи код:

• Потпроблема који се понављају
• Оптималне подструктуре
• Мемоизације.

Овај алгоритам користи најчешће један од следећа два приступа:

• Одозго надоле: Проблем се растави на потпроблеме, потпроблеми се реше и памте се њихова решења, у случају њихове касније употребе. Овај приступ представља комбиновање рекурзије и мемоизације.
• Одоздо нагоре: Сви потпроблеми се редом решавају и користе за налажење већих. Овај приступ је бољи због чувања меморијског простора на стеку, али је понекад тешко одредити који су све потпроблеми потребни за тражење датог.

Наивна имплементација функције за тражење n-тог члана Фибоначијевог низа се базира директно на математичкој дефиницији:

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

Треба приметити да, ако се позове функција fib(5), мање функције се позивају већи број пута, што расте експоненцијално:

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))

Ако се искористи приступ одозго надоле, тј. примени мемоизација, тада се потпроблеми решавају тачно једном, јер се њихове вредности памте:

   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]

Међутим, користећи приступ одоздо нагоре, линеарна просторна сложеност се може преобразити у константну:

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

У оба последња случаја, само се једном рачуна fib(2), да би се затим искористио за налажење fib(4) и fib(3), уместо што би се рачунао сваки пут када се позове нова функција.

Нека је дата шаховска табла димензија n × n и функција c(i, j) која враћа одређену вредност за дато поље i,j (i означава ред, а j колону). Узмимо, на пример, да је 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

Дакле, c(1, 3) = 5.

Нека се у доњој колони налази краљ који треба да стигне до горње колоне, тако што ће прећи најкраћи пут (сума квадрата на путу до горње колоне треба да буде најмања). Под претпоставком да се краљ може померати само напред, дијагонално лево или дијагонално десно, он из поља (1,3) може прећи на (2,2), (2,3) или (2,4).

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

Овај проблем захтева тражење оптималне подструктуре, односно решавање целокупног проблема се заснива на тражењу његових потпроблема. Нека је функција q(i, j) дефинисана на следећи начин:

q(i, j) = најкраћи пут до поља (i, j).

Лако се уочава да је вредност функције q(i, j) једнака минималној вредности од три поља испод датог (то су поља са којих се једино до њега може и стићи) плус c(i, j). На пример:

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

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

Сада, q(i, j) се може дефинисати као:

${\displaystyle 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.}$

Ово се може представити псеудокодом:

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)

Лако се уочава да наведена функција не одређује најкраћи пут, већ само његову вредност. Најпре, може се применити приступ одоздо нагоре и искористити дводимензионални низ q[i, j] уместо функције. Затим, коришћењем још једног низа p[i, j], за памћење откуда тренутни најкраћи пут долази, може се одредити и најкраћи пут. То се може приказати кодом на следећи начин:

 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

Сада је лако наћи минимум и исписати најкраћи пут.

 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])

• Најдужи заједнички подниз
• CYK алгоритам
• Белман-Фордов алгоритам
• Флојд-Воршалов алгоритам
• Проблем ранца
• Множење матрица
• Најдужи растући подниз

• Thomas Cormen, Charles Leiserson, Ronald Rivest и Clifford Stein, 2001. Представљање алгоритама, 2nd ed. MIT Press & McGraw-Hill. ISBN 978-0-262-03293-3. Especially chpt. 15: 323-69.
• Nancy Stokey, Robert Lucas и Edward Prescott, 1989. Рекурзивне методе. Harvard University Press.
• Dimitri P. Bertsekas, 2000. Динамичко програмирање и оптимално контролисање, 2nd ed. Athena Scientific. ISBN 978-1-886529-09-0. Vols. 1 and 2.

• Динамичко програмирање
• Динамичко програмирање - туторијал Архивирано на веб-сајту Wayback Machine (7. фебруар 2006)
• Примери
• Примена динамичког програмирања на пољу макроекономије
• Туторијал на TopCoder-у Архивирано на веб-сајту Wayback Machine (23. април 2006)
• Примери за примену динамичког програмирања у економији Архивирано на веб-сајту Wayback Machine (5. децембар 2008)