AC-3 algorithm
Encyclopedia
The AC-3 algorithm
(short for Arc Consistency Algorithm #3) is one of a series of algorithms used for the solution of constraint satisfaction problem
s (or CSP's). It was developed by Alan Mackworth
in 1977. The earlier AC algorithms are often considered too inefficient, and many of the later ones are difficult to implement, and so AC-3 is the one most often taught and used in very simple constraint solvers.
s, variables
, and the variables' domains (scopes). A variable can take any of several discrete values; the set of values for a particular variable is known as its domain. A constraint is a relation
that limits or constrains the values a variable may have. The constraint may involve the values of other variables.
The CSP can be viewed as a directed graph
, where the nodes are the variables of the problem, with edges or arcs between variables that are related by constraints. AC-3 proceeds by examining the arcs between pairs of variables (x, y). It removes those values from the domains of x and y which aren't consistent with the constraints between x and y. The algorithm keeps a collection of arcs that are yet to be checked; when the domain of a variable has any values removed, all the arcs of constraints including that variable (except the current one) are added to the collection. Since the domains of the variables are finite and either one arc or one value are removed at each step, this algorithm is guaranteed to terminate
.
For illustration, here is an example of a very simple constraint problem:
X (a variable) has the possible values {0, 1, 2, 3, 4, 5} -- the set of these values are the domain of X, or D(X). The variable Y likewise has the domain D(Y) = {0, 1, 2, 3, 4, 5}. Together with the constraints C1 = "X must be even" and C2 = "X + Y must equal 4" we have a CSP which AC-3 can solve. Notice that the actual constraint graph representing this problem must contain two edges between X and Y since C2 is undirected but the graph representation being used by AC-3 is directed.
It does so by first removing the non-even values out of the domain of X as required by C1, leaving D(X) = { 0, 2, 4 }. It then examines the arcs between X and Y implied by C2. Only the pairs (X=0, Y=4), (X=2, Y=2), and (X=4, Y=0) match the constraint C2. AC-3 then terminates, with D(X) = {0, 2, 4} and D(Y) = {0, 2, 4}.
AC-3 is expressed in pseudocode as follows:
Input:
A set of variables
X
A set of domains D(x) for each variable x in X. D(x) contains vx0, vx1... vxn, the possible values of x
A set of unary constraints R1(x) on variable x that must be satisfied
A set of binary constraints R2(x, y) on variables x and y that must be satisfied
Output:
Arc consistent domains for each variable.
function ac3 (X, D, R1, R2)
// Initial domains are made consistent with unary constraints.
for each x in X
D(x) := { x in D(x) | R1(x) }
// 'worklist' contains all arcs we wish to prove consistent or not.
worklist := { (x, y) | there exists a relation R2(x, y) or a relation R2(y, x) }
do
select any arc (x, y) from worklist
worklist := worklist - (x, y)
if arc-reduce (x, y)
if D(x) is empty
return failure
else
worklist := worklist + { (z, x) | z != y and there exists a relation R2(x, z) or a relation R2(z, x) }
while worklist not empty
function arc-reduce (x, y)
bool change = false
for each vx in D(x)
find a value vy in D(y) such that vx and vy satisfy the constraint R2(x, y)
if there is no such vy {
D(x) := D(x) - vx
change := true
}
return change
The algorithm has a worst-case time complexity of O
(ed3) and space complexity of O
(e), where e is the number of arcs and d is the size of the largest domain.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
(short for Arc Consistency Algorithm #3) is one of a series of algorithms used for the solution of constraint satisfaction problem
Constraint satisfaction problem
Constraint satisfaction problems s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint...
s (or CSP's). It was developed by Alan Mackworth
Alan Mackworth
Alan Mackworth is a Professor of Computer Science and Canada Research Chair in Artificial Intelligence in the Department of Computer Science at the University of British Columbia.-Education:...
in 1977. The earlier AC algorithms are often considered too inefficient, and many of the later ones are difficult to implement, and so AC-3 is the one most often taught and used in very simple constraint solvers.
The algorithm
AC-3 operates on constraintConstraint (mathematics)
In mathematics, a constraint is a condition that a solution to an optimization problem must satisfy. There are two types of constraints: equality constraints and inequality constraints...
s, variables
Variable (mathematics)
In mathematics, a variable is a value that may change within the scope of a given problem or set of operations. In contrast, a constant is a value that remains unchanged, though often unknown or undetermined. The concepts of constants and variables are fundamental to many areas of mathematics and...
, and the variables' domains (scopes). A variable can take any of several discrete values; the set of values for a particular variable is known as its domain. A constraint is a relation
Relation (mathematics)
In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
that limits or constrains the values a variable may have. The constraint may involve the values of other variables.
The CSP can be viewed as a directed graph
Directed graph
A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...
, where the nodes are the variables of the problem, with edges or arcs between variables that are related by constraints. AC-3 proceeds by examining the arcs between pairs of variables (x, y). It removes those values from the domains of x and y which aren't consistent with the constraints between x and y. The algorithm keeps a collection of arcs that are yet to be checked; when the domain of a variable has any values removed, all the arcs of constraints including that variable (except the current one) are added to the collection. Since the domains of the variables are finite and either one arc or one value are removed at each step, this algorithm is guaranteed to terminate
Termination analysis
In computer science, a termination analysis is program analysis which attempts to determine whether the evaluation of a given program will definitely terminate. Because the halting problem is undecidable, termination analysis cannot work correctly in all cases. The aim is to find the answer...
.
For illustration, here is an example of a very simple constraint problem:
X (a variable) has the possible values {0, 1, 2, 3, 4, 5} -- the set of these values are the domain of X, or D(X). The variable Y likewise has the domain D(Y) = {0, 1, 2, 3, 4, 5}. Together with the constraints C1 = "X must be even" and C2 = "X + Y must equal 4" we have a CSP which AC-3 can solve. Notice that the actual constraint graph representing this problem must contain two edges between X and Y since C2 is undirected but the graph representation being used by AC-3 is directed.
It does so by first removing the non-even values out of the domain of X as required by C1, leaving D(X) = { 0, 2, 4 }. It then examines the arcs between X and Y implied by C2. Only the pairs (X=0, Y=4), (X=2, Y=2), and (X=4, Y=0) match the constraint C2. AC-3 then terminates, with D(X) = {0, 2, 4} and D(Y) = {0, 2, 4}.
AC-3 is expressed in pseudocode as follows:
Input:
A set of variables
Variable (mathematics)
In mathematics, a variable is a value that may change within the scope of a given problem or set of operations. In contrast, a constant is a value that remains unchanged, though often unknown or undetermined. The concepts of constants and variables are fundamental to many areas of mathematics and...
X
A set of domains D(x) for each variable x in X. D(x) contains vx0, vx1... vxn, the possible values of x
A set of unary constraints R1(x) on variable x that must be satisfied
A set of binary constraints R2(x, y) on variables x and y that must be satisfied
Output:
Arc consistent domains for each variable.
function ac3 (X, D, R1, R2)
// Initial domains are made consistent with unary constraints.
for each x in X
D(x) := { x in D(x) | R1(x) }
// 'worklist' contains all arcs we wish to prove consistent or not.
worklist := { (x, y) | there exists a relation R2(x, y) or a relation R2(y, x) }
do
select any arc (x, y) from worklist
worklist := worklist - (x, y)
if arc-reduce (x, y)
if D(x) is empty
return failure
else
worklist := worklist + { (z, x) | z != y and there exists a relation R2(x, z) or a relation R2(z, x) }
while worklist not empty
function arc-reduce (x, y)
bool change = false
for each vx in D(x)
find a value vy in D(y) such that vx and vy satisfy the constraint R2(x, y)
if there is no such vy {
D(x) := D(x) - vx
change := true
}
return change
The algorithm has a worst-case time complexity of O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(ed3) and space complexity of O
Big O notation
In mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(e), where e is the number of arcs and d is the size of the largest domain.