post_ico5

Programowanie dynamiczne

Po dłuższej przerwie w pisaniu artykułów związanej z nadmiarem pracy i nauki zaprezentuję jedną z podstawowych technik optymalizacji algorytmów wykorzystujących rekurencję. Programowanie dynamiczne (bo o nim mowa) umożliwia znaczne przyspieszenie rozwiązywania problemów wymagających dużej ilości wywołań funkcji rekurencyjnej.


Programowanie dynamiczne opiera się na podziale rozwiązywanego problemu na podproblemy względem kilku parametrów. W odróżnieniu od techniki dziel i zwyciężaj podproblemy w programowaniu dynamicznym nie są na ogół rozłączne, ale musi je cechować własność optymalnej podstruktury. W celu wykorzystania programowania dynamicznego musimy sprowadzić nasz problem do równania rekurencyjnego.

Najprostszym przykładem optymalizacji za pomocą programowania dynamicznego jest wyliczanie n-tego wyrazu ciągu Fibonacciego.

Klasyczna funkcja rekurencyjna wygląda tak:

function fib($n) {
    if($n==0)
	   return 0;
    if($n==1)
        return 1;
    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):

function fib(&$dyn, $n) {
    if(sizeof($dyn)<=1) {
        $dyn[0]=0;
        $dyb[1]=1;
    }
    if($n>=sizeof($dyn)) {
        for($i=sizeof($dyn);$i<=$n;$i++) { // za pomoca petli wpisujemy odpowiednie wartosci w poszczegolne komorki tablicy
            $dyn[$i]=$dyn[$i-2] + $dyn[$i-1];
        }
    }
    return $dyn[$n];
}

W powyższej funkcji, wartości kolejnych wyrazów ciągu zapamiętujemy w tablicy $dyn[] – dzięki temu nie musimy obliczać jej za każdym razem. Raz obliczoną wartość wykorzystujemy do obliczenia kolejnych wyrazów.

Dla: fib(2), fib(30), fib(20), fib(4) skrypt wykorzystujący funkcję rekurencyjną wykonuje się w 0.69s. Natomiast skrypt używający programowanie dynamiczne – 0.0001s. Jak widać jest to różnica rzędu kilku wielkości, a liczymy tylko 4 wyrazy(!).

Podsumowując, idea programowania dynamicznego polega na zapamiętywaniu poszczególnych wywołań rekurencji, dzięki czemu nie musimy ich liczyć na nowo za każdym razem. Odpowiednie wykorzystanie tej techniki zezwala na znaczną optymalizację niektórych problemów algorytmicznych.

Co sądzisz o wpisie?
BeżnadziejnySłabyŚredniDobryBardzo dobry (Brak ocen, bądź pierwszy!)
Loading...