( ). ( C) . .
3.16.
3.1 1 3 , . 3.11.
. 3.11
1. n =5. :
C = .
2. k = 0, l 1(0) = 0, l 2(0) = l 3(0) = l 4(0) = l 5(0) = . . 3.2.
3.
k = 1.
l 1(1) = 0.
(3.1) k = 1 :
li (1) = { lj (0) + cji }.
l 2(1) = min { l 1(0) + c 12; l 2(0) + c 22; l 3(0) + c 32; l 4(0) + c 42; l 5(0) + c 52;} = min {0 1; ¥ + ¥; ¥ + ¥; ¥ + ¥; ¥ + ¥} = 1.
l 3(1) = min { l 1(0) + c 13; l 2(0) + c 23; l 3(0) + c 33; l 4(0) + c 43; l 5(0) + c 53;} = min {0 + ¥; ¥ 8; ¥ + ¥; ¥ 2; ¥ + ¥} = ¥.
l 4(1) = min { l 1(0) + c 14; l 2(0) + c 24; l 3(0) + c 34; l 4(0) + c 44; l 5(0) + c 54;} = min {0 + ¥; ¥ 7; ¥ + ¥; ¥ + ¥; ¥ 4} = ¥.
l 5(1) = min { l 1(0) + c 15; l 2(0) + c 25; l 3(0) + c 35; l 4(0) + c 45; l 5(0) + c 55;} = min {0 3; ¥ 1; ¥ + 5; ¥ + ¥; ¥ + ¥} = 3.
li (1) . 3.2. , , , , li (1), i -, .
k = 2.
l 1(2) = 0.
(3.1) k = 2 :
li (2) = { lj (1) + cji }.
l 2(2) = min {0 1; 1 + ¥; ¥ + ¥; ¥ + ¥; 3 + ¥} = 1.
l 3(2) = min {0 + ¥; 1 8; ¥ + ¥; ¥ 2; 3 + ¥} = 9.
l 4(2) = min {0 + ¥; 1 7; ¥ + ¥; ¥ + ¥; 3 4} = 8.
l 5(2) = min {0 3; 1 1; ¥ + 5; ¥ + ¥; 3 + ¥} = 3.
li (2) . 3.2. li (2) i -, .
k = 3.
l 1(3) = 0.
(3.1) k = 3 :
li (3) = { lj (2) + cji }.
l 2(3) = min {0 1; 1 + ¥; 9 + ¥; 8 + ¥; 3 + ¥} = 1.
l 3(3) = min {0 + ¥; 1 8; 9 + ¥; 8 2; 3 + ¥} = 10.
l 4(3) = min {0 + ¥; 1 7; 9 + ¥; 8 + ¥; 3 4} = 8.
l 5(3) = min {0 3; 1 1; 9 + 5; 8 + ¥; 3 + ¥} = 4.
li (3) . 3.2. li (3) i -, .
|
|
k = 4.
l 1(4) = 0.
(3.1) k = 4 :
li (4) = { lj (3) + cji }.
l 2(4) = min {0 1; 1 + ¥; 10 + ¥; 8 + ¥; 4 + ¥} = 1.
l 3(4) = min {0 + ¥; 1 8; 10 + ¥; 8 2; 4 + ¥} = 10.
l 4(4) = min {0 + ¥; 1 7; 10 + ¥; 8 + ¥; 4 4} = 8.
l 5(4) = min {0 3; 1 1; 10 + 5; 8 + ¥; 4 + ¥} = 5.
li (4) . 3.2. li (4) i -, .
3.2
i ( ) | li (0) li (1) li (2) li (3) li (4) |
0 0 0 0 0 ¥ 1 1 1 1 ¥ ¥ 9 10 10 ¥ ¥ 8 8 8 ¥ 3 3 4 5 |
. 3.2 , (. 3.3). li (k) i -, k .
3.3
i ( ) | li (0) li (1) li (2) li (3) li (4) |
0 0 0 0 0 ¥ 1 1 1 1 ¥ ¥ 9 10 10 ¥ ¥ 8 8 8 ¥ 3 3 4 5 |
5. , .
10. , . . li (3) = li (4) = 10. (3.2) , n 1.
, x 3 xr (3.2) s =3:
lr (2) + cr 3 = l 3(3), (3.7)
xr Î G- 1(x 3), G- 1(x 3) - x 3.
G- 1(x 3)= { x 2, x 4}.
(3.7) r = 2 r = 4, , r :
l 2(2) + c 23 = 1 + 8 ¹ l 3(4) = 10,
l 4(2) + c 43 = 8 + 2 = l 3(4) = 10.
, , x 3, x 4.
x 4 xr (3.2) s =4:
lr (1) + cr 4 = l 4(2), xr Î G- 1(x 4), (3.8)
G- 1(x 4) - x 4.
G- 1(x 4)= { x 2, x 5}.
(3.8) r = 2, r = 3 r = 5, , r :
l 2(1) + c 24 = 1 + 7 = l 4(3) = 8,
l 5(1) + c 54 = 3 + 4 ¹ l 4(3) = 8,
, , x 4, x 2.
x 2 xr (3.2) s =2:
lr (0) + cr 2 = l 2(1), xr G- 1(x 2), (3.9)
G- 1(x 2) - x 2.
G- 1(x 2)= { x 1}.
(3.9) r = 1, , :
l 1(1) + c 12 = 0 + 1 = l 2(1) = 1.
, , x 2, x 1.
, x 1, x 2, x 4, x 3, 10.