AC-3 algorithm
This product was added to computer science because of the content, defects on the quality assurance side of the editor. This is done to bring the quality of the articles from the computer science subject area to an acceptable level. Help us to eliminate the substantive shortcomings of this article and take part you in the discussion! ( ) Reason: sources and technical revision, for example, the sentence "Because AC-3 is difficult to implement, it is used in teaching most ". Is he in comparison to the other effectively? - Dr. Slow Decay (talk) 12:58, July 7, 2012 (UTC)
The AC-3 algorithm ( from English- arc consistency algorithm, dt: arc consistency algorithm ) is an algorithm for solving constraint compliance problems ( CSPs ). It was developed in 1977 by Alan Mackworth. While previous AC algorithms were often too inefficient, successor to the AC-3 are generally much more difficult to implement, this makes the AC-3 in teaching the algorithm most widely used.
The algorithm
AC - 3 operates in the domains of variables in constraint fulfillment problems. A variable can take on any value of a specified amount of their domain, here. These assignments of the variables are constrained by clearly defined rules (constraints ). These constraints can include the assignment of other variables.
A CSP can be viewed as a directed graph, where the nodes correspond to the variables of the problem and are the edges for constraints. AC-3 examines the edges between pairs of variables (x, y). It will be removed from the domains of x and y are the values that are not consistent with the constraints between x and y is consistent. The algorithm stores the edges that still need to be checked. When values are removed from the domain of a variable, all edges are added (constraints ) on this variable, the amount of edges still to be tested. Since the domains of variables are finite - and in each step either an edge or a variable to be removed - the algorithm terminates guaranteed.
An example of using a simple problem: It is to be given a variable X with the domain D (x) = {0, 1, 2, 3, 4, 5}. In addition, a variable Y D ( y) = {0, 1, 2, 3, 4, 5} is given. The constraints are C1 = " X is even" and C2 = " X Y = 4". Since AC-3 is represented in a directed graph, there are two edges thereby due C2 between X and Y.
First the odd values of the domain of X ( D ( X) = { 4 0, 2,} ) In the application of AC -3 are removed, leaving all remaining assignment possibilities for X satisfy the constraint C1. Subsequently, the edges between X and Y to be examined. Constraint C2 is satisfied only by the assignments (X = 0, Y = 4), ( X = 2, Y = 2), and (X = 4, Y = 0). AC-3 terminated with D (x) = {0, 2, 4 } and D ( Y) = {0, 2, 4}.
AC-3 in pseudocode:
Function AC3 / / Reduced domains queue = all edges of the CSP while (! empty ( queue) ) Removing an edge ( x, y) in queue; if ( EntferneInkonsistenteWerte (x, y)) foreach (neighbor z of x) queue.ADD ( edge (z, x)) function AC3 end EntferneInkonsistenteWerte function (x, y) / / Returns true if the domain D (x ) is reduced removed = false foreach (value v1 in D ( x)) if ( v2 No D (Y ) such that (x = v1, v2 = y ) satisfies all the constraints of (x, y)) D (x). CLEAR (V1) removed = true return removed function EntferneInkonsistenteWerte end The algorithm has a worst case time complexity of O ( ED3 ), worst case storage complexity is O ( e), where e is the number of edges, and d is the size of the largest domain.
Documents
- Algorithm