, , , . . , . , , .. . . , , ..
, , . , , , , .
, .
, .1.1. , xi 1 mi. . n. .
.1.1
, , . .
. mi = m, ( ) mn. m = 10, , n £ 3 , n 4 7-8 , n 11-12 . , 1 10 . , , , .
, , . , , , , .
|
|
. - Ui, . First(U) U, Last(U) , Next(U, x) , U x, Next(U, Last(U)) NoValue. Ui U[i]. , . CompleteSearch(k), p G(X,p) , x1, x2, , xk .
procedure CompleteSearch(k: Integer);
begin
if( k ) then
begin
if G(X,p) then begin
X
A, B C;
end;
end
else begin
k:=k+1;
X[k]:=First(U[k]);
repeat
CompleteSearch(k);
X[k]:=Next(U[k],X[k]);
until X[k]=NoValue;
end;
end;
( ) :
CompleteSearch(0);
, . k n k = n. , - , . , A B , A B.
:
A (): , . , , .
B (): (, ) .
C (): ( ) X F(X) , .
, . , . , .
xi , . , , , . , .
. . , , . , 500 , 200 350 . , .
|
|
, , . , , x1 = 0 .
, , , . , , , , , .
, , . , 1-2 , .
? , . , . G(X,p,k) = 0, x1, x2, , xk xk+1, xk+2, , xn , G(X,p,k) = 1, xk+1, xk+2, , xn , , . CompleteSearch ReducedSearch, :
procedure ReducedSearch(k: Integer);
begin
if G(X,p,k) then begin
if( k ) then
begin
X
A, B C;
end
else begin
k:=k+1;
X[k]:=First(U[k]);
repeat
ReducedSearch(k);
X[k]:=Next(U[k],X[k]);
until X[k]=NoValue;
end;
end;
end;
, , .
, , . , , , , , , . , .
, , ( ) . , .
U - F(X) - , . - U U0 U1. , U0 , .. . , , : - U0 . U0 U00 U01, U00 U000 U001 .. , . , , : U0000= {X0}. .1.2. X0. ?
|
|
.1.2
- j(W), W U, .. j(W) F(X) X W. [3] , .. , , F(X) X W , j(W). , .
F(X0) j(U0001). F(X0) j(U0001), X0 U000. , U0001. U001. , , F(X0) j(U001), X0 U00 ..
, - j(W) ? , , F(X0) > j(U01). U01 U010 U011, U010 U0100 U0111 .., . , X1. .
, , , .
, :
.
.
, , , .
, , . , . , , . , , , .
. , .
. , , . .
5 A, .1.1. , .
|
|
1.1
A | ji | |||||
¥ | ||||||
¥ | ||||||
¥ | ||||||
¥ | ||||||
¥ | ||||||
jj | j = 47 |
, . ji i- . ji . . ji. j = 47. A¢ .1.2.
1.2
A¢ | |||||
¥ | |||||
0 (15) | ¥ | ||||
¥ | 0 (2) | ||||
¥ | 0 (3) | ||||
0 (12) | 0 (2) | ¥ |
? (.. ), , . j , . , . . 0, j.
. aij, i j, : , i j (U0), , (U1). U0 , aij, . A¢, ? , , . , i j? -, i - , aij = 0 i- aik, k ¹ j. i- aik . -, j - , arj, r ¹ i, , i. dij .
.1.2 dij . , d21 = 15. , U0 , 2 1, U1 . U1 j1 = j + d21 = 62.
, U0. A0 A¢ 2 1, . , 2 1, 1 2, a12 = ¥. .1.3.
1.3
A0 | ji | ||||
¥ | |||||
¥ | |||||
¥ | |||||
¥ | |||||
jj | j = 3 |
A0¢ (.1.4). j = 3, , U0 j0 = 47 + 3 = 50.
1.4
A0¢ | ||||
¥ | 0 (1) | |||
¥ | 0 (2) | |||
¥ | 0 (18) | |||
0 (13) | 0 (13) | 0 (1) | ¥ |
|
|
, dij. d45 = 18. U00 U0, 4 5, U01 , 2 1, 4 5. j01 = j0 + d45 = 50 + 18 = 68.
U00 A00, A0¢ 4 5 a54 = ¥. .1.5.
1.5
A00 | ji | |||
¥ | ||||
¥ | ||||
¥ | ||||
jj | j = 3 |
.1.6 A00¢. U00 j00 = 50 + 3 = 53.
1.6
A00¢ | |||
¥ | 0 (12) | ||
¥ | 0 (11) | ||
0 (11) | 0 (12) | 0 (0) |
: d14 = d53 = 12. [4], , a14. U001 ( U00, 1 4), j001 = j00 + d14 = 53 + 12 = 65.
, , 2 1, 4 5 1 4, 2 1 4 5. , 3 ( , U000 ). , 1, : 1 4 5 3 2 1. , , j00 = 53 a53 = 0 a32 = 11, . f000 = 64, .
? . j001 = 65, , U001 , , 1 , , U001 . U01, j01 = 68. U1 j1 = 62, , , 64. U1 , .
, U1 , 2 1. , A¢ a21 = ¥. A1 .1.7.
1.7
A1 | ji | |||||
¥ | ||||||
¥ | ¥ | |||||
¥ | ||||||
¥ | ||||||
¥ | ||||||
jj | j = 15 |
A1¢ (.1.8). U1, , j1 = 62.
1.8
A1¢ | |||||
¥ | 0 (3) | ||||
¥ | ¥ | 0 (8) | |||
¥ | 0 (2) | ||||
0 (12) | ¥ | 0 (0) | |||
0 (0) | 0 (2) | ¥ |
d41 = 12. : U10 , 2 1, 4 1, U11 , 2 1, 4 1. j11 = j1 + d41 = 62 + 12 = 74, .. U11 , , .
A10 U10 .1.9.
1.9
A10 | ji | ||||
0 (3) | ¥ | ||||
¥ | 0 (8) | ||||
¥ | 0 (4) | ||||
0 (0) | 0 (2) | ¥ | |||
jj | j = 0 |
, j10 = j1 = 62 . d23 = 8. U101 j101 = j10 + d23 = 62 + 8 = 70, , U101 . U100 , 2 1, 4 1 2 3. A100 .1.10.
1.10
A100 | ji | |||
0 (3) | ¥ | |||
¥ | 0 (4) | |||
0 (3) | ¥ | |||
jj | j = 0 |
, j100 = j10 = 62. d35 = 8. U1001 j1001 = j100 + d35 = 62 + 4 = 66, U1001 . U1000 , 4 1, 2 3 3 5. , ( U1000), : 1 2 3 5 4 1. f1000 = 62, , !
, , . , ( 24 ).
.1.3 . , . , .
.1.3