AC-3-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
QS-Informatik

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+)
Begründung: Quellen und fachliche Überarbeitung, z. B. der Satz "Weil AC-3 schwierig zu implementieren ist, wird es in der Lehre am häufigsten eingesetzt". Ist er denn im Vergleich zu den anderen effektiv? --Dr. Slow Decay (Diskussion) 12:58, 7. Jul. 2012 (CEST)

Der AC-3-Algorithmus (von englisch arc consistency algorithm, dt.: Kantenkonsistenz-Algorithmus) ist ein Algorithmus zur Lösung von Constraint-Erfüllungsproblemen (CSPs). Er wurde 1977 von Alan Mackworth entwickelt[1]. Während frühere AC Algorithmen oftmals zu ineffizient waren, sind Nachfolger des AC-3 in der Regel deutlich schwieriger zu implementieren, dies macht den AC-3 in der Lehre zum meist verwendeten Algorithmus.

Der Algorithmus[Bearbeiten]

AC-3 arbeitet auf den Domänen von Variablen in Constraint-Erfüllungsproblemen. Eine Variable kann hier jeden Wert einer festgelegten Menge, ihrer Domäne, annehmen. Diese Belegungen der Variablen werden durch klar definierte Regeln (Constraints) eingeschränkt. Diese Constraints können die Belegungen anderer Variablen beinhalten.

Ein CSP kann als gerichteter Graph betrachtet werden, wobei die Knoten den Variablen des Problems entsprechen und die Kanten für Constraints stehen. AC-3 untersucht die Kanten zwischen Variablen-Paaren (x, y). Es werden jene Werte aus den Domänen von x und y entfernt, die nicht mit den Constraints zwischen x und y konsistent sind. Der Algorithmus speichert die Kanten, die noch geprüft werden müssen. Wenn Werte aus der Domäne einer Variable entfernt werden, werden alle Kanten (Constraints) an dieser Variable der Menge der noch zu prüfenden Kanten hinzugefügt. Da die Domänen von Variablen endlich sind - und in jedem Schritt entweder eine Kante oder eine Variable entfernt werden - terminiert der Algorithmus garantiert.

Ein Beispiel anhand eines einfachen Problems: Es sei eine Variable X mit der Domäne D(X) = {0, 1, 2, 3, 4, 5} gegeben. Außerdem sei eine Variable Y mit D(Y) = {0, 1, 2, 3, 4, 5} gegeben. Die Constraints seien C1 = "X sei gerade" und C2 = "X + Y = 4". Da AC-3 in einem gerichteten Graphen repräsentiert wird, existieren dabei aufgrund von C2 zwei Kanten zwischen X und Y.

Bei Anwendung von AC-3 werden zunächst die ungeraden Werte der Domäne von X entfernt, wodurch alle verbleibenden Belegungsmöglichkeiten für X (D(X) = { 0, 2, 4 }) den Constraint C1 erfüllen. Anschließend werden die Kanten zwischen X und Y untersucht. Constraint C2 wird nur durch die Belegungen (X=0, Y=4), (X=2, Y=2), and (X=4, Y=0) erfüllt. AC-3 terminiert mit D(X) = {0, 2, 4} und 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

Der Algorithmus hat eine Worst-Case-Zeit-Komplexität von O(ed3), Worst-Case-Speicher-Komplexität: O(e), wobei e die Anzahl der Kanten und d die Größe der größten Domäne ist.

Belege[Bearbeiten]

  1. Alan K. Mackworth: Consistency in Networks of Relations. In: Artificial Intelligence. Bd. 8, Nr. 1, Februar 1977, ISSN 0004-3702, S. 99–118, doi:10.1016/0004-3702(77)90007-8.