Information Technology Reference
In-Depth Information
The problem can be considered on the network of Com-objects (O, F) as follows:
O = {O
1
: triangle ABC with AB = AC, O
2
: triangle AEG, O
3
: square ABDE, O
4
: square
ACFG }, and F = {f
1
, f
2
, f
3
, f
4
, f
5
} consists of the following relations
f
1
: O
1
.c = O
3
.a the edge c of triangle ABC = the edge of the square ABDE
f
2
: O
1
.b = O
4
.a the edge b of triangle ABC = the edge of the square ACFG
f
3
: O
2
.b = O
4
.a the edge b of triangle AEG = the edge of the square ACFG
f
4
: O
2
.c = O
3
.a the edge c of triangle AEG = the edge of the square ABDE
f
5
: O
1
.A + O
2
.A = .
Definition 3.8:
Let (O, F) be a network of Com-objects, and M be a set of concerned
attributes. Suppose A is a subset of M.
a.
For each f F, denote f(A) is the union of the set A and the set consists of all attributes
in M deduced from A by f. Similarly, for each Com-object O
i
O, O
i
(A) is the union of
the set A and the set consists of all attributes (in M) that the object O
i
can determine
from attributes in A.
b.
Suppose D = [t
1
, t
2
, ..., t
m
] is a list of elements in F O. Denote A
0
= A, A
1
= t
1
(A
0
), . . .,
A
m
= t
m
(A
m-1
), and D(A) = A
m
.
We have A
0
A
1
. . . A
m
= D(A) M. Problem HG is called
solvable
if there is a list
D F O such that D(A) B. In this case, we say that D is a
solution
of the problem.
Technically the above theorems and algorithms can be developed to obtain the new ones for
solving the problem HG on network of Com-objects (O,F). They will be omitted here
except the algorithm to find a solution of the problem. The worthy of note is that the objects
may participate in solutions as computational relations.
Algorithm 3.3:
Find a solution of the problem HG on a network of Com-objects.
Step 1: Solution empty;
Step 2: if
G H then
begin Solution_found true; goto step 5; end
Else Solution_found false;
Step 3: Repeat
Hold H;
Select f F;
while not Solution_found and (f found) do begin
if (applying f from H produces new facts) then begin
H H M(f); Add f to Solution;
end;
if
G H then Solution_found true;
Select new f F;
end;
while
Until Solution_found or (H = Hold);
Step 4: if not Solution_found then
begin
Select O
i
O such that O
i
(H) H;
if
(the selection is successful) then begin
H O
i
(H); Add O
i
to Solution;
if (G H) then
begin