![]() 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 pointing to that pruned variable (except the arc of the current constraint) are added to the collection. ![]() It removes those values from the domain of x which aren't consistent with the constraints between x and y. AC-3 proceeds by examining the arcs between pairs of variables ( x, y). The current status of the CSP during the algorithm 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 symmetric constraints, where each arc in the worklist represents a constraint that needs to be checked for consistency. The constraint may involve the values of other variables. A constraint is a relation that limits or constrains the values a variable may have. A variable can take any of several discrete values the set of values for a particular variable is known as its domain. 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.ĪC-3 operates on constraints, variables, and the variables' domains (scopes). It was developed by Alan Mackworth in 1977. In constraint satisfaction, 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).
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |