Information Technology Reference
In-Depth Information
The root node of binary tree gather all information of all branch nodes. It
becomes an agent for all leaf nodes of binary tree. And the node set of current
visited variable is all root node set of such binary tree(including isolation node).
For tree search, it is necessary to consider that equation is made after assumption
assignment. After assumption assignment is revoked, the equivalent relation of
assertions is no longer tenable, which should be revoked as well. The method is
to revoke its corresponding common node. The equation reasoner offers to
inquiry equal relation of any two variables with the same type, even they are not
assigned. This strategy has the following advantages, which certainly may be
interrelated.
(1) The complexity of constraint search is mainly depend on the number of
constraint variable. The unit sharing strategy merges two or more variables
with identical relation into one variable. Therefore the strategy can be used to
reduce search space.
(2) Make the constraint reasoner can find inconsistencies relevant to identical
relation before variables are not assigned. For example, for constraints {
x=y
,
y=z
,
x
≠
z
}, even
x
,
y
and
z
are not assigned yet, system can check out
inconsistency of constraints.
(3) Make constraint propagation run. The unit sharing strategy of identical
relation reduces the number of unknown variables and reduce the number of
unknown variables of one constraint relation as well. In general, only when
the number of unknown variable in one constraint relation is less enough,
constraint propagation can be carried on. Constraint propagation at early time
is equivalent to pruning branches close to root node of search tree ahead of
time, therefore can reduce search space greatly.
For example, for the constraint
r(x,y,z)
which includes three enumerated
variables
are different variables, in
general we can do consistency refinement for domain of
x
,
y
and
z
, after
x
is instantiated, if
y
and
z
y
or
z
. If there exists
, then means that unassigned variable is only one.
Therefore constraint propagation can be carried on.
(4) Make constraint language have ability of pattern matching in symbol
processing.
one constraint
y=z
In order to explain the advantage of such strategy, we consider taking
qualitative add operation of qualitative physic implemented by COPE language
as example. One physical quantity that varies in real domain can be characterized
