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):
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:
Abhilfe schafft in diesem Fall der von Freuder (1982) eingeführte Begriff der strengen k-Konsistenz (vgl. Güsgen, 2000, S. 271):
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 , 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.
|
Der von Freuder (1978) vorgestellte
Synthese-Algorithmus ist in
der Lage, für beliebige
, 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
, 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).