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

Из пројекта Википедија

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

Садржај

1 Преглед
2 Примери
- 2.1 Фибоначијев низ
- 2.2 Шаховска табла
3 Алгоритми који користе динамичко програмирање
4 Спољашње везе
5 Референце

[уреди] Преглед

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

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

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

За разлику од неких алгоритама у којима се појаваљују потпроблеми који се понављају, код динамичког програмирања, један потпроблем се решава само једном. На пример, у Фибоначијевом низу 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), мање функције се позивају већи број пута, што расте експоненцијално:

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

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

   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

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

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

$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 0262032937. Especially chpt. 15: 323–69.
Nancy Stokey, Robert Lucas и Edward Prescott, 1989. Рекурзивне методе. Harvard Univ. Press.
Dimitri P. Bertsekas, 2000. Динамичко програмирање и оптимално контролисање, 2nd ed. Athena Scientific. ISBN 1886529094. Vols. 1 and 2.

Добављено из "http://sr.wikipedia.org../../../%D0%B4/%D0%B8/%D0%BD/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%BA%D0%BE_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%B8%D1%80%D0%B0%D1%9A%D0%B5.html"

Категорија страница: Алгоритми