Programowanie dynamiczne - metoda znajdowania rozwiązań problemów optymalizacyjnych podobna do metody „dziel i zwyciężaj” - w metodzie tej zadany problem dzielimy na podproblemy, rozwiązujemy je, a następnie łączymy rozwiązania podproblemów.

Różnice:

• metoda „dziel i zwyciężaj” - wielokrotnie rozwiązuje ten sam problem, wykonuje więc dużo więcej pracy

• programowanie dynamiczne - algorytm oparty na tej metodzie rozwiązuje każdy podproblem tylko jeden raz zapamiętując wynik, unika się w ten sposób wielokrotnych obliczeń dla tego samego podproblemu

Przykład:

Definicja rekurencyjna:

sugeruje zastosowanie techniki „dziel i zwyciężaj”:

long Fib(int n)

{

if (n==0 || n==1) return 1;

return Fib(n-1) + Fib(n-2);

}

Wady:

1. Obliczenie Fib(20) wymaga ponad 14 000 operacji dodawania.

2. Te same podproblemy wykonywane są wielokrotnie, np. Fib(10) wywoływane jest 76 razy.

3. Szybkie zapełnianie stosu.

Odwrócenie kolejności obliczeń, tzn. rozpoczęcie obliczania od małych podproblemów daje algorytm wymagający n - 1 dodawań (czyli 19 dla Fib(20))

long Fib(int n)

{

if (n==0 || n==1) return 1;

else {

long x[]; x[0] = x[1] = 1;

for (int i = 2; i <= n; i++) x[i] = x[i-1] + x[i-2];

}

return x[n];

}

Ponieważ nie trzeba pamiętać wszystkich wyników podproblemów (tylko dwa ostatnie) - nie trzeba używać tablicy:

long Fib(int n)

{

int a, b = 1, f = 1, i;

for (i = 1; i <= n; i++)

{ a = f + b; b = f; f = a; } return f; }

Opracowanie algorytmu programowania dynamicznego

1. Określamy zależność rekurencyjną, która pozwala znaleźć rozwiązanie problemu

2. Rozwiązujemy problem zgodnie z podejściem wstępującym, najpierw rozwiązując mniejsze podproblemy

Kiedy można stosować tę metodę?

1. Problem wykazuje optymalną podstrukturę, jeśli jego optymalne rozwiązanie jest funkcją optymalnych rozwiązań podproblemów; metoda dowodzenia jest następująca: zakładamy, że jest lepsze rozwiązanie podproblemu, po czym pokazujemy, iż to założenie zaprzecza optymalności rozwiązania całego problemu

2. Mówimy, że problem ma własność wspólnych podproblemów, jeśli algorytm rekurencyjny wielokrotnie oblicza rozwiązanie tego samego podproblemu; algorytmy oparte na programowaniu dynamicznym rozwiązują dany podproblem tylko jeden raz i zapamiętują gotowe rozwiązania, które potem wystarczy odczytać w stałym czasie

Jeśli problem wykazuje te dwie własności warto spróbować, czy daje się stosować metoda programowania dynamicznego.

Ponadto:

3. „Rozsądnie mała” przestrzeń istotnie różnych podproblemów

zastosowania techniki programowania dynamicznego

1. Algorytm Floyda określania najkrótszej drogi w grafie (zostanie omówiony w temacie „Grafy”)

2. Najdłuższy wspólny podciąg

3. Mnożenie ciągu macierzy

4. Droga przez tablicę

5. Współczynniki dwumianowe

6. Optymalne drzewa wyszukiwania binarnego

7. Problem komiwojażera

8. Dyskretny problem plecakowy

9. Optymalna triangulacja wielokąta (Cormen, Leiserson, Rivest, rozdz. 16.4.)

10. Wyprowadzanie słowa w gramatyce (Aho, Hopcroft, Ullman)

i wiele, wiele innych

---