AC-3 algorithm
The AC-3 algorithm (from English arc consistency algorithm , German: edge consistency algorithm ) is an algorithm for solving constraint fulfillment problems (CSPs) with binary conditions. It was developed by Alan Mackworth in 1977 . While earlier AC algorithms were often inefficient, successors to the AC-3 are usually much more difficult to implement, which makes the AC-3 the most widely used algorithm in teaching.
The algorithm
AC-3 works on the domains of variables in constraint satisfaction problems. A variable can take on any value of a specified set, its domain . These assignments of the variables are restricted by clearly defined rules ( constraints ). These constraints can contain the assignments of other variables.
A CSP can be viewed as a directed graph, where the nodes correspond to the variables of the problem and the edges represent constraints. AC-3 examines the edges between pairs of variables ( x , y ). It removes those values from the domains of x and y that are inconsistent with the constraints between x and y . The algorithm saves the edges that still need to be checked. If values are removed from the domain of a variable, all edges (constraints) on this variable are added to the set of edges still to be checked. Since the domains of variables are finite - and either an edge or a variable are removed in each step - the algorithm is guaranteed to terminate.
An example based on a simple problem: Assume a variable X with the domain D ( X ) = {0, 1, 2, 3, 4, 5}. In addition, let a variable Y be given with D ( Y ) = {0, 1, 2, 3, 4, 5}. 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 between X and Y due to C2 .
When using AC-3, the odd values of the domain of X are first removed, whereby all remaining occupancy possibilities for X (D ( X ) = {0, 2, 4}) fulfill the constraint C1 . Then the edges between X and Y are examined. Constraint C2 is only fulfilled by the assignments ( X = 0, Y = 4), ( X = 2, Y = 2), and ( X = 4, Y = 0). AC-3 terminates with D ( X ) = {0, 2, 4} and D ( Y ) = {0, 2, 4}.
AC-3 in pseudocode:
function AC3 // Reduziert Domänen queue = Alle Kanten des CSP while (!empty(queue)) Entferne eine Kante (x, y) aus queue; if(EntferneInkonsistenteWerte(x, y)) foreach (Nachbar z von x) queue.ADD(Kante(z, x)) function AC3 end
function EntferneInkonsistenteWerte(x, y) // Liefert true, wenn Domäne D(x) reduziert wird removed = false foreach (Value v1 in D(x)) if(Kein v2 in D(Y), so dass (x=v1, y=v2) alle Constraints zwischen (x,y) erfüllt) D(x).LÖSCHE(v1) removed = true return removed function EntferneInkonsistenteWerte end
The algorithm has a worst-case time complexity of O ( ed 3 ), worst-case memory complexity: O ( e ), where e is the number of edges and d is the size of the largest domain.
supporting documents
- ^ Alan K. Mackworth: Consistency in Networks of Relations. In: Artificial Intelligence. Vol. 8, No. 1, February 1977, ISSN 0004-3702 , pp. 99-118, doi : 10.1016 / 0004-3702 (77) 90007-8 .