3582326899

PROGRAMOWANIE DYNAMICZNE

1.    Metoda optymalizacyjna do rozwiązywania pewnej klasy problemów wymagających sekwencyjnego podejmowania decyzji w kolejnych etapach.

2.    Decyzja podjęta w jednym etapie ma wpływ na stan problemu i decyzje możliwe do podjęcia w kolejnych etapach.

3.    Brak "postaci standardowej"

4.    Podproblem jednoetapowy, następnie coraz większe podprobiemy rozwiązywane rekurencyjnie aż do rozwiązania problemu wyjściowego,

5.    Unikalność problemów - filozofia podejeścia.

Przykład wprowadzający:

cc

£

|

V

Nowy Jork

Pewien pasażer pragnie podróżować dyliżansem ze stanu Kalifornia do stanu Nowy Jork.

Graf pokazuje wszystkie dostępne połączenia dyliżansowe na przestrzeni miedzy tymi dwoma stanami. Liczby w kwadratach określają stany pośrednie które są etapami w podróży. Określić jaką drogę powinien wybrać pasażer, aby czas podróży był jak najkrótszy.

Droga “ północna " = 15 dni, “ południowa “ =21 dni.

1.    Metoda całkowitego przeglądu; 54 możliwości = 3* 3* 2* 3.

2.    Dla problemu 20 — u etapów, 10 stanów = 10¹⁹ możliwości.

3.    W etapie 1 nie jest oczywista droga najkrótsza. Wynika to z faktu, że zbyt wiele etapów jest jeszcze do rozpatrzenia.

4.    Nie jest optymalne podejmowanie decyzji.

5.    Jeżeli rozważymy tylko jeden pozostający etap (etap 5) to rozwiązanie jest oczywiste.