To tylko jedna z 4 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Krzysztof Koz_owski. Notatka składa się z 4 stron.
Mamy 6-o etapowy proces przejścia z pkt A do B wzdłuż jednej z możliwych dróg siatki przedstawionej na rysunku . Rozpatrujemy 6-o etapowy proces przejścia z punktu A do B. Na każdym etapie mamy kilka możliwych stanów(są to węzły siatki), przy czym z każdego stanu wychodzą 3 drogi umożliwiające przejście do następnego stanu. Decyzję odpowiadającą wyborowi 1 z 3 grup będziemy oznaczać za stanem:
+1 droga najwyższa
0 droga środkowa
-1 droga najniższa
Każdemu odcinkowi łączącemu 2 stany odpowiada pewien koszt przejścia oznaczony liczbą w liczniku.
Zadaniem jest wybór takiej trasy przy którym jest minimalny koszt całkowity.( Zadanie sterowania optymalnego) Zadanie programowania dynamicznego R. Bellman Uniwerek USC i UCLA.
Obliczenia rozpoczynamy od końca - od punktu (B) do punktu (A)
I etap
Od B do 5
II etap - Od 5 do 4
(Na każdym etapie wybieramy najlepszą drogę)
III etap
Od 4 do 3
IV etap
Od 3 do 2
V etap
Od 2 do 1
Sterowanie
Dzięki sekwencyjnemu charakterowi obliczeń programowanie dynamiczne od prawej do lewej pozwala na oszczędność obliczeń w stosunku do bezpośredniego porównywania wszystkich możliwości. W kolejnych etapach eliminujemy tory nieoptymalne pozostawiając do obliczeń tylko te, które mogą być ewentualnie optymalne
W naszym przypadku gdybyśmy chcieli wyznaczyć tor optymalny metodą bezpośrednich obliczeń musimy przeanalizować 3 5 możliwości(245). Stosując prog. dynamiczne: ilość obliczeń = 3+4*3 2 +3=42 (tzw. zasada dyskretna programowania dynamicznego). Ostatecznego wyboru dokonujemy z chwilą przejścia wszystkich etapów. Metoda ta jest podobna do. Metoda ta jest podobna do wyłaniania mistrza sportowego przez kolejne zawody i eliminacje
Zasada optymalności: strategią optymalną jest strategia mająca tę właściwość, że przy dowolnym stanie po decyzji początkowej następne decyzje powinny tworzyć strategię optymalną w odniesieniu do stanu wynikającego z pierwszej decyzji.
... zobacz całą notatkę
Komentarze użytkowników (0)