Information Technology Reference
In-Depth Information
[
l
x
, g
x
] and [
l
y
, g
y
] respectively, then after constraints propagate, the interval of
variable
x
and
y
are
[max(
l
x
, l
y
) ,
g
x
]
[
l
y
, min(
g
x
, g
y
) ]
If
l
y
, then it means the contradiction.
This reasoning can be promoted to more complicated equation or inequality
as well. Consider equation
g
x
<
x +y =z
, and current interval of variable
x
,
y
and
z
are
[
l
x
,
g
x
], [
l
y
,
g
y
]and [
l
z
,
g
z
] respectively. if
l
x
+
l
y
> g
z
or
g
x
+ g
y
<l
z
, it means the
contradiction. Otherwise the
z'
s new interval values of [
l'
z
,
g'
z
] are
l'
z
= max(l
x
+ l
y
, l
z
)
g'
z
= min(g
x
+ g
y
, g
z
)
x'
s new interval values of [
l'
x
,
g'
x
] are
l'
x
= max(l
z
- g
y
, l
x
)
g'
x
= min(g
z
- l
y
, g
x
)
y'
s new interval values of [
l'
y
,
g'
y
] are
l'
y
= max(l
z
- g
x
, l
y
)
g'
y
= min(g
z
- l
x
, g
y
)
3.10.3
Inequality Graph
In many AI applications such as qualitative reasoning, temporal reasoning and
activity planning, what they care about is the relative relation among variables.
Therefore the reasoning of ordering relation is very important. This is actually
reasoning on axioms of inequality, such as identical relation, partial order
relation etc..
All inequalities which are similar to
x
≤
y
and
x
≠
y
are used to made up an
inequality graph. Relation
x
≥
y
is represented as
y
≤
x
, and
x <y
is represented as
x
≤
y
and
x
≠
y
, and
x > y
is represented as
y
≤
x
with
x
≠
y
(identical relation has
been implemented by unit sharing strategy).
Definition 3.1
inequality graph is a marked graph <V, E>, in
which V is a set of nodes and E is a set of xry relations, where x,y
∈
V and r
denotes
≤
or
≠
relation. A positive path in graph is a node series v
1
,v
2
,...,v
i
,, such
that for i (i =2,... ,l),(v
i-1
≤
v
i
) is a edge in the graph. If v
1
=v
l
, then the path is
called positive cycle.
Positive Cycle
. A
Obviously, the inequality graph has the following properties:
