Information Technology Reference
In-Depth Information
select and delete any arc(
V
k
,
V
m
) from Q;
if (REVISE(
V
k
,
V
m
)) then
Q
ŕ
{(
V
i
,
V
k
) such that (
V
i
,
V
k
) ∈ arcs(
G
) ,
i
≠
k,i
≠
m
}
End if;
End while;
end AC-3
The famous algorithm of Waltz(Waltz, 1975) is a special case of this
algorithm and equivalent to another algorithm AC-2 proposed by Mackworth.
Suppose that the domain size for each variable is
d
, and the total number of
constraints network is
e
. The complexity of arc-consistency algorithm proposed
3
). Mohr and Henderson proposed another arc-consistency
algorithm(Mohr, 1986), whose complexity is O(
by Mackworth is O(
ed
2
). Therefore, Mohr and
Henderson's algorithm is optimal considering worst-case complexity.
Given an arc-consistent constraint network, is there an instantiation of the
variable from current domains make the variable become a solution to CSP? If
the domain size of each variable becomes one after obtaining arc consistency,
then the network has exactly one solution. Otherwise, the answer is no in general.
Nevertheless, arc-consistent algorithms reduce the search space of backtracking.
Since arc-consistency algorithm has not enough ability to replace
backtracking, can another stronger consistent algorithm eliminate the search need
in backtracking? The notion of K consistency captures different degrees of
consistency for different values of K. A constraint network is K consistent if the
following is true: Choose values of any K-1 variables that satisfy all the
constraints among these variables, then choose any Kth variable. A value for this
variable exists that satisfies all the constraints among these K variables. The
exactly formal description is as following:
Suppose that the variables
ed
x
1
,
x
2
,…,
x
k-1
are instantiated by value
a
1
,
a
2
, … ,
a
k-1
separately. If each value of
a
1
,
a
2
, … ,
a
k-1
satisfy all the constraints among
x
1
,
x
2
,…,
x
k-1
,
x
k
, then for variable
x
k
, there is a value
a
k
to make value of
a
1
,
a
2
, … ,
a
k-1
,
a
k
satisfy all the constraints among
x
1
,
x
2
,…,
x
k-1
,
x
k
.
.
Node consistency is equivalent to strong 1 consistency. Arc consistency is
equivalent to strong 2 consistency. Algorithms exist to make a constraint network
strong
A constraint network is strong
K
consistent if it is
J
consistent for all
J
≤
K
> 2 (Cooper 1989). If a n-node constraint network is
strong n consistent, then a solution to CSP can be found without any search.
However, the worst-case complexity of the algorithm for obtaining n consistency
in a n-node constraint network is also exponential.
K
consistent for
K
