-. , G (V, A) c - V A. , (x, y) - w (x, y), , , . - . N (.. N ) x 0. P W (P) . P -, P N x 0 W (P) ≥ W (P). , , P (x 0, N).
( ) . , , 8 - , . - . , , ( , ) . , ( - ) - (. 2.3). , .
- x 0 N. . N - N 1, .., 1. - .
r x Z (r, x), (.. ) P (x, r), W (x, r). , x G Z (r, x) , P (x, r), W (x, r). x 0 P r +1 x 0. (.. ) P x. W (P) P : w (x 0, x) P W (P), P P x , r, ..
W (P) = w (x 0, x) + W (P). (4)
W (x, r) x r , (4) ,
W (P) ≤ w (x 0, x) + W (x, r), (5)
x , (5) , x 0 r +1
|
|
W (x 0, r +1) = max x { w (x 0, x) + W (x, r)}. (6)
(6) , , r ó - r +1. , , , r (x 0, x), x (6). , r = 1 P (x,1) x:
W (x,1) = max yw (x, y). (7)
, , - −∞ ( +∞).
, , - , (6) , , - ( ) - .
, , - . G m. , , .. -, (.. ). N , , mN. m 2, N Nm 2. - m = 20 N = 10 - 10*400 = 4000, 2010 ≈ 1016 .
, - , . - .
1. , .8-3. .1. x 0 1. - N = 6.
.1
1. 1- . , 5- ( ) 12- . .
1.1. 1
−∞ | −∞ | −∞ | −∞ | ||||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−∞ | −∞ | −5 | −∞ | ||||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−4 | −∞ | −∞ | −∞ |
(i, j) i - j - j i ( ). . i - , i - , , . , 1- , 1 (8), ( 3); 2- 7 5, .. (7) , 1- 1.
|
|
2 - .
1.2. 2.1
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−∞ | −∞ | −5 | −∞ | ||||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−4 | −∞ | −∞ | −∞ | −4 |
1- . 1 . - 1. - (12) - 1- 2, - (3). (6). 2- :
1.2. 2.2
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−∞ | −∞ | −5 | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−4 | −∞ | −∞ | −∞ |
3-, 4- 5- . :
|
|
1.2. 2.3
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−∞ | −∞ | −5 | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−4 | −∞ | −∞ | −∞ | −∞ | −∞ |
1.2. 2.4
−∞ | −∞ | −∞ | −∞ | ||||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−∞ | −∞ | −5 | −∞ | −5 | −1 | ||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−4 | −∞ | −∞ | −∞ | −∞ | −∞ |
1.2. 2.5
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−∞ | −∞ | −5 | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−4 | −∞ | −∞ | −∞ | −∞ | −∞ |
2. 1- 1→3→2 12, 2- 2→5→4 13, 3- 3→2→5 11, 4- 4→1→3 10, 5- 5→4→2 8.
|
|
3- . 2- , - 2:
1.3. 3.1
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−∞ | −∞ | −5 | −∞ | ||||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−4 | −∞ | −∞ | −∞ | −4 |
1.3. 3.2
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−∞ | −∞ | −5 | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−4 | −∞ | −∞ | −∞ |
1.3. 3.3
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−∞ | −∞ | −5 | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−4 | −∞ | −∞ | −∞ | −∞ | −∞ |
1.3. 3.4
−∞ | −∞ | −∞ | −∞ | ||||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−∞ | −∞ | −5 | −∞ | −5 | |||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−4 | −∞ | −∞ | −∞ | −∞ | −∞ |
1.3. 3.5
|
|
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−∞ | −∞ | −5 | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−4 | −∞ | −∞ | −∞ | −∞ | −∞ |
4- :
1.4. 4.1
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−∞ | −∞ | −5 | −∞ | ||||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−4 | −∞ | −∞ | −∞ | −4 |
1.4. 4.2
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−∞ | −∞ | −5 | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−4 | −∞ | −∞ | −∞ |
1.4. 4.3
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−∞ | −∞ | −5 | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−4 | −∞ | −∞ | −∞ | −∞ | −∞ |
1.4. 4.4
−∞ | −∞ | −∞ | −∞ | ||||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−∞ | −∞ | −5 | −∞ | −5 | |||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−4 | −∞ | −∞ | −∞ | −∞ | −∞ |
1.4. 4.5
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−∞ | −∞ | −5 | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−4 | −∞ | −∞ | −∞ | −∞ | −∞ |
5- :
1.5. 5.1
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−∞ | −∞ | −5 | −∞ | ||||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−4 | −∞ | −∞ | −∞ | −4 |
1.5. 5.2
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−∞ | −∞ | −5 | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−4 | −∞ | −∞ | −∞ |
1.5. 5.3
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−∞ | −∞ | −5 | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−4 | −∞ | −∞ | −∞ | −∞ | −∞ |
1.5. 5.4
−∞ | −∞ | −∞ | −∞ | ||||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−∞ | −∞ | −5 | −∞ | −5 | |||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−4 | −∞ | −∞ | −∞ | −∞ | −∞ |
1.5. 5.5
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−∞ | −∞ | −5 | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−4 | −∞ | −∞ | −∞ | −∞ | −∞ |
6- . 6- 1- -, 1:
1.6. 6
−∞ | −∞ | −∞ | −∞ | −∞ | −∞ | ||||||||||||||
−∞ | −∞ | −∞ | |||||||||||||||||
−∞ | −∞ | −5 | −∞ | ||||||||||||||||
−∞ | −∞ | −∞ | −∞ | −∞ | |||||||||||||||
−4 | −∞ | −∞ | −∞ | −4 |
6 1. , , . 35. . : 1→3→2→5→4→1→3. , , 1→3.
, - . ■
2. , N = 6 - . , 1 , ; , . -, ∞ ( −∞). ; - .
2.1. 1
∞ | ∞ | ∞ | ∞ | −4 | |||||||||||||||
∞ | ∞ | ∞ | |||||||||||||||||
∞ | ∞ | −5 | ∞ | ||||||||||||||||
∞ | ∞ | ∞ | −5 | ||||||||||||||||
−4 | ∞ | ∞ | ∞ |
2.2. 2
∞ | ∞ | ∞ | ∞ | −4 | |||||||||||||||
∞ | ∞ | ∞ | −4 | ||||||||||||||||
∞ | ∞ | −5 | ∞ | ||||||||||||||||
∞ | ∞ | ∞ | −2 | −5 | |||||||||||||||
−4 | ∞ | ∞ | ∞ |
2.3. 3
∞ | ∞ | ∞ | ∞ | −3 | −4 | ||||||||||||||
∞ | ∞
: 2016-10-07; !; : 588 | : : , , |
: 0.045 .