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. == The algorithm == AC-3 operates on constraints, variables, and the variables' domains. 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''. 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. 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) } and { (y, x) | there exists a relation R2(x,y) } 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 } 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 all constraints 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 big O notation(''ed''3), 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. Algorithms
See other meanings of words starting from letter:
Words begining with AC-3_algorithm:
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. == The algorithm == AC-3 operates on constraints, variables, and the variables' domains. 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''. 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. 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) } and { (y, x) | there exists a relation R2(x,y) } 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 } 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 all constraints 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 big O notation(''ed''3), 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. Algorithms
See other meanings of words starting from letter:
A
AB | AC | AD | AE | AF | AG | AH | AI | AJ | AK | AL | AM | AN | AO | AP | AR | AS | AT | AU | AW | AX | AY | AZ |Words begining with AC-3_algorithm:
AC-3_algorithm
Sponsored links: praca.
These materials are based on Wikipedia and licensed under the GNU FDL
Untitled Document
| Linki sponsorowane | Tani hosting | Pozycjonowanie |
YouTube.com videos better site than Turbo Tax 2007
