Programowanie dynamiczne można zrozumieć na dwa sposoby:
praktyczny i teoretyczny. Ten pierwszy jest znacznie prostszy i wystarcza na
zaliczenie, ale zgłębienie tego drugiego pozwala na konstruowanie samemu
rozwiązań dynamicznych.
Poniższy opis w całości poświęcę teoretycznym
rozważaniom (praktyczne da się jedynie zrobić na konkretnych przykładach). Temat
nie należy do łatwych i trudno się go omawia. Raczej będę go męczyć i dręczyć, i
przejście przez poniższy opis w moim wykonaniu może być bolesny. Dlatego osoby o
słabych nerwach proszone są o opuszczenie strony.
Programowanie dynamiczne daje się zastosować jedynie do
problemów, które mają tzw. własność optymalnej podstruktury. Chodzi tu o to, że
rozwiązując problem "dochodzimy" do pewnego "miejsca" i nasza dalsza droga Z
tego miejsca jest całkowicie niezależna od drogi DO tego miejsca (własność
Markowa :-) ).
Można na tą własność spojrzeć z nieco innej strony. Jeżeli
pewna "droga" (od "początku" do "końca" problemu) rozwiązująca problem jest
drogą najlepszą i zawiera pewne "miejsce" to poddrogi "początek-miejsce" i
"miejsce-koniec" też muszą być najlepsze.
Powyższe ogólne rozważania są najprawdopodobniej niejasne, więc
może podam przykład problemu, który ma własność optymalnej podstruktury.
Konkretnie jest to problem znajdowania najkrótszej ścieżki między dwoma miastami
na mapie.
Jeżeli chcemy dojść z miasta A do miasta B i w jakiejś fazie
pośredniej doszliśmy do miasta C, to nas to mało obchodzi w jaki sposób
doszliśmy do C - ważne jest dla nas jedynie, żeby z C znaleźć jak najkrótszą
drogę do B. Oczywiście jeżeli wiemy, że C należy na najkrótszej drodze z A do B
to nie tylko C-B musi być najkrótsza, ale A-C też (bo gdyby szło skrócić jedną z
tych poddróg, to cała droga też uległa by skróceniu).
Chciałbym już w tym
miejscu zwrócić uwagę, że to nie zawsze miasto C musi leżeć na najlepszej drodze
z A do B. Zawsze trzeba sprawdzić wszystkie (sensowne) drogi z wszystkimi
możliwymi punktami pośrednimi. A w programowaniu dynamicznym chodzi o to, żeby
przeglądając wszystkie drogi bezsensownie nie rozważać dróg ponownie. I dotyczy
to nie tylko miast i dróg, ale wszelkich problemów o tzw. własności wspólnych
podproblemów (o tym później).
Podstawowym pojęciem dotyczącym programowania dynamicznego jest
stan, który oznacza pewne miejsce (o którym tak usilnie wspominałem), do
którego można "dojść" i niezależnie "rozejrzeć się" za najlepszym rozwiązaniem z
tego miejsca. Stan może być charakteryzowany przez jedną lub kilka wartości. W
podanym przeze mnie przykładzie stanem będzie miasto (a konkretnie jego numer).
Stan jednoznacznie określa nam pewien podproblem (dotarcie do celu z miasta
pośredniego) całego problemu (dotarcie do celu z miasta
początkowego).
Każdemu stanowi odpowiada pewna wartość, która zazwyczaj jest
wynikiem gdybyśmy zaczynali od tego stanu (choć nie koniecznie). Te wartości
definiują nam funkcję stanu. W przykładzie z mapą funkcja stanu określa
nam najmniejszą odległość z dowolnego miasta do miasta docelowego.
I
najważniejsze to określić rekurencyjne zależności między stanami (czy
jakkolwiek se to nazwiecie), czyli jak obliczyć wartość funkcji dla pewnego
stanu, znając wartości funkcji dla pewnych innych stanów. To nam określa pewną
kolejność obliczania stanów (to taki skrót myślowy, chodzi mi oczywiście o
obliczanie wartości funkcji dla tych stanów). Nie możemy obliczyć pewnego stanu
jeżeli nie obliczyliśmy wcześniej stanów, od których on zależy.
Należy
wyróżnić pewne stany (bądź stan) początkowe, które mają pewną konkretną wartość
łatwą do obliczenia ręcznie, albo oczywistą (w naszym przykładzie jest to miasto
końcowe, dla którego odległość do miasta końcowego jest oczywiście równa 0).
Mając te stany możemy zabrać się za liczenie stanów, które zależą wyłącznie od
nich. W ten sposób zbiór obliczonych stanów się powiększy i będzie można
obliczyć kolejne stany, uzależnione jedynie od tych z tego zbioru, itd, itd,
itd.
Warto zauważyć, że obliczanie stanów jest równoważne zapuszczeniu
rekurencji (zgodnie z rekurencyjnymi zależnościami między stanami). Tyle że tym
razem nie idziemy w głąb (w dół) drzewa rekurencji, zaczynając od korzenia, a w
górę tego drzewa; czyli tak jakby rozwiązujemy problem od tyłu. Stany początkowe
programowania dynamicznego odpowiadają warunkom końcowym działania rekurencji.
Powiedziałem, że programowanie dynamiczne sprowadza się do
znalezienia funkcji rekurencyjnej, którą należy przerobić od tyłu (od tylca :-))
???). Więc dlaczego by nie zrobić po prostu zwykłego rozwiązania rekurencyjnego?
Jak ktoś chce to może - miłej zabawy.
Oto chodzi, że jak zapuścimy sobie
rekurencję to możemy narobić komputerowi kupę niepotrzebnej roboty. Żeby
rozwiązać problem będzie trzeba rozwiązać (rekurencyjnie) jego podproblemy i
podproblemy tych podproblemów, itd. No i może się tak zdarzyć, że pewien
podproblem i pewien inny podproblem mają taki sam podproblem (a nawet
podproblemy), który będzie rozwiązywany za każdym razem na nowo (czyli
wielokrotnie), a wskutek czego jego podproblemy (i ich podproblemy, ...) będą
też rozwiązywane wielokrotnie i algorytm zazwyczaj staje się wykładniczy.
No
i to jest właśnie własność wspólnych podproblemów, dzięki której programowanie
dynamiczne ma zastosowanie. Algorytmy skonstruowane tą metodą pozwalają na
zapamiętanie (ale umiejętne zapamiętanie) rozwiązań podproblemów, z których
wielokrotnie korzystamy, żeby nie rozwiązywać ich za każdym razem na nowo. Jak
już wcześniej wspomniałem podproblemy odpowiadają stanom i ich rozwiązania
określa (choć nie koniecznie) funkcja stanu.
Weźmy sobie na przykład ciąg Fibonacciego. Wartość N-tego
wyrazu tego ciągu wyraża się powszechnie znanym, rekurencyjnym wzorem
F(N)=F(N-1)+F(N-2), przy czym F(0)=0, F(1)=1. Jeżeli naszym
zadaniem jest znalezienie N-tego wyrazu ciągu Fibonacciego dla danego N, to nic
nie stoi na przeszkodzie, żeby zapuścić rekurencję zgodnie z powyższym wzorem.
Problem leży w tym, że w ten sposób kilkakrotnie będziemy niepotrzebnie liczyć
te same wartości. Np. żeby obliczyć F(6) będzie trzeba obliczyć
F(4) oraz F(5), do którego obliczenia potrzebne będzie ponowne
obliczenie F(4). Oto jak wygląda drzewo wywołań rekurencyjnych, potrzebne
do obliczenia F(5) (prawda, że niepotrzebnie duże?):
To teraz spójrzmy na problem od strony programowania
dynamicznego. Stanami są liczby naturalne - numery wyrazów ciągu Fibonacciego, a
funkcja stanu określa na wartości tych wyrazów. Zależności między stanami są
jednoznacznie zdefiniowane przez rekurencyjny wzór.
Stanem początkowe to
oczywiście 0 (dla którego funkcja przyjmuje wartość 0) oraz 1 (funkcja ma
wartość 1). Znając te stany, możemy oblicz stan 2; znając 1 i 2 można obliczyć
3; ... . Więc widać, że obliczając kolejno stany 0,1,2,3,4,... liczymy każdy z
nich dokładnie raz. Co więcej w tym przypadku nie trzeba zapamiętać wszystkich
stanów, bo wystarczą dwa ostatnie (choć nie zawsze mamy tak dobrze).
Tym
razem zamiast drzewa można sobie narysować "graf zależności stanów" (indukowany
przez rekurencyjne zależności między stanami), który obrazuje kolejność
obliczania stanów. Graf ten jest w rzeczywistości skompaktowanym drzewem
rekurencji (z odwróconymi krawędziami), a co za tym idzie jest znacznie
mniejszy, co widać na załączonym obrazku: