, - (., , [3,4]). - , , ( ). .5.
.5. .
"" . . , . , . .6.
.6. .
, , . , , ( ) ( ).
, .
. , ( ).
- , - , . , - . , , - , , , .
. :
- (, , ), ( );
- ( ).
. ? : (, , , ) ? - . (.7).
.7. .
, , (.7). . .7 . , .4.
4.
|
|
.
: 1 4?
. : () - 1 . ( , , , , , , .) (4) , .
, .7 .4, 3 , 1, , 1, (3) = 1. , , (1) = 0.
4 2, , 4, 5, , 5.
(4) = min {(2) + 4; (5) + 5}.
, () - (4) (2) (5).
5 3, , 2, 6, , 3.
(5) = min { (3) + 2; (6) + 3}.
, (3) = 1.
(5) = min {3; (6) + 3}.
, (6) - , , (5) = 3.
2 1, , 7, 3, , 5, 5, , 2.
(2) = min {(1) + 7; (3) + 5; (5) + 2}.
, (1) = 0, (3) = 1, (5) = 3.
(2) = min {0 + 7; 1 + 5; 3 + 2} = 5.
(4):
(4) = min { (2) + 4; (5) + 5} = min {5 + 4; 3 + 5} = 8.
, 8. , 4 5. (5), , 5 3. 3 1. , :
1 → 3 → 5 → 4.
(.7 .4) .
, , . , .
. (.. ) , ?
, , - . (.8).
.8.
, , , .8, (.5).
|
|
5.
.
, 6, 6 0, , 2 1, 3 2 1 3.
, 6 0 4. , 2 , 1, 4. 2 : 2 4, 1 - 3 (- 2 4). 3 : 1 0 1 2. 4.
, - 6 . () 1 2, 1 3. 1 4 - 2 3 .
(.6).
6.
. . KM - . .8 = 0,1,2,3, = 1,2,3,4, . , 9 KM , , 01, 02, 03, 12, 13, 14, 23, 24, 34 . , , :
F → max,
01 + 02 + 03 = F (0)
- 01 + 12 + 13 + 14 = 0 (1)
- 02 - 12 + 23 + 24 = 0 (2)
- 03 - 13 - 23 + 34 = 0 (3)
- 14 - 24 - 34 = - F (4)
01 ≤ 2
02 ≤ 3
03 ≤ 1
12 ≤ 4
13 ≤ 1
14 ≤ 3
23 ≤ 1
24 ≤ 2
34 ≤ 2
≥ 0, , = 0, 1, 2, 3, 4, F ≥ 0.
F - , (0) . (1) - (3) 1- 3 . , , "" . (4) - "" . (0) ("" ""). "" . . , ( (0) (4)) . - , (, ), ( , " ").
|
|
. . , . - . ( ) ( ).
, , , 0 ( - ). . .
[5], , [6]. , , , . ( 3.4). .
1. . / . . - .: , 1973. - 176 .
2. ., . / . .. - ,: , 1966. -280 .
3. .., .., .. . - .: , 1976. - 392 .
4. .., .., .. . .: , 2001. 124 .
5. .. . .: , 1980. 64 .
6. .. . .: - , 2002. 576 .