AC-3 algorithm

This article was due to content flaws on the quality assurance side of the computer science editorial added. This is done in order to bring the quality of the articles from the subject area of ​​computer science to an acceptable level. Help to eliminate the shortcomings in this article and take part in the discussion !  ( + ) Reason: Sources are missing, e.g. B. the claim that it is the most widely used algorithm in teaching because its successors are more difficult to implement. Erik Streb del Toro ( discussion ) 1:20 am, Dec 28, 2016 (CET)

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 ³ ), worst-case memory complexity: O ( e ), where e is the number of edges and d is the size of the largest domain.

supporting documents

1. ^ 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 .