:
- RN (i,j)
- RO (i,j)
- PN (i,j)
- PO (i,j)
- r (i,j)
- R (i,j).
.
RN (i,j) .
RO (i,j) .
1 , . , :
RO (i,j) = 0 + t i,j.
2 (i,j) (l,j), :
RN (i,j) = RO (l,j).
3 , :
RN (i,j) = max RO (l,j).
4 (i,j) :
RO (i,j) = RN (i,j) + t i,j
(.2).
1-2, 1-3, 1-5 , , :
RN (1,2) = 0, RO (1,2) = RN (1,2) + t 1,2 = 0 + 8 = 8
RN (1,3) = 0, RO (1,3) = RN (1,3) + t 1,3 = 0 + 2 = 2
RN (1,5) = 0, RO (1,5) = RN (1,5) + t 1,5 = 0 + 6 = 6
2-4, 2-6 1-2:
RN (2,4) = RO (1,2) = 8, RO (2,4) = RN (2,4) + t 2.4 = 8 + 5 = 13
RN (2,6) = RO (1,2) = 8, RO(2,6) = RN (2,6) + t 2.6 = 8 + 4 = 12
3-6, 3-5 1-3:
RN (3,6) = RO (1,3) = 2, RO (3,6) = RN (3,6) + t 3,6 = 2 +10 = 12
RN (3,5) = RO (1,3) = 2, RO (3,5) = RN (3,5) + t 3,5 = 2 + 7 = 9
5-6 5-7 [RO (3,5) RO (1,5)]:
RN (5,6) = max [RO (3,5), RO (1,5)] = max [ 9, 6 ] = 9
RN (5,7) = max [RO (3,5), RO (1,5)] = max [ 9, 6 ] = 9,
:
RO (5,6) = RN (5,6) + t 5,6 = 9 +12 = 21
RO (5,7) = RN (5,7) + t 5,7 = 9 + 9 = 18
..
. .
, .. .
1. .
|
|
|
2. :
N (i,j) = O (i,j) - t i,j.
3. , :
O (i,j) = N (j, ).
4. , :
O (i,j) = min N (j, ).
.
:
O (8,10) = (9,10) = (7,10) = 30
:
N (7,10) = (7,10) - t 7,10 = 30 - 3 = 27
N (9,10) = (9,10) - t 9,10 = 30 - 4 = 26
N (8,10) = (8,10) - t 8,10 = 30 - 6 = 24
:
O (6,8) = N (8,10) = 24
N (6,8) = (6,8) - t 6,8 = 24 - 3 = 21
O (6,9) = N (9,10) = 26
N (6,9) = (6,9) - t 6,9 = 26 - 5 = 21
. .
4.3.1 Ri,j - , , .
.
:
R1-2 = 7 - 0 = 7
R1-3 = 0 - 0 = 0
R1-5 = 3 - 0 = 3
R2-4 = 15 - 8 = 7
R2-6 = 17 - 8 = 9
R3-5 = 2 - 2 = 0
R3-6 = 11 - 2 = 9
R4-8 = 20 -13 = 7
R6-8 = 21 - 21= 0
..
4.3.2 ri.j - , .
.
:
r 1-2= 8 - 8 = 0
r 1-3= 2 - 2 = 0
r 1-5= 9 - 6 = 3
r 2-4= 21 - 12 = 9
r 2-5= 13 - 13 = 0
r 3-5= 9 - 9 = 0
r 3-6= 21 - 12 = 9
..
5
1 ?
2 ?
3 ?
4 ?
5 ?
6 ?
7 ?
8 ?
9 ?
10 ?
11 ?
12 ?
13 ?
14 ?
15 ?
| , . | |
| 1 , . . []: . / . . , . . . .: , 2001. - 368 . | |
| 2 []: . / .. [ .]; . . . . .: , 2006. 407. | |
| 3 , . . []: / . . . .: , 2001. - 544 . | |
| 4 - []: . / . . [ .]; . . . . .: , 1999. 391 . |
|
|
|
