To tylko jedna z 3 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
PROGRAMOWANIE DYNAMICZNE
Metoda optymalizacyjna do rozwiązywania pewnej klasy problemów wymagających sekwencyjnego podejmowania decyzji w kolejnych etapach.
Decyzja podjęta w jednym etapie ma wpływ na stan problemu i decyzje możliwe do podjęcia w kolejnych etapach.
Brak "postaci standardowej"
Podproblem jednoetapowy, następnie coraz większe podproblemy rozwiązywane rekurencyjnie aż do rozwiązania problemu wyjściowego.
Unikalność problemów - filozofia podejeścia.
Przykład wprowadzający:
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. Metoda całkowitego przeglądu: 54 możliwości = 3 3 2 3. Dla problemu 20 u etapów, 10 stanów = 1019 możliwości. W etapie 1 nie jest oczywista droga najkrótsza. Wynika to z faktu, że zbyt wiele etapów jest jeszcze do rozpatrzenia. Nie jest optymalne podejmowanie decyzji. Jeżeli rozważymy tylko jeden pozostający etap (etap 5) to rozwiązanie jest oczywiste. Kolejne etapy obliczeń:
Rozwiązanie:
Niech N oznacza liczbę etapów (N = 5),
fn(s) = czas przebycia najkrótszej drogi na etapach od n do N , jeżli pasażer jest w stanie s
np. f5(10) = 2 , f5(11) = 4 , f5(12) = 2 Poszukujemy:
f1(1) = czas przebycia najkrótszej drogi na etapach od 1 do 5 przy założeniu że pasażer jest w stanie 1. fn(s,xn) = czas przebycia najkrótszej drogi na etapach od n do N, przy założeniu , że pasażer jest w stanie s oraz że pasażer w etapie n jedzie do xn. fn(s,xn) =
Czas podróży ze stanu s do stanu xn
+ Czas podróży najkrótszą drogą w etapach n+1 do N jeśli pasażer jest w stanie xn
ETAP 5
s
f5(s)
x5*
10
2
13
11
4
13
12
2
... zobacz całą notatkę
Komentarze użytkowników (0)