Neben den bisher vorgestellten Konsistenzgraden und Verfahren, gibt es noch eine Reihe weiterer bekannter Variationen, Kombinationen und Weiterführungen der bisher genannten Verfahren, die in diesem Abschnitt angesprochen werden. In der nachfolgenden, übersichtsartigen Auflistung werden die wesentlichen Merkmale jeweils kurz angesprochen:
Auch k-Konsistenz kann noch
weiter verallgemeinert werden. In einem
(i,j)-konsistenten Constraint-Netz können
i unterschiedliche, mit konsistenten Werten belegte
Variablen um j weitere Variablen zur einer
konsistenten Belegung erweitert werden
(vgl. Freuder, 1985, S. 757).
k-Konsistenz ist demnach
äquivalent zu (k-1,1)-Konsistenz. Für
entspricht
-Konsistenz der Kantenkonsistenz und für
entspricht
-Konsistenz der Pfadkonsistenz.
Strenge
-Konsistenz ist gegeben, wenn ein
Constraint-Netz
-konsistent ist, für alle
.
Algorithmen, die
-Konsistenz herstellen können,
besitzen eine hohe Platzkomplexität, da sie Tupel mit
i Werten verwalten müssen. Sie sind daher praktisch
häufig nicht nutzbar für
. Zudem belassen sie das
Constraint-Netz nicht in seinem ursprünglichen Zustand,
sondern überführen es in ein äquivalentes Constraint-Netz
(vgl. Barták, 2001, S. 11).
Da beim Erhöhen von i die effiziente Anwendbarkeit
von -Konsistenz stark nachlässt, wird bei der
inversen Konsistenz
belassen und stattdessen
j erhöht. Dementsprechend wird
(1,k-1)-Konsistenz k-inverse Konsistenz
bzw. engl. k-inverse consistency genannt
(vgl. Freuder und Elfe, 1996). (1,k-1)-Konsistenz
bedeutet, dass durch diesen Konsistenzgrad alle Werte entfernt
werden, die nicht um (k-1)-konsistente
Variablenbelegungen erweitert werden können
(vgl. Freuder, 1985). Inverse
Kantenkonsistenz ist äquivalent zur gewöhnlichen
Kantenkonsistenz (d.h.
-Konsistenz).
Inverse Pfadkonsistenz (engl. path inverse consistency, PIC) ist eine
inverse Konsistenz, die mehr inkonsistente Werte eliminiert als
Kantenkonsistenz, dabei allerdings nicht den Konsistenzgrad der
vollständigen Pfadkonsistenz erreicht. Der (inverse)
Konsistenzgrad erhöht sich mit der Größe von k,
allerdings steigt entsprechend auch die Zeitkomplexität
polynomial mit k. Daher ist auch inverse Konsistenz
für große k nur beschränkt anwendbar. Ein
optimaler, auf AC-7 basierender
Algorithmus PIC-2 wird von
Debruyne (2000) vorgestellt. Eine Variante ist die
neighborhood inverse consistency (NIC),
die sicherstellt, dass der Wert einer Variable um eine
konsistente Belegung aller unmittelbaren Nachbarn der Variable
erweitert werden kann (vgl. Freuder und Elfe, 1996).
Allerdings ist worst-case Zeitkomplexität von
NIC exponentiell. So würde in einem vollständigen
Constraint-Netz durch dieses Verfahren globale Konsistenz
hergestellt werden. Die Anwendung von NIC sollte
sich daher auf überschaubare, schwach beschränkte
Constraint-Netze begrenzen.
Einen Sonderfall stellt die lazy arc consistency dar
(vgl. Schiex et al., 1996): Im Gegensatz zur gewöhnlichen
Kantenkonsistenz, die die Domänen
der
Constraint-Variablen um alle kanteninkonsistenten Werte
reduziert, ist das Ziel von LAC das Erkennen von
Inkonsistenzen durch Herbeiführen eines
domain wipe out, d.h. der
Wertebereich einer Variablen enthält keine Elemente mehr.
Während Kantenkonsistenz für gewöhnlich eine maximale,
kantenkonsistente Teildomäne
zurückliefert, ist es bei LAC ausreichend, wenn
eine beliebige kantenkonsistente Teildomäne gefunden wird, die
lediglich eine konsistente Belegung enthalten muss, weil
dadurch nachgewiesen ist, dass ein
domain wipe out nicht
auftreten kann. Der von Schiex et al. (1996) vorgestellte
Algorithmus LAC
sowie die beiden
Varianten LAC
und
MinLAC
sind modifizierte
Versionen des AC-7-Algorithmus.
Rina Dechter und Judea Pearl stellen fest, dass es für
baumartige Constraint-Netze, die keine Zyklen enthalten, nicht
notwendig ist, vollständige Kantenkonsistenz herzustellen, um
eine Backtracking-freie Suchstrategie zu ermöglichen
(vgl. Dechter und Pearl, 1987, S. 10 ff.). Algorithmen
zur Herstellung von Kantenkonsistenz müssen, wie in
Abschnitt 5.2.3.3 angemerkt, den
REVISE-Algorithmus mehrfach auf einzelne Kanten
anwenden, da die Reduktion des Wertebereichs einer Variablen
aufgrund von Zyklen im Constraint-Netz Auswirkungen auf
Wertebereiche von vorher bereits eingeschränkten Variablen
haben kann. Algorithmen, die REVISE ausschließlich
auf geordnete Variablenpaare mit
anwenden,
stellen einen Konsistenzgrad her, der gerichtete
Kantenkonsistenz (engl. directional arc
consistency) genannt wird. Gerichtete Kantenkonsistenz ist
schwächer als vollständige Kantenkonsistenz lässt sich aber
erheblich effizienter, d.h. mit weniger Berechnungsaufwand
als AC-3 und weniger Speicherbedarf als
AC-4, herstellen.5.35 Eine geschickte
Anordnung der Variablen kann dabei die Reduzierung der Domänen
erhöhen.
Ähnlich wie DAC für AC existiert eine
abgeschwächte Form der Pfadkonsistenz, die gerichtete
Pfadkonsistenz (engl. directional path
consistency). Gerichtete Pfadkonsistenz nutzt wie
DAC eine geordnete Variablenliste. Es werden
grundsätzlich dieselben Umformungen vorgenommen, wie bei
normalen Pfadkonsistenz-Algorithmen, allerdings werden nur
ausgewählte Relationen mit Konsistenztests
unterzogen. Das Ergebnis ist ein Konsistenzgrad, der weniger
Berechnungsaufwand erfordert als vollständige Pfadkonsistenz,
dabei die Domänen der Constraint-Variablen allerdings um nicht
ganz so viele inkonsistente Wertekombinationen reduziert
(vgl. Dechter und Pearl, 1987, S. 14 ff.).
Aufgrund der dargelegten Nachteile wird Pfadkonsistenz relativ selten eingesetzt. Eine schwächere Form, die eine Kombination aus Pfad- und Kantenkonsistenz darstellt, ist die eingeschränkte Pfadkonsistenz (engl. restricted path consistency). Der RPC-1-Algorithmus von Berlandier (1995) basiert auf AC-4, erweitert um Filtermethoden der Pfadkonsistenz, die immer dann angewendet werden, wenn es für einen Wert einer Variable in einem (binären) Constraint nur eine einzige konsistente Wertekombination gibt, die das Constraint erfüllt (durch einen entsprechenden support-Eintrag, vgl. Abschnitt 5.2.3.3). Ist diese Wertekombination inkonsistent mit den übrigen Constraints, kann der ursprüngliche Wert aus seiner Domäne gelöscht werden. Im Gegensatz zu anderen Pfadkonsistenz-Algorithmen ändert RPC nur die Domänen der Constraint-Variablen, nicht hingegen das Constraint-Netz an sich durch Hinzufügen neuer Constraints. RPC ist schwächer als vollständige Pfadkonsistenz, reduziert die Domänen der Constraint-Variablen jedoch um mehr Werte als Kantenkonsistenz. Ein verbesserter Algorithmus RPC-2 und die Erweiterungen k-RPC und Max-RPC, die jeweils eigene, höhere Konsistenzgrade darstellen, werden von Debruyne und Bessière (1997a) bzw. Debruyne (1998) vorgestellt.5.36
Verfahren zum Herstellen von Singleton-Konsistenz sind generisch und können mit beliebigen Konsistenzverfahren kombiniert werden, um die Reduktion der Wertebereiche der Constraint-Variablen zu erhöhen (vgl. Prosser et al., 2000; Debruyne und Bessière, 1997b). Zum Erreichen von Singleton-Konsistenz wird nacheinander für alle Variablen geprüft, ob das Beschränken der jeweiligen Domäne auf ein einziges Element (engl. singleton) durch Anwenden von Konsistenztechniken zu einem inkonsistenten CSP, d.h. zu min. einem leeren Wertebereich, führt. Ist dies der Fall, kann der entsprechende Wert aus der Domäne gelöscht werden. Die Überprüfung muss jeweils für alle möglichen Werte einer Variablen durchgeführt werden. Zur Konsistenzüberprüfung sollte aus Komplexitätsgründen eine lokale Konsistenz hergestellt werden, z.B. Kantenkonsistenz (singleton arc consistency, SAC)5.37 oder beschränkte Pfadkonsistenz (singleton restricted path consistency, SRPC). Wenn lokale Konsistenz mit polynomialen Zeitaufwand hergestellt werden kann, besitzt die entsprechende Singleton-Konsistenz ebenfalls polynomiale worst-case Zeitkomplexität.
Adaptive Konsistenz ist eine gerichtete, globale Konsistenz bezogen auf eine bestimmte Anordnung der Variablen, d.h. es wird globale Konsistenz für eine gegebene Ordnung der Variablen hergestellt (vgl. Dechter und Pearl, 1987, S. 17 ff.). Das Verfahren wird adaptiv genannt, weil die Eigenschaften des Constraint-Graphen die anzuwendenden Konsistenztechniken beeinflussen. Die Variablen werden in der gegebenen Ordnung absteigend bearbeitet. Es wird dabei Konsistenz mit den jeweils übergeordneten Variablen hergestellt, d.h. für eine Variable mit einem Vorgänger wird Kantenkonsistenz hergestellt, bei zwei Vorgängern entsprechend Pfadkonsistenz usw. Das Ergebnis ist ein geordneter Constraint-Graph, aus dem Lösungen mittels systematischer Suche ohne Anwendung von Backtracking generiert werden können. Allerdings wird hierfür exponentielle Zeit- und Platzkomplexität in Anspruch genommen. Zudem wird bei Anwendung entsprechender Konsistenzverfahren (Pfadkonsistenz) der Constraint-Graph modifiziert.
Diese Auflistung erhebt keinen Anspruch auf Vollständigkeit. Sie zeigt allerdings auf, wie ,,reichhaltig`` die Möglichkeiten des Preprozessings für CSPs durch Konsistenztechniken sind. Zum Teil setzen die genannten Verfahren spezielle CSPs bzw. spezielle Strukturen voraus. Wie bereits erwähnt werden in der Praxis trotz der vielen Varianten häufig generelle und einfach zu implementierende Techniken, wie die Kantenkonsistenz, eingesetzt, die unabhängig von der Struktur eines Problems mit geringer Komplexität bereits sehr viele Inkonsistenzen entdecken und herausfiltern können. Von besonderem Interesse sind daher Verfahren, die stärker als Kantenkonsistenz sind, dabei aber im Gegensatz zur Pfadkonsistenz das Constraint-Netz nicht verändern (z.B. restricted path consistency und singleton consistency) und mit einem vertretbaren Aufwand anwendbar sind.5.38 Eine Übersicht (siehe Abbildung 5.12) und formale Vergleiche bzgl. der Filterstärke von praxisrelevanten Konsistenztechniken sind den Arbeiten von Debruyne und Bessière (2001,1997b) und Prosser et al. (2000) zu entnehmen.
![]() |