Problem

Pewien student, mieszkaniec Zakopanego, postanowił odwiedzić znajomych mieszkających w Gdańsku. Zdecydował się na podróż autobusami PKS. Ponieważ nie ma bezpośredniego połączenia autobusowego między miastami, studenta czeka kilka przesiadek. Poniższy schemat przedstawia możliwe połączenia między miastami na trasie Zakopane (wierzchołek 1)-Gdańsk (wierzchołek 10) oraz czas (godziny) w jakim można pokonać odległość między miastami. Celem studenta jest wybór takiej trasy Zakopane-Gdańsk, dla której czas podróży będzie najkrótszy.

Rysunek 1 Schemat połączeń pomiędzy miastami na trasie Zakopane – Gdańsk

Rysunek 2 Etapy rozpatrywanego procesu

Oznaczenia

c_i,j – czas w jakim można pokonać odcinek drogi między i-tym a j-tym miastem

f_s(i) – decyzja jaką należy podjąć w etapie s dla miejscowości i

f_s(i)= c_i,j+f_i+1(j)

Zgodnie z zasadą optymalności Bellmana, rozwiązanie problemu rozpoczynamy od ostatniego etapu. Rozwiązanie optymalne dla etapu pierwszego jest zarazem optymalne dla całego problemu.

Rozwiązanie

Etap 5

Przyjmujemy odległość do celu = 0, wobec tego:

F₅(10)=0

Etap 4

Obliczamy czas drogi do miasta 10 (Gdańska) z dwóch punktów. Z miasta 8 czas podróży wynosi 1 godzinę, natomiast z miasta 9 podróż zajmie 4 godziny. Korzystając z wprowadzonych oznaczeń oraz zależności otrzymujemy:

• Dla miasta 8:

f₄(8)=c_8,10+ f₅(10)=1

• Dla miasta 9:

f₄(9)=c_9,10+ f₅(10)=4

Etap 3

Na tym etapie rozpatrujemy wszystkie drogi rozpoczynające się w miastach o numerach 5,6 i 7 i prowadzące do miasta 10.

• Z miasta 5 istnieją dwie drogi: 5-8-10 oraz 5-9-10. Minimalny czas potrzebny na pokonanie drogi na tych trasach prezentuje się następująco:

$$f_{3}(5) = \min\left\{ \begin{matrix} c_{5,8} + f_{4}(8) \\ c_{5,9} + f_{4}(9) \\ \end{matrix} = min\left\{ \begin{matrix} 7 + 1 \\ 6 + 4 \\ \end{matrix} = min\left\{ \begin{matrix} 8 \\ 10 \\ \end{matrix} = 8 \right.\ \right.\ \right.\ $$

• Z miasta 6 wychodzą drogi 6-8-10 oraz 6-9-10. Czas podróży wynosi:

$$f_{3}(6) = \min\left\{ \begin{matrix} c_{6,8} + f_{4}(8) \\ c_{6,9} + f_{4}(9) \\ \end{matrix} = min\left\{ \begin{matrix} 3 + 1 \\ 8 + 4 \\ \end{matrix} = min\left\{ \begin{matrix} 4 \\ 12 \\ \end{matrix} = 4 \right.\ \right.\ \right.\ $$

• Z miasta 7 możemy wybrać drogę 7-8-10 lub 7-9-10. Czas potrzebny do pokonania tego dystansu wynosi:

$$f_{3}(7) = \min\left\{ \begin{matrix} c_{7,8} + f_{4}(8) \\ c_{7,9} + f_{4}(9) \\ \end{matrix} = min\left\{ \begin{matrix} 7 + 1 \\ 1 + 4 \\ \end{matrix} = min\left\{ \begin{matrix} 8 \\ 5 \\ \end{matrix} = 5 \right.\ \right.\ \right.\ $$

Na podstawie powyższych wyliczeń twierdzimy, że znajdując się w trzecim etapie, czyli w miejscowości 5, 6 lub 7 to czas dojazdu do miasta 10 jest równy:

• 8 godzin – drogą z miasta 5 przez 8 a następnie do 10;

• 4 godziny – drogą z miasta 6 do miasta 8 i dalej do 10;

• 5 godzin – drogą z miasta 7 przez miasto 9 a stamtąd do 10.

Etap 2

Rozpatrujemy drogi rozpoczynające się w jednej z trzech miejscowości 2, 3 i 4.

• Z miasta 2 można podróżować dwoma trasami. Czas minimalny, potrzebny do pokonania tych odcinków wynosi:

$$f_{2}(2) = \min\left\{ \begin{matrix} c_{2,5} + f_{3}(5) \\ c_{2,6} + f_{3}(6) \\ \end{matrix} = min\left\{ \begin{matrix} 11 + 8 \\ 10 + 4 \\ \end{matrix} = min\left\{ \begin{matrix} 19 \\ 14 \\ \end{matrix} = 14 \right.\ \right.\ \right.\ $$

Aby czas podróży był minimalny, powinniśmy z miasta 2 udać się do 6.

• Z miasta 3 prowadzą trzy możliwe drogi w kierunku celu. Czas przedstawia się następująco:

$$f_{2}(3) = \min\left\{ \begin{matrix} c_{3,5} + f_{3}(5) \\ c_{3,6} + f_{3}(6) \\ c_{3,7} + f_{3}(7) \\ \end{matrix} = min\left\{ \begin{matrix} 6 + 8 \\ 10 + 4 \\ 8 + 5 \\ \end{matrix} = min\left\{ \begin{matrix} 14 \\ 14 \\ 13 \\ \end{matrix} = 13 \right.\ \right.\ \right.\ $$

Powinniśmy wybrać podróż do miasta 7.

• Z miasta 4 możemy wybrać spośród dwóch wariantów. Czas tych rozwiązań wygląda następująco:

$$f_{2}(4) = \min\left\{ \begin{matrix} c_{4,6} + f_{3}(6) \\ c_{4,7} + f_{3}(7) \\ \end{matrix} = min\left\{ \begin{matrix} 15 + 4 \\ 10 + 5 \\ \end{matrix} = min\left\{ \begin{matrix} 19 \\ 15 \\ \end{matrix} = 15 \right.\ \right.\ \right.\ $$

W mieście 4 należy wybrać drogę prowadzącą do miasta 7

Etap1

Jest to ostatni etap procesu. Rozpatrujemy optymalne drogi rozpoczynające się w mieście 1 i kończące się w 10. Mamy trzy możliwości, a czas podróży, w zależności od wyboru, jest następujący:

$$f_{1}(1) = \min\left\{ \begin{matrix} c_{1,2} + f_{2}(2) \\ c_{1,3} + f_{2}(3) \\ c_{1,4} + f_{2}(4) \\ \end{matrix} = min\left\{ \begin{matrix} 3 + 14 \\ 5 + 13 \\ 3 + 15 \\ \end{matrix} = min\left\{ \begin{matrix} 17 \\ 18 \\ 18 \\ \end{matrix} = 17 \right.\ \right.\ \right.\ $$

Powinniśmy wybrać drogę do miasta 2.

Interpretacja wyników

Optymalna droga, o najkrótszym czasie trwania podróży, jest następująca:

Z miasta numer 1 do miasta o numerze 2 (etap 1), następnie do miasta numer 6 (etap 2), później do miasta 8 (etap 3), a stamtąd do miasta końcowego – 10 (etap 4). Czas trwania podróży tą drogą wyniesie 17 godzin.