W wielu omawianych w tym wykładzie algorytmach była stosowana zasada "dziel i zwyciężaj", która polega na podzieleniu  rozwiązywanego problemu na dwa podproblemy, rozwiązaniu ich i połączeniu wyników, tak by uzyskać rozwiązanie całego problemu. Metoda programowania dynamicznego jest właściwie rozwinięciem tej idei. Podzielmy dany problem na mniejsze podproblemy, a z ich wyników spróbujmy wywnioskować rozwiązanie końcowe. Nie zawsze jednak wiadomo, jakie to mniejsze podproblemy są nam potrzebne. W metodzie zwanej "programowaniem dynamicznym" proponuje się rozważenie wszystkich mniejszych podproblemów. Z pozoru takie podejście może się wydawać nierozsądne ze względu na nakład potrzebnej pracy. Tymczasem jest odwrotnie. Wykonując pewną dodatkową pracę, postawiony problem możemy rozwiązać z kosztem mniejszym, niż gdybyśmy ten problem atakowali bezpośrednio. Oczywiście nie każdy problem można rozwiązać tą metodą, tak jak to było w przypadku techniki zachłannej, metody dziel i zwyciężaj, czy metody rekurencyjnej. Jednak klasa problemów, dla których metoda programowania dynamicznego daje dobre rezultaty jest na tyle duża, że warto poznać bliżej tę technikę rozwiązywania problemów.

Matematyczne podstawy tej metody zawdzięczamy R. Belmanowi, który rozpoczął badania nad tą metodą w 1955 r. Słowo "programowanie" użyte w nazwie tej metody nie odnosi się do programowania, w sensie zapisywania pewnej metody postępowania w języku zrozumiałym dla komputera, ale do techniki tablicowania wyników pośrednich w celu ich późniejszego użycia do znalezienia optymalnego rozwiązania danego problemu.

Metodę programowania dynamicznego zwykle stosuje się w przypadku problemów optymalizacyjnych, dla których proste rozwiązania rekurencyjne prowadzą do algorytmów wykładniczych. Aby można było zastosować metodę programowania dynamicznego, problem powinien mieć dwie podstawowe cechy: optymalną podstrukturę oraz wspólne podproblemy.

Powiemy, że problem ma optymalną podstrukturę, jeżeli optymalne rozwiązanie problemu zawiera w sobie optymalne rozwiązania jego podproblemów. Wyznaczenie optymalnego rozwiązania problemu polega na wybraniu tych podproblemów, które składają się na rozwiązanie całego problemu.

Paradygmat programowania dynamicznego składa się z trzech prostych zasad:

1. Scharakteryzować strukturę rozwiązania optymalnego.
2. Zdefiniować rekurencyjnie wartość rozwiązania optymalnego, jako funkcję rozwiązań optymalnych dla podproblemów.
3. Skonstruować optymalne rozwiązanie problemu na bazie wyliczonych wcześniej wielkości.

Użycie tych zasad wyjaśnimy na przykładach, które są treścią pozostałych punktów tego wykładu.

Na zakończenie tego punktu zauważmy, że metoda zachłanna, o której mówiliśmy w wykładzie XI też wymaga by problem posiadał własność optymalnej podstruktury. Istotna różnica polega na sposobie wykorzystania tej własności. Stosując technikę zachłanną, najpierw dokonujemy wyboru podproblemu, który w danym momencie rokuje najlepsze rozwiązanie zadania, a następnie rozwiązujemy ten podproblem. W programowaniu dynamicznym najpierw znajdujemy optymalne rozwiązania podproblemów, a potem wybieramy te właściwe, które pozwolą nam znaleźć optymalne rozwiązanie problemu.

Pytanie 1: Niech problem polega na znalezieniu najkrótszej ścieżki w grafie zorientowanym, w którym każda krawędź ma taki sam koszt. Czy problem najkrótszej ścieżki ma własność optymalnej podstruktury?

« poprzedni punkt

następny punkt »