85938

Rozwiązanie:

Niech N oznacza liczbę etapów (N = 5),

f„(s) = czas przebycia najkrótszej drogi na etapach od n do N , jeżli pasażer jest w stanie s

np. f₅(10) = 2 , f₅( 11) = 4 , f₅( 12) = 2

Pos/,ukąjemy:

fi(l) = 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 \n.

/.(*.*.) "*(*.*.)

fn(S,Xn) =

Czas podróży ze stanu s do stanu

+

Czas podróży najkrótszą drogą w etapach n+1 doN jeśli pasażer jest w stanie x„

s	*2=5	x2 = 6	X2=7	M*)	X2*
2	3 + f3(5)	2 + f3(6)	4 + f3(7)	12	5
3	2 ♦ f*5)	8 + U6)	1 + W)	11	5,7
4	7 ^ł «5)

ETAP 1

l*i= 3    |xi=4 |f|(s) |xi» |

ETAP 3

s		v,^#
10	2	13
11	4	13
12	2

ETAP 4

s	Yj — 10	\4= 11	\4= 12	L[s)	V4*
8	6 + fij( 10)	5 + fs(ll)	9 + fs(12)	8	10
9	5 + fsCIO)	1 + Wll)

ETAP 3

s	*3=8	xj = 9	f,(s)	X3*
5	2 + fj(8)	4 ^+ fj(9)	9	9
6	3 + W8)	7 + f^9)	11	8
7	2 + fj(8)
ETAP 2