Projektowanie algorytmów : Programowanie dynamiczne
Spis treści
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.
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ówjest zmniejszenie obciążenia wynikającego z implementacji rekurencji.
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.
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];
}
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];
}
}
Dyskusja i komentarze
Masz pytania do tego wpisu? Może chcesz się podzielić spostrzeżeniami? Zapraszamy dyskusji na naszej grupie na Facebooku.
Poniżej znajdziesz archiwalne wpisy z czasów, gdy strona była jeszcze hobbystycznym blogiem.
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?