next up previous contents index
Nächste Seite: 5.2.4 Suchverfahren Aufwärts: 5.2.3 Konsistenzverfahren Vorherige Seite: 5.2.3.5 k-Konsistenz   Inhalt   Index

5.2.3.6 Weitere Konsistenzverfahren

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:

(i,j)-consistency:

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 $k=2$ entspricht $(1,1)$-Konsistenz der Kantenkonsistenz und für $k=3$ entspricht $(2,1)$-Konsistenz der Pfadkonsistenz. Strenge $(i,j)$-Konsistenz ist gegeben, wenn ein Constraint-Netz $(k,j)$-konsistent ist, für alle $k \leq i$. Algorithmen, die $(i,j)$-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 $i \geq 2$. 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).

inverse consistency:

Da beim Erhöhen von i die effiziente Anwendbarkeit von $(i,j)$-Konsistenz stark nachlässt, wird bei der inversen Konsistenz $i=1$ 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. $(1,1)$-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.

lazy arc consistency (LAC):

Einen Sonderfall stellt die lazy arc consistency dar (vgl. Schiex et al., 1996): Im Gegensatz zur gewöhnlichen Kantenkonsistenz, die die Domänen $D = \{D_1,\ldots,D_n\}$ 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 $D' = \{D'_1,\ldots,D'_n\}$ 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$_7$ sowie die beiden Varianten LAC$^+_7$ und MinLAC$^++_7$ sind modifizierte Versionen des AC-7-Algorithmus.

directional arc consistency (DAC):

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 $(v_i,v_j)$ mit $i<j$ 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.

directional path consistency (DPC):

Ä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 $v_i<v_j<v_k$ 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.).

restricted path consistency (RPC):

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

singleton consistency:

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 consistency:

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.

Abbildung 5.12: Filterstärke unterschiedlicher Konsistenztechniken (vgl. Debruyne und Bessière, 2001, S. 217)
\begin{figure}\centering
\includegraphics[width=13cm]{images/constraints_filterstaerke}
\ifx\pdfoutput\undefined
\fi
\end{figure}



Fußnoten

...5.35
Anders als von Dechter und Pearl (1987, S. 13) hervorgehoben garantiert allerdings die zweimalige Anwendung des DAC-Algorithmus (Hin- und Rückrichtung) auf einem Constraint-Graphen, der einen Baum darstellt, nicht vollständige Kantenkonsistenz vgl. Tsang, 1993, S. 89 f.; Tsang, 1998, S. 356.
...5.36
Anstatt Pfadkonsistenz nur dann herzustellen, wenn es nur eine kompatible Wertekombination gibt, kann dies bereits durchgeführt werden, wenn k kompatible Wertekombinationen vorhanden sind.
...5.37
Wobei sich LAC in diesem Fall anbietet.
...5.38
Insbesondere für ein inkrementelles Vorgehen sind Konsistenzverfahren, die die Struktur des Constraint-Netzes modifizieren, weniger geeignet.

next up previous contents index
Nächste Seite: 5.2.4 Suchverfahren Aufwärts: 5.2.3 Konsistenzverfahren Vorherige Seite: 5.2.3.5 k-Konsistenz   Inhalt   Index