Information Technology Reference
In-Depth Information
3.10 Constraint Relation Processing
3.10.1
Unit Sharing Strategy for Identical Relation
In constraint reasoning, if two variables always take the same value, then the
relation of these two variables is identical relation, which is a kind of important
constraint relations. For instance, two devices are connected in series in the
circuit, which means that the electric current through one device is equal to the
other device. A square can be defined as a rectangle whose length and width are
equal. Although identical relation can be processed by common constraint
relation, it is necessary to carry on special processing for its popularity and
special semantic. As a result, it can avoid the low efficiency of common CSP
solver, more importantly it can directly reduce the computing scale of CSP.
Because the two equal variable should take the same value, they can be regarded
as the same variable in computing. This is the basic idea of unit sharing strategy.
A simple method to realize unit sharing strategy is that replacing equal
variables with a new variable, however, this will lead to global variable
replacement of constraint network. Meanwhile, consider that some equal
relations are defined after making some assignment assumptions, therefore
original variable information before equated must be kept. So we use binary tree
to represent variable information. For equation
have been already
assigned, then determine whether they are equal and return Boolean value. If
x
=
y
, if
x
and
y
x
is
assigned but
y
is not, then determine whether the values of
x
are belong to the
domain of
. If the condition is not true, then return “inconsistence”
information(failure information). Otherwise, assign the value of
y
x
to
y
. If
x
and
y
are not assigned yet, then create a new variable node
com
(
x,y
) which is called
common node of
x
and
y
and its two branch nodes are
x
and
y
respectively. The
domain of
. If the
intersection set is null, then return “inconsistent” information(fail information).
Constraint connections between
com
(
x,y
) is the intersection set of domains of
x
and
y
x
or
y
and other nodes, are all merged into
com
(
x,y
). All operations on
x
or
y
later will be implemented by operating on
com
).
In general, when a variable involves a lot of equation constraints, such as the
equation set {
(
x,y
x=y
,
y=z
,
x=u
}, our method will form a big binary tree.
