Kurs Java Podstawy - rozszerzony

Projektowanie algorytmów : Programowanie dynamiczne

Programowanie dynamiczne – definicyjnie, jest to tabelaryczny sposób rozwiązywania problemów, które dają się sformułować rekurencyjnie, jednak bez użycia rekurencji w samym procesie implementacji.

 

1. Programowanie dynamiczne w praktyce

2. Przykładowa implementacja rekurencyjna

3. Ten sam algorytm, z wykorzystaniem programowania dynamicznego

4. Porównanie czasowe

 

1. Programowanie dynamiczne

W praktyce jest to pewne udoskonalenie funkcji rekurencyjnych tak, aby pewnych rzeczy nie liczyć wielokrotnie, lecz korzystać z dotychczasowych osiągnięć pracującej funkcji.

Ideą, tego sposobu tworzenia algorytmów jest zmniejszenie obciążenia wynikającego z implementacji rekurencji.

 

2. Implementacja rekurencyjna

Jako przykład wykorzystamy słynny ciąg liczb Fibonacciego.

Najbardziej podstawowa implementacja rekurencyjna, jaką można znaleźć wygląda tak:

 

public static long fib1(int arg) {
 if ((arg==1)||(arg==2)) return 1;
 else return fib1(arg-1)+fib1(arg-2);
}

 

Jest to implementacja standardowego algorytmu wyznaczania wyrazów Fibonacciego. Jednak nie jest ona zbytnio efektywna. Przyjrzyjmy się, jak dużego czasu potrzebuje, aby wygenerować pierwsze 47 wyrazów:

 

fibonacci

 

No właśnie - czy jest to duży czas czy mały?

 

3. Implementacja - programowanie dynamiczne

Gdyby wykorzystać idee programowania dynamicznego, ten sam algorytm (a raczej jego implementacja) mogłaby wyglądać tak:

public static long fibo2(int arg) {
 if ((arg == 1) || (arg == 2))
   return 1;
 long[] F = new long[48];
 F[0] = 0;
 F[1] = 1;
 int i = 0;
 for (i = 2; i F[i] = F[i - 1] + F[i - 2];
 }
return F[i - 1];
 }

 

W tym przypadku czas potrzebny na obliczenie pierwszych 47 wyrazów ciągu wygląda tak:

 

Fibonacci z wykorzystaniem tablicy

 

4. Podsumowanie

A więc podsumowując, potencjalnie bardziej skomplikowana implementacja, daje nam czas o 18188 razy lepszy.

Powyższy przykład jest nieco trywialny, jednak pozwala wykazać, że (często bardzo wygodne) korzystanie z rekurencji, można znacznie "odchudzić", korzystając z założeń programowania dynamicznego.

 

Przykładowy program, gdzie możemy przetestować powyższe funkcje:

public class fib2 {

    public static void main(String[] args) {

        long time1 = System.nanoTime();

        for(int i=2; i<=154; i++)
        {
            System.out.println(i + " wyraz: " + fibo2(i));
        }

        long time2 = System.nanoTime();
        System.out.println("Całkowity czas obliczeń: " + (time2-time1)/1000000 + " milisekund");

    }

    public static long fibo2(int arg) {
        if ((arg == 1) || (arg == 2))
            return 1;

        long[] F = new long[155];

        F[0] = 0;
        F[1] = 1;

        int i = 0;

        for (i = 2; i <= arg; i++) {
            F[i] = F[i - 1] + F[i - 2];
        }

        return F[i - 1];
    }

}

Komentarze

Damian

Przecież to jest zwykłe zastąpienie rekurencji iteracją i to jeszcze niezbyt ładne, bo pamięć jest deklarowana dla 155 elementów, a potrzebujemy jej na upartego tylko dla 2.

Sławek Ludwiczak

Istotą problemu jest to gdzie przechowywane są dane. W przypadku np Fibonacciego i klasycznej rekurencji pokazanej wyżej trzeba pamiętać, że może i wykorzystujemy tylko dwie zmienne, tylko te 150 poprzednich wartości jest odkładanych na stosie - nie trudno sprawdzić, że dla większych wartości funkcja powoduje dosyć szybkie przepełnienie stosu, co w przypadku iteracji nie wystąpi nawet przy ogromnych danych. Wykorzystanie pamięci, której zazwyczaj w komputerze i tak jest spory nadmiar nie jest żadną wadą.
Można też połączyć rekurencję z iteracją w tzw. rekurencji ogonowej, gdzie dodajemy do funkcji dodatkowe parametry, w których na bieżąco przekazujemy wynik poprzedniej iteracji, przez co na stosie nie jest odkładanych tyle wartości.

Daniel

Wydaje mi się, że Damianowi raczej chodziło o zbędne tablicowanie pośrednich wartości kolejnych iteracji w tak przedstawionym zadaniu. W algorytmie iteracyjnym wystarczą w zasadzie dwie zmienne jak wspomniał Damian. Tablicowanie korzystne będzie chyba tylko jedynie przy wielokrotnym sprawdzaniu różnych wartości wyrazów ciągu Fibonacciego w trakcie jednego uruchomienia programu.

prezco

a co to za pętla ? pkt.3.
...
for (i = 2; i F[i] = F[i - 1] + F[i - 2];
}
return F[i - 1];
}

Gombal

Też się własnie nad tym zastanawiam :P

jDevel

Taka pętla powstaje w skutek położenia kawy na klawiaturę celem zaznaczenia tekstu oraz naciśnięcia delete :P

Amadeuszx

Czemu akurat tablica do 154 skoro 93 wyraz jest już poza zakresem long?