Information Technology Reference
In-Depth Information
return(1) ; /*Return no solution */
end BACKTRACK
Although backtracking is better than the generate-and-test method, it still has
low efficiency for nontrivial problems, that is because search in different paths of
the space keeps failing for the same reasons. Some researchers think that the
thrashing is caused by so-called local inconsistency. The simplest cause of
thrashing concerns the so-called node inconsistency. If a variable vi contains a
value a that does not satisfy the unary constraint on
v
i
to a always results in inconsistency. Another possible source of thrashing is so-
called arc inconsistency which is illustrated by the following example: Suppose
the variables are instantiated in the order
v
i
, then the instantiation of
v
1
, v
2
,··· ,v
i
, ···,v
j
, ···, v
n
. Suppose also
that the binary constraint between
v
i
and
v
j
is such that for
v
i
=a
, there is no value
for
v
j
would satisfy such constraint. The search will fail while instantiation is
tried with
v
j
and the failure will be repeated for each possible combination that
the variables
) can take.
Thrashing because of node inconsistency can be eliminated by removing
those values from the domains of each variable that does not satisfy unary
constraint. And the thrashing because of arc inconsistency can be eliminated by
arc consistency algorithm. In the next section, the formal definition of arc
consistency and corresponding algorithm will be presented.
v
r
(
i<r<j
3.3 Constraint Propagation
If for every value
x
in the current domain of
v
i
, there is some value
y
in the
domain of
v
j
such that
v
i
=
x
and
v
j
=
y
, which are permitted by the constraint
between
v
j
) is arc consistent. The concept of arc consistency
is directional, that is, if an arc(
v
i
and
v
j
, then arc(
v
i
,
v
i
,
v
j
) is consistent then it does not automatically
mean that arc(
v
j
,
v
i
) is consistent. For example, if the current domain of
v
1
is {a},
the current domain of
v
2
is {a, b} and the constraint between
v
1
and
v
2
is unequal,
v
1
,
v
2
) is consistent but arc(
v
2
,
v
1
) is not consistent. Because there does not
exist any value of
v
1
to satisfy the unequal constraint for
then arc(
v
2
=
b
. Obviously, an
arc(
v
j
) can be make consistent by deleting those values which do not satisfy
constraints. Furthermore, deletions of such values do not affect any solution of
original CSP. The following algorithm realizes such deletion operation.
v
i
,
Algorithm 3.2
Revised Constraint Propagation Algorithm[Mackworth 1977]
