AC-3 algorithm


AC-3 algorithm

The AC-3 algorithm (short for Arc Consistency Algorithm #3) is one of a series of algorithms used for the solution of constraint satisfaction problems (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.

The algorithm

AC-3 operates on constraints, 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.

References

* A.K. Mackworth. [http://citeseer.ist.psu.edu/context/1023/0 Consistency in networks of relations] . "Artificial Intelligence", 8:99-118, 1977.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Algorithm design — is a specific method to create a mathematical process in solving problems. Applied algorithm design is algorithm engineering.Algorithm design is identified and incorporated into many solution theories of operation research, such as dynamic… …   Wikipedia

  • Algorithm engineering — is a combination of theoretical algorithm design with real world data. By taking an algorithm and combining it with a hardware device connected to the real world, you are able to more accurately verify and validate the algorithm results and… …   Wikipedia

  • algorithm — UK US /ˈælgərɪðəm/ noun [C] IT ► a set of mathematical instructions that must be followed in a fixed order, and that, especially if given to a computer, will help to calculate an answer to a mathematical problem: a computer/mathematical/search… …   Financial and business terms

  • algorithm — n. a precise rule (or set of rules) specifying how to solve some problem; a set of procedures guaranteed to find the solution to a problem. Syn: algorithmic rule, algorithmic program [WordNet 1.5 +PJC] …   The Collaborative International Dictionary of English

  • algorithm — [al′gə rith΄əm] n. [altered (after ARITHMETIC) < ALGORISM] 1. Math. a) any systematic method of solving a certain kind of problem b) the repetitive calculations used in finding the greatest common divisor of two numbers: called in full… …   English World dictionary

  • Algorithm Builder — ist eine Entwicklungsumgebung für AVR Mikrocontroller, basierend auf einer graphischen Makro Assembler Sprache. Der gesamte Programmablauf wird in graphischer Form als Flussdiagramm eingegeben. Es lässt sich mit einzelnen Anweisungen direkt auf… …   Deutsch Wikipedia

  • Algorithm —   [engl.], Algorithmus.   …   Universal-Lexikon

  • algorithm — (n.) 1690s, from Fr. algorithme, refashioned (under mistaken connection with Gk. arithmos number ) from O.Fr. algorisme the Arabic numeral system (13c.), from M.L. algorismus, a mangled transliteration of Arabic al Khwarizmi native of Khwarazm,… …   Etymology dictionary

  • algorithm — ► NOUN ▪ a process or set of rules used in calculations or other problem solving operations. DERIVATIVES algorithmic adjective. ORIGIN Latin algorismus, from an Arabic word meaning the man of Kw rizm , referring to a 9th century mathematician …   English terms dictionary

  • Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… …   Wikipedia

  • Algorithm characterizations — The word algorithm does not have a generally accepted definition. Researchers are actively working in formalizing this term. This article will present some of the characterizations of the notion of algorithm in more detail. This article is a… …   Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.