Programowanie Dynamiczne

Romualda Laskowska

Zastosowanie rekurencji do rozwiązywania problemów najczęściej ograniczone jest do przypadku, gdy podproblemy są od siebie niezależne. W innym przypadku musimy wielokrotnie rozwiązywać te same podproblemy. Receptą na to może być pamiętanie rozwiązań tych podproblemów, które już zostały rozwiązane. Gdy jest ich niewiele to możemy tak właśnie postąpić, ale gdy jest ich zdecydowanie zbyt wiele? Możemy wówczas zastosować PROGRAMOWANIE DYNAMICZNE. Jest to metoda polegająca na obliczeniu rozwiązań dla wszystkich podproblemów zaczynając od najprostszych.

Przykład 1. Obliczanie symbolu Newtona

Dane: Liczby naturalne n, k.
Wynik:

(1)

\begin{align} {n}\choose{k} \end{align}

Naturalna metoda redukcji problemu obliczenia

(2)

\begin{align} {n}\choose{k} \end{align}

korzysta z zależności

$c2d02458d8c35f11e465c639ba62f081.png$

Powszechnie znanym wzorem na symbol Newtona jest następujący wzór rekurencyjny:

$fd91604e2a264813369476ff6f721816.png$

Zastosowanie metody rekurencyjnej byłoby jednak w tym przypadku nierozważne, ponieważ w trakcie liczenia

(3)

\begin{align} {n-1}\choose{k-1} \end{align}

jak i

(4)

\begin{align} {n-1}\choose{k} \end{align}

wywoływalibyśmy rekurencyjnie procedurę dla tych samych danych (tj. dla n − 2 i k − 1), co w konsekwencji prowadziłoby do tego, że niektóre podproblemy byłyby rozwiązywane wykładniczą liczbę razy.

Za zastosowaniem w tym przypadku programowania dynamicznego przemawia fakt, iż liczba różnych podproblemów jakie mogą pojawić się w trakcie obliczania

(5)

\begin{align} {n}\choose{k} \end{align}

jest niewielka, a mianowicie O(n²). Podobnie jak w metodzie spamiętywania, algorytm dynamiczny oblicza początkowy fragment trójkąta Pascala i umieszcza go w tablicy tab. W przeciwieństwie jednak do poprzedniej metody, która jest implementowana rekurencyjnie, algorytm dynamiczny jest implementowany iteracyjnie.

for ( int i = 1; i<= n; i++)
tab[i][0] = 1;
..................
function symbol(int n,int k){
for (int j = 1; j<=k; j++)
tab[j][j]= 1;
for (int i = j + 1; i<=n; i++)
tab[i][j] = tab[i−1][j−1] + tab[i−1][j];
return tab[n][k];
}

Jak widzimy duża zaletą tej metody jest to, że obliczamy wszystkie wartości symbolu Newtona w zadanym przedziale, zatem po obliczeniu wszystkich wartości możemy tylko odczytywać wyniki z tablicy (jest to bardzo dobra optymalizacja, jeżeli ilości takich sprawdzeń symbolu Newtona byłaby bardzo duża).

Fakt, że metoda programowania dynamicznego oblicza w sposób systematyczny rozwiązania wszystkich podproblemów, pozwala często na poczynienie dodatkowych oszczędności w stosunku do metody spamiętywania. W tym przykładzie możemy znacznie zredukować koszty pamięciowe. Jak łatwo zauważyć, obliczenie kolejnej przekątnej trójkąta Pascala wymaga znajomości jedynie wartości z poprzedniej przekątnej. Tak więc zamiast tablicy n×k wystarcza tablica n×2, a nawet tablica n×1.
Koncepcja: rozwiązuj problem "od końca"

rozwiąż problem dla jednego elementu, przy różnych wartościach parametru sterującego, zapamiętaj wyniki,
dodaj następny element do problemu
zbuduj rozwiązanie problemu powiększonego o nowy składnik, dokonując optymalnego wyboru w oparciu o poprzednio zapisane rozwiązania

Przykład 2: Wyliczanie n-tego wyrazu ciągu Fibonacciego

Klasyczna funkcja rekurencyjna wygląda tak:

unsigned long fib(int n)
{
  if(n <= 1) return n;
  else return fib(n - 2) + fib(n - 1);
}

Jeżeli chcemy obliczyć trzeci wyraz ciągu będziemy mieć następujące wywołanie:

fib(3) = fib(1) + fib(2) = fib(1) + fib(0) + fib(1) = 1 + 0 + 1 = 2

Złożoność czasowa powyższej funkcji rekurencyjnej wynosi O(2n), a więc czas wykonania wzrasta wykładniczo. Co wiąże się z „gwałtownym” wzrostem czasu dla kolejnych wyrazów ciągu. Wykorzystując programowanie dynamiczne możemy obliczyć n-ty wyraz ciągu Fibonacciego wykorzystując algorytm o złożoności czasowej O(n):

int fibonacci(int n) {
    int a, b;
    if(n == 0) return 0;
    a = 0; b = 1;
    for(int i=0; i<(n-1); i++) {
        b += a;
        a = b-a;
    }
    return b;
}

Zadanie do rozwiązania

Bajtek ma k-ulubionych nominałów i w swojej wielkiej śwince-skarbonce przechowuje nieskończenie
wiele bajtomonet każdego ulubionego nominału. Niestety Bajtek popadł w długi i musi zapłacić n
bajtomonet. Jako, ze Bajtek jest słaby jeżeli chodzi o kombinowanie, to poprosił Ciebie o napisanie
programu który poda nominały i liczby monet potrzebnych do spłacenia długu. Ale uważaj! Bajtek
bardzo ceni sobie każdą monetę, dlatego pod groźbą słuchania piosenek Justina Bitona, zażądał byś
zużył jak najmniej monet, bądź wypisał NIE jeżeli niemożliwe jest wydanie reszty za pomocą
danych nominałów.
Przykład:
— dla nominałów [1, 3, 4] i n = 6 - Wynikiem są 2 monety nominału 3
— dla nominałów [3, 4] i n = 13 - Wynikiem jest NIE

Algorytmika