5.2.3.5 k-Konsistenz

Das Konzept der Knoten-, Kanten- und Pfadkonsistenz wurde von Eugene C. Freuder um den Begriff der k-Konsistenz erweitert (vgl. Freuder, 1978). Die k-Konsistenz ist eine Verallgemeinerung der bisher genannten Konsistenzgrade und garantiert, dass in einem Constraint-Netz für jede Menge von (k-1)-konsistent belegten Variablen eine konsistente Belegung der k-ten Variable existiert (vgl. Güsgen, 2000, S. 270):

Definition 5.2.10   (k-Konsistenz/k-consistency)
Gegeben sei ein beliebiges CSP auf den Variablen $v_1,\ldots,v_n$ mit den Wertebereichen $D_1,\ldots,D_n$. Sei $(d_{i_1},\ldots,d_{i_{(k-1)}}) \in D_{i_1} \times \cdots \times D_{i_{(k-1)}}$ mit $i_j \in \{1,\ldots,n\}$ für $j = \{1,\ldots,k\}$ eine Zuweisung von Werten an $(k-1)$ paarweise verschiedene Variablen, die alle Constraints zwischen den Variablen erfüllt. Das Netz ist k-konsistent, wenn durch Hinzunahme einer beliebigen weiteren Variablen $v_{i_k}, k \in \{1,\ldots,n\}$, die Wertezuweisung zu $(d_{i_1},\ldots,d_{i_k}) \in D_i \times \cdots \times D_{i_k}$ so erweitert werden kann, dass alle Constraints zwischen den k Variablen erfüllt sind.

Es ist wichtig festzustellen, dass k-Konsistenz nicht automatisch impliziert, dass ein Constraint-Netz ebenfalls (k-1)-konsistent ist. Ein einfaches Beispiel nach Freuder (1982, S. 26 f.) ist in Abbildung 5.10 zu sehen:

Beispiel 5.2.3   Das dargestellte Constraint-Netz in Abbildung 5.10 ist 3-konsistent aber nicht 2-konsistent. 2-Konsistenz ist deshalb ausgeschlossen, weil es für die Belegung $v_2 = 1$ weder eine konsistente Belegung für $v_1$ noch für $v_3$ gibt, so dass die Constraints $C_{1,2}$ und $C_{2,3}$ erfüllt würden. 3-Konsistenz hingegen ist sichergestellt, da sich, wie von der Definition gefordert, alle konsistenten Belegungen von zwei Variablen um eine dritte Variable mit konsistenter Belegung erweitern lassen: $v_1=1, v_2=2, v_3=1$.

Abbildung 5.10: 3-konsistentes, jedoch nicht 2-konsistentes Constraint-Netz

Abhilfe schafft in diesem Fall der von Freuder (1982) eingeführte Begriff der strengen k-Konsistenz (vgl. Güsgen, 2000, S. 271):

Definition 5.2.11   (strenge k-Konsistenz/strong k-consistency)
Ein Constraint-Netz ist streng k-konsistent, wenn es i-konsistent ist für alle $1 \leq i \leq k$.

Nach diesen Definitionen ist Knotenkonsistenz äquivalent zur 1-Konsistenz, Kantenkonsistenz äquivalent zur strengen 2-Konsistenz und Pfadkonsistenz äquivalent zur strengen 3-Konsistenz vgl. Barták, 1999a, S. 558; Barták, 1999b, S. 10. Wenn ein CSP mit n Variablen streng n-konsistent ist, sind die Wertebereiche aller Constraint-Variablen minimal, d.h. sie können nicht weiter eingeschränkt werden, ohne dass mögliche Lösungen verloren gehen. In diesem Zustand ist ein CSP global konsistent. Globale Konsistenz garantiert Konfliktfreiheit und erlaubt dadurch die Generierung einer konsistenten Lösung in linearer Zeit. Die Wertebereiche der Constraint-Variablen enthalten ausschließlich Werte, die Teil einer Lösung sind. Somit lässt sich jede konsistente Teilbelegung der Constraint-Variablen zu einer vollständigen Lösung des CSP erweitern, ohne dass Backtracking angewendet werden muss (vgl. Abschnitt 5.2.4.2).

Eine interessante Beobachtung geht auf die von Freuder (1982, S. 30 f.) beschriebenen Zusammenhänge zurück. Demnach kann in einem knoten- und kantenkonsistenten, binären CSP,^5.31 dessen Constraint-Graph einen Baum darstellt und demnach keine Zyklen enthält (engl. tree-structured), eine Lösung in linearer Zeit ohne jegliches Backtracking der Suchstrategie gefunden werden (engl. backtrack-free).^5.32 Das heißt in einem azyklischem Constraint-Netz ist diese Form lokaler Konsistenz gleichbedeutend mit globaler Konsistenz. In Abhängigkeit von der Struktur des Constraint-Graphen ist man daher sehr an effizienten Verfahren zur Herstellung lokaler Konsistenz interessiert (vgl. Mackworth und Freuder, 1985; Dechter und Pearl, 1989,1987; Dechter, 1992).

Allgemein allerdings impliziert k-Konsistenz nicht, dass ein CSP lösbar ist.^5.33 Auch für ein Constraint-Netz, welches streng k-konsistent ist, mit $k<n$, lässt sich Backtracking bei einem anschließenden Suchverfahren zum Generieren einer Lösung nicht ausschließen, da das Constraint-Netz weiterhin inkonsistente Wertekombinationen enthalten kann. Umgekehrt impliziert eine Lösung nicht k-Konsistenz, d.h. eine Lösung setzt nicht voraus, dass ein Constraint-Netz einen bestimmten Konsistenzgrad aufweist (vgl. Tsang, 1993, S. 64 f.). Wie bereits erwähnt, werden Konsistenz- und Suchverfahren häufig kombiniert, um ein CSP effizient zu lösen. Die Effizienz von Suchverfahren kann gesteigert werden, indem Konsistenzverfahren zur Reduzierung des Suchraums zum Einsatz kommen. Allerdings erfordert die Anwendung von Konsistenzverfahren ebenfalls einen nicht unerheblichen Aufwand (siehe Tabelle 5.1). Je mehr Aufwand in die Problemreduktion investiert wird, umso weniger Aufwand wird bei einem anschließenden Suchverfahren zur Auffindung von Lösungen des Problems benötigt. In Abbildung 5.11 ist grob die Beziehung zwischen dem Aufwand zur Problemreduktion und dem Aufwand zur Lösungssuche skizziert. In der Praxis muss häufig eine Balance zwischen beiden gefunden werden.

Abbildung 5.11: Aufwand von Problemreduktion vs. Suchaufwand (vgl. Tsang, 1993, S. 42)

Tabelle 5.1: Übersicht über die worst-case Zeit- und Platzkomplexitäten

e = Anzahl der Constraints
d = Kardinalität der größten Domäne
n = Anzahl der Variablen
	worst-case	worst-case
Algorithmus	Zeitkomplexität	Platzkomplexität
NC-1 (Mackworth, 1977a)	$O(nd)$	$O(nd)$
AC-1 (Mackworth, 1977a)	$O(ned^3)$	$O(e+nd)$
AC-3 (Mackworth, 1977a)	$O(ed^3)$	$O(e+nd)$
AC-4 (Mohr und Henderson, 1986)	$O(ed^2)$	$O(ed^2)$
AC-5 (Van Hentenryck et al., 1992)	$O(ed)$ (nur für bestimm-	$O(ed+nd)$
	te Constraint-Klassen)
AC-6 (Bessière und Cordier, 1993;	$O(ed^2)$	$O(ed)$
Bessière, 1994a)
AC-7 (Bessière et al., 1995,1999a)	$O(ed^2)$	$O(ed)$
AC-8 (Chmeiss und Jégou, 1998,1996b)	$O(ed^3)$	$O(n)$
AC-2000 (Bessière und Régin, 2001a)	$O(ed^3)$	$O(nd)$
AC-2001 (Bessière und Régin, 2001a)	$O(ed^2)$	$O(ed)$
AC-3.1 (Zhang und Yap, 2001)	$O(ed^2)$	$O(ed)$
AC-$3_d$ (van Dongen, 2002b,a)	$O(ed^3)$	$O(e+nd)$
PC-1 (Mackworth, 1977a)	$O(n^5d^5)$	$O(n^3,d^2)$
PC-2 (Mackworth, 1977a)	$O(n^3d^5)$	$O(n^3+n^2d^2)$
PC-3 (Mohr und Henderson, 1986)	$O(n^3d^3)$	$O(n^3d^3)$
PC-4 (Han und Lee, 1988)	$O(n^3d^3)$	$O(n^3d^3)$
PC-5/PC-6 (Chmeiss und Jégou, 1995;	$O(n^3d^3)$	$O(n^3d^2)$
Chmeiss, 1996; Singh, 1995)
PC-7 (Chmeiss und Jégou, 1996a)	$O(n^3d^4)$	$O(n^2d^2)$
PC-8 (Chmeiss und Jégou, 1998,1996b)	$O(n^3d^4)$	$O(n^2d)$
Freuders Synthese-Algorithmus	$O(2^n+nd^{2n})$	$O(2^nd^n)$
(Freuder, 1978)

Der von Freuder (1978) vorgestellte Synthese-Algorithmus ist in der Lage, für beliebige $k \in \{1,\ldots,n\}$, wobei n die Anzahl der Variablen des CSP darstellt, in einem Constraint-Netz strenge k-Konsistenz herzustellen. Dazu konstruiert der Algorithmus nach und nach Constraints mit zunehmender Stelligkeit und fügt diese dem Constraint-Netz hinzu, bis nach k Durchläufen strenge k-Konsistenz erreicht ist. Eine Weiterführung dieses Algorithmus, der ebenfalls k-Konsistenz für beliebige k herstellt, wird von Martin C. Cooper vorgestellt. Coopers Algorithmus KS-1 ist optimal und nimmt Anleihen sowohl bei Freuders Arbeit als auch beim PC-4-Algorithmus (vgl. Cooper, 1989). Beide Algorithmen sind nicht auf binäre Constraints beschränkt, sondern können auf n-äre Constraint-Netze angewendet werden. Aufgrund des hohen Berechnungsaufwandes unterbleibt dies jedoch häufig in der Praxis.

Synthese-Algorithmen können auch dazu genutzt werden, in einem CSP mit n Variablen strenge n-Konsistenz, d.h. globale Konsistenz, herzustellen (engl. solution synthesis). So können Synthese-Algorithmen einerseits durch Berechnung von k-Konsistenz, mit $k<n$, als Preprozessor zur Reduktion des Lösungsraums dienen, um ggf. ein nachfolgendes Suchverfahren zu vereinfachen, andererseits können sie genutzt werden, durch Berechnung von n-Konsistenz, alle Lösungen eines CSP zu finden.^5.34 Allerdings sind Algorithmen, die strenge k-Konsistenz in einem Constraint-Netz herstellen, von exponentieller Komplexität. Grundsätzlich ist die Anwendung von Algorithmen, die einen hohen Konsistenzgrad herstellen und damit einen hohen Komplexitätsgrad aufweisen, immer dann sinnvoll, wenn sichergestellt ist, dass sie eine große Menge redundanter Werte aus den Domänen der Constraint-Variablen eines stark beschränkten Problems entfernen und die Effizienz eines nachfolgenden Suchverfahrens dadurch entsprechend gesteigert wird (vgl. Tsang, 1993, S. 136).

Fußnoten

...^5.31

DAC ist in diesem Fall ausreichend vgl. Dechter und Pearl, 1987, S. 11; Tsang, 1993, S. 63 und Abschnitt 5.2.3.6.

...^5.32

Vgl. minimal width ordering, Abschnitt 5.2.5.1.

...^5.33

Ein kanten- oder pfadkonsistentes Constraint-Netz besitzt nicht zwangsläufig eine Lösung.

...^5.34

Das k-stellige Constraint, welches der Synthese-Algorithmus von Freuder (1978) berechnet, stellt die Menge der Lösungen des CSP dar, so dass die Anwendung eines Suchverfahrens entfällt.