5.2.3.4 Pfadkonsistenz

Da Kantenkonsistenz nicht alle inkonsistenten Werte aus den Domänen der Constraint-Variablen ausschließt, und zudem nicht sichergestellt ist, dass ein kantenkonsistentes Constraint-Netz eine Lösung besitzt, wurden höhere Konsistenzgrade und Verfahren zu deren Herstellung entwickelt. Die natürliche Erweiterung der Kantenkonsistenz ist die Pfadkonsistenz. Zur Herstellung der Pfadkonsistenz werden Pfade im Constraint-Graphen betrachtet, wobei ein Pfad eine Sequenz von Constraint-Variablen bzw. Knoten im Constraint-Netz ist.^5.23 Dabei werden wie bei der Kantenkonsistenz Wertebelegungen eliminiert, die im Widerspruch zu den durch die Constraints formulierten Forderungen stehen.

Beispiel 5.2.2   Bezogen auf das PC-Beispiel aus Kapitel 3 sind in Abbildung 5.7 die (symbolischen) Abhängigkeiten des Sockel-Typs der CPU auf andere Komponenten dargestellt. Neben dem Constraint zwischen GEHAEUSE_SOCKEL_TYP und KUEHLER_SOCKEL_TYP besteht eine indirekte Abhängigkeit zwischen diesen Variablen entlang des Pfades über MAINBOARD_SOCKEL_TYP und PROZESSOR_SOCKEL_TYP. Eine Wertekombination für GEHAEUSE_SOCKEL_TYP und KUEHLER_SOCKEL_TYP ist nur dann zulässig, wenn sie ebenfalls für alle Pfade zwischen diesen beiden Variablen zulässig ist, d.h. alle unären und binären Constraints erfüllt sind.

Abbildung 5.7: Pfade im Constraint-Netz

Allgemein formuliert: Ein Pfad $P=(v_1,\ldots,v_i,\ldots,v_m)$ in einem Constraint-Graph ist pfadkonsistent, wenn sich für alle Wertepaare für $(v_1,v_m)$, die das binäre Constraint $C_{1,m}$ erfüllen, Werte für die dazwischenliegenden Variablen $v_i$ finden lassen, so dass die entsprechenden Constraints $C_{1,2},\ldots,C_{i,i+1},\ldots,C_{m-1,m}$ entlang des Pfades erfüllt sind (siehe Abbildung 5.8). Formal kann dies wie folgt ausgedrückt werden (vgl. Mackworth, 1977a, S. 103):

Definition 5.2.9   (Pfadkonsistenz/path consistency, PC)
Gegeben sei ein binäres CSP auf den Variablen $v_1,\ldots,v_n$ mit den Wertebereichen $D_1,\ldots,D_n$. Sei $C_1^u,\ldots,C_n^u$ die Menge der unären Constraints im Constraint-Netz, wobei $C_i^u$, $i \in \{1,\ldots,n\}$, die Relation $R_i^u$ besitzt und die Variable $v_i$ einschränkt. Weiterhin sei $C_{1,1}^b,\ldots,C_{n,n}^b$ die Menge der binären Constraints im Constraint-Netz, wobei $C_{i,j}^b$, $i,j \in \{1,\ldots,n\}$ und $i \neq j$, die Relation $R_{i,j}^b$ besitzt und die Variablen $v_i$ und $v_j$ einschränkt. Ein Pfad der Länge $m$ mit $m \leq n$ durch die Knoten $v_1,v_2,\ldots,v_{m-1},v_m$ ist pfadkonsistent, gdw. es für Werte $d_1 \in D_1$ und $d_m \in D_m$, mit $D_1 \subseteq R_1^u,$ und $D_m \subseteq R_m^u$ und $(d_1,d_m) \in R_{1,m}^b$, eine Sequenz von Werten $d_2 \in D_2,\ldots,d_{m-1} \in D_{m-1}$ gibt, so dass $D_2 \subseteq R_2^u,\ldots,D_{m-1} \subseteq R_{m-1}^u$ und $(d_1,d_2) \in R_{1,2}^b,\ldots,(d_{m-1},d_m) \in R_{m-1,m}^b$.

Ein Constraint-Netz ist pfadkonsistent, wenn alle Pfade im Constraint-Graph pfadkonsistent sind. Zu beachten ist, dass die Definition von Pfadkonsistenz für einen Pfad $(v_1,\ldots,v_i,\ldots,v_m)$ nicht bedingt, dass konsistente Wertebelegungen für diese Variablen konsistent sind mit Constraints, die nicht Teil dieses Pfades sind. Es wird also wiederum lediglich eine lokale Konsistenz erreicht.

In (Montanari, 1974) weist Ugo Montanari nach, dass Pfadkonsistenz für vollständige Constraint-Graphen erreicht werden kann, indem sichergestellt wird, dass alle Pfade der Länge zwei pfadkonsistent sind (vgl. Mackworth, 1977a, S. 111). Es reicht daher aus, innerhalb eines vollständigen Constraint-Netzes die Konsistenz für Wertetripel, d.h. für alle Pfade der Länge zwei, sicherzustellen, damit das gesamte CSP pfadkonsistent ist.^5.24 Verkürzt lässt sich daher Pfadkonsistenz auch wie folgt definieren (vgl. Mackworth, 1977a, S. 100 f.):

$$\begin{eqnarray*} \forall v_i,v_j & : & D_i \subseteq R_i^u \wedge D_j \subseteq... ...^u \wedge (d_i,d_k) \in R_{i,k}^b \wedge (d_k,d_j) \in R_{k,j}^b \end{eqnarray*}$$

Infolgedessen arbeiten Algorithmen zur Herstellung von Pfadkonsistenz ausschließlich mit Wertetripeln, d.h. Pfaden der Länge zwei. Sie sind generell als eine Verallgemeinerung der Kantenkonsistenz-Algorithmen anzusehen. Ähnlich wie diese stellen sie Konsistenz her, indem wiederholt Einschränkungen der Wertebereiche der Constraint-Variablen vorgenommen werden. Außerdem nehmen die Algorithmen eine Umformung des vorhandenen Constraint-Netzes vor, indem abgeleitete Constraints, die restriktiver sind und mehr Werte ausschließen als die ursprünglichen Constraints, eingefügt werden bzw. bestehende Constraints überschreiben, bis ein vollständiges, pfadkonsistentes Constraint-Netz vorliegt. Das bestehende Constraint-Netz wird dadurch in ein äquivalentes, pfadkonsistentes Constraint-Netz mit vollständiger Vernetzung überführt.

Abbildung 5.8: Pfadkonsistenz

Zur Repräsentation der Abhängigkeiten nutzen Pfadkonsistenz-Algorithmen eine extensionale Darstellung in Form von booleschen Matrizen. Voraussetzung hierfür ist, dass für die Wertebereiche der Constraint-Variablen eine fixe Reihenfolge angenommen wird. Binäre Constraints lassen sich mittels Matrizen darstellen, indem jeder Eintrag einer Matrix für eine konsistente oder inkonsistente Wertekombination der beiden beteiligten Variablen steht. Ein Constraint $C_{i,j}$, welches die Ungleichheit von $v_i \neq v_j$ spezifiziert, wobei die beiden identischen Domänen $D_i = \{1,2\}$ und $D_j = \{1,2\}$ jeweils nur zwei Werte enthalten, wird z.B. durch die folgende Matrix repräsentiert:

$$C_{i,j} = \left[ \begin{array}{c c} 0 & 1 \\ 1 & 0 \\ \e... ...1 & 2 \\ \hline 1 & 0 & 1 \\ 2 & 1 & 0 \\ \end{array}\right]$$

Die Zeilen stehen jeweils für Werte von $v_i$, die Spalten entsprechend für Werte von $v_j$. Als Ergebnis steht oben links und unten rechts in der Matrix eine 0, da hier jeweils die beiden ersten bzw. zweiten Werte aus den beiden identischen Domänen $D_i$ und $D_j$ mit $1 \neq 1$ bzw. $2 \neq 2$ eine nach $C_{i,j}$ ungültige Kombination bilden. Entsprechend stellen der erste Wert aus $D_i$ und der der zweite Wert aus $D_j$ oben rechts bzw. der zweite Wert aus $D_i$ und der erste Wert aus $D_j$ unten links mit $1 \neq 2$ und $2 \neq 2$ eine gültige Kombination dar, welches mit einer 1 in der Matrix gekennzeichnet wird.

Aus Gründen der Einheitlichkeit und Vereinfachung werden die Domäne einer Variablen und unäre Constraints in dieser Repräsentation als binäres Constraint $C_{i,i}$ dargestellt, wobei dazu auf der Diagonalen der Matrix jeweils der Wert 1 eingetragen wird. Der Wertebereich $D_i = \{3,4,5\}$ einer Variable $v_i$ wird demnach z.B. durch die folgende Matrix repräsentiert:

$$C_{i,i} = \left[ \begin{array}{c c c} 1 & 0 & 0 \\ 0 & 1 ... ...& 0 \\ 4 & 0 & 1 & 0 \\ 5 & 0 & 0 & 1 \\ \end{array}\right]$$

Ein unäres Constraint $C_{i,i}$, welches den Wert 5 für die obige Variable $v_i$ ausschließt, würde durch die folgende Matrix spezifiziert werden:

$$C_{i,i} = \left[ \begin{array}{c c c} 1 & 0 & 0 \\ 0 & 1 ... ...& 0 \\ 4 & 0 & 1 & 0 \\ 5 & 0 & 0 & 0 \\ \end{array}\right]$$

Die Arbeitsweise von Pfadkonsistenz-Algorithmen stützt sich auf die folgende Beobachtung: Angenommen das Constraint $C_{1,2}$ beschränkt die Variablen $v_1$ und $v_2$ und das Constraint $C_{2,3}$ die Variablen $v_2$ und $v_3$. Es lässt sich nun ein Constraint

$$C_{1,3} = C_{1,2} \cdot C_{2,3}$$

ableiten (engl. composite relation), welches sich durch die binäre Multiplikation der beiden Matrizen $C_{1,2}$ und $C_{2,3}$ ergibt.^5.25 Dieser Mechanismus wird engl. composition genannt und ist wie folgt definiert (vgl. Tsang, 1993, S. 91):

$$\begin{eqnarray*} C_{i,j} & = & C_{i,k} \cdot C_{k,j}, \hspace{0.2cm} gdw.\ \\ ... ...e C_{k,j,2,s}) \vee \ldots \vee (C_{i,k,r,t} \wedge C_{k,j,t,s}) \end{eqnarray*}$$

Wobei $r$ die $r$-te Zeile, $s$ die $s$-te Spalte und $t$ die Kardinalität von $D_y$ bezeichnet. Ein Beispiel für eine derartige Operation:

$$\left[ \begin{array}{c c c} 1 & 0 & 1 \\ 0 & 1 & 0 \\ 1... ...0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \\ \end{array}\right]$$

Ein Wertepaar $(a,c)$ der Variablen $v_1$ und $v_3$, ist mit $C_{1,3}$ nur dann konsistent, wenn es ebenfalls ein konsistentes Wertepaar $(a,b)$ für $v_1$ und $v_2$ mit $C_{1,2}$ und ein konsistentes Paar $(b,c)$ für $v_2$ und $v_3$ mit $C_{2,3}$ gibt. Dies lässt sich darauf verallgemeinern, dass die Werte, die $v_i$ und $v_j$ gleichzeitig als Teil einer Lösung annehmen können, außer durch das Constraint $C_{i,j}$ ebenfalls durch die Verknüpfung aller Constraints $C_{i,k} \cdot C_{k,k} \cdot C_{k,j}$ für alle $v_k \in V$ eingeschränkt werden (vgl. Tsang, 1993, S. 92):

$$C_{i,j} = C_{i,j} \wedge C_{i,k_1} \cdot C_{k_1,k_1} \cdot C... ...edge \ldots \wedge C_{i,k_n} \cdot C_{k_n,k_n} \cdot C_{k_n,j}$$

Wobei n die Anzahl der Variablen des CSP ist. Der einfachste, erste Pfadkonsistenz-Algorithmus PC-1 in Abbildung 5.9 macht sich dies zu Nutze, indem er für jede Variable $v_k$ mit $k \in \{1,\ldots,n\}$ des CSP jedes Constraint $C_{i,j}$ mittels composition reduziert:^5.26

Abbildung 5.9: Der Pfadkonsistenz-Algorithmus PC-1 (vgl. Mackworth, 1977a, S. 111)

$$Y_{i,j}^k \leftarrow Y_{i,j}^{k-1}\hspace{0.1cm}\&\hspace{0.1cm}Y_{i,k}^{k-1} \cdot Y_{k,k}^{k-1} \cdot Y_{k,j}^{k-1}$$

$Y^k$ steht dabei jeweils für eine aktuelle Menge von Constraints.^5.27 $Y_{i,j}^k$ benennt das Constraint $C_{i,j}$ aus der Menge $Y^k$. $Y^k$ wird jeweils dazu genutzt, den Nachfolger $Y^{k+1}$ zu erstellen. Der Durchlauf durch alle Schleifen des Algorithmus wird ähnlich wie bei AC-1 so oft wiederholt, bis keine Änderung an einem Constraint mehr vorgenommen wird ($Y^n = Y^0$). Der Algorithmus iteriert für alle Variablen $v_k$ durch alle Constraints $C_{i,j}$, welche durch Nutzung des composition-Operators aus $C_{i,k}$, $C_{k,k}$ und $C_{k,j}$ neu berechnet werden. Die $\&$-Operation kennzeichnet die logische UND-Verknüpfung zweier Matrizen und stellt sicher, dass die Restriktionen eines bestehenden Constraints $C_{i,j}$ berücksichtigt werden (engl. intersection).^5.28

Wie AC-1 ist der Algorithmus PC-1 sehr ineffizient, da für jede Änderung an nur einem einzigen Constraint der Algorithmus komplett erneut durchlaufen werden muss. Aufgrund der vielen Variablen $Y^k$ ist PC-1 zudem sehr speicherintensiv. Der Algorithmus PC-2 (vgl. Mackworth, 1977a, S. 113) ist ähnlich wie AC-3 eine Verbesserung in der Hinsicht, dass bei Änderungen nur noch die betroffenen Constraints erneut geprüft werden müssen.

Neben PC-1 und PC-2 gibt es noch eine Reihe weiterer, bekannter Pfadkonsistenz-Algorithmen. Sie sind jeweils Verallgemeinerungen der entsprechenden Algorithmen zur Herstellung von Kantenkonsistenz. So ist der Algorithmus PC-3 eine Verbesserung von PC-2, der seine erhöhte Effizienz mit ähnlichen Mechanismen und denselben Nachteilen bzgl. erhöhtem Speicherbedarf zur Verwaltung von zusätzlichen Informationen erreicht, wie AC-4 gegenüber AC-3. PC-3 wird zusammen mit AC-4 von Mohr und Henderson (1986) vorgestellt. Aufgrund kleinerer Fehler in PC-3 präsentierten Ching-Chih Han und Chia-Hoang Lee eine korrigierte Version namens PC-4 (vgl. Han und Lee, 1988).^5.29 Die Algorithmen PC-5 und PC-5++ von Moninder Singh sind weitere Verbesserungen, basierend auf AC-6 bzw. AC-6++ (vgl. Singh, 1995). Hauptvorteil ist die geringere Platzkomplexität der Algorithmen, wobei die worst-case Zeitkomplexität gleich der von PC-4 ist. Das durchschnittliche Laufzeitverhalten ist jedoch deutlich verbessert.

Unabhängig von PC-5 wurde der Algorithmus PC-6 entwickelt, der ebenfalls das Prinzip des minimal support von AC-6 auf die Pfadkonsistenz überträgt (vgl. Chmeiss und Jégou, 1995; Chmeiss, 1996)^5.30. Die Algorithmen bzw. deren Eigenschaften sind demnach identisch. Die Algorithmen PC-7 (vgl. Chmeiss und Jégou, 1996a) und PC-8 (vgl. Chmeiss und Jégou, 1998,1996b) von Assef Chmeiss und Philippe Jégou basieren ebenfalls wie PC-5 bzw. PC-6 darauf, nicht benötigte Konsistenzberechnungen durch minimal support zu vermeiden, allerdings ohne diese supports in einer aufwendigen Datenstruktur zu speichern. Der Algorithmus PC-8 ist dabei als eine Optimierung von PC-7 hinsichtlich der Platzkomplexität zu sehen. Einer Verbesserung des Speicherbedarfs steht bei beiden Algorithmen eine leichte Verschlechterung des Laufzeitverhaltens gegenüber. Eine Übersicht über die jeweiligen worst-case Zeit- und Platzkomplexitäten der hier angesprochenen Algorithmen befindet sich in der Tabelle 5.1.

Obwohl die Pfadkonsistenz einen höheren Konsistenzgrad darstellt als die Kantenkonsistenz und ggf. wesentlich mehr Werte aus den Wertebereichen der Variablen eines CSP entfernt, die nicht Teil einer Lösung sein können, werden die entsprechenden Algorithmen zum Herstellen von Pfadkonsistenz, außer bei speziellen Problemstellungen, relativ selten eingesetzt. Dies liegt darin begründet, dass Pfadkonsistenz mehrere Probleme mit sich bringt (vgl. Barták, 2001, S. 10): So filtern Pfadkonsistenz-Algorithmen zwar mehr inkonsistente Werte aus den Wertebereichen heraus, allerdings wird dafür im Vergleich zur Kantenkonsistenz ein wesentlich schlechteres Verhältnis in Bezug zur Ausführungsgeschwindigkeit bzw. Zeitkomplexität in Kauf genommen. Weiterhin ist der Speicherbedarf von Pfadkonsistenz-Algorithmen durch die extensionale Repräsentation aller Constraints bzw. Domänen auch für überschaubare Problemstellungen wesentlicher höher als bei Verfahren zur Herstellung von Kantenkonsistenz. Zudem werden bei der Herstellung von Pfadkonsistenz abgeleitete Constraints zu dem Constraint-Netz hinzugefügt. Suchverfahren zur Bestimmung von Lösungen, die bestimmte, vormals vorhandene Strukturen eines Constraint-Netzes ausnutzen, lassen sich dadurch nicht mehr anwenden. Und letztendlich stellt Pfadkonsistenz i.A. immer noch lediglich lokale Konsistenz her, d.h. es werden nicht alle inkonsistenten Werte aus den Domänen entfernt.

Eine besondere Rolle bzgl. Pfadkonsistenz spielen allerdings sog. row-convex-Constraints. Ein binäres Constraint in Matrixrepräsentation ist row-convex, wenn in jeder Zeile der Matrix die 1er Einträge aufeinander folgend sind und nicht durch eine 0 in derselben Zeile unterbrochen werden. Für diese Art Constraints wird von van Beek (1992) nachgewiesen, dass Pfadkonsistenz gleichbedeutend mit globaler Konsistenz ist. Die Konvexitätseigenschaften haben eine besondere Relevanz z.B. für Zeitplanungsprobleme formalisiert durch TCSPs (vgl. Abschnitt 4.4.1) und bei Verfahren zum Auffinden von Lösungen in ICSPs (vgl. Abschnitt 5.3.1.4 und Abschnitt 5.3.7).

Fußnoten

...^5.23

Ein Knoten kann dabei durchaus mehr als einmal in einem Pfad vorkommen, auch unmittelbar hintereinander (vgl. Montanari, 1974, S. 109).

...^5.24

Auch wenn man eigentlich von einem pfadkonsistenten Constraint-Netz nur sprechen sollte, wenn es sich um ein vollständiges Netz handelt, wird in der Literatur Pfadkonsistenz häufig mit (strenger) 3-Konsistenz (vgl. Abschnitt 5.2.3.5) gleichgesetzt.

...^5.25

Die Multiplikation entspricht dabei dem logischen UND, die Addition dem logischen OR (vgl. Schöning, 2000).

...^5.26

Der Algorithmus PC-1 wurde ursprünglich von Montanari (1974, S. 113) mit ,,Algorithm C`` benannt (,,C`` steht in diesem Fall für engl. closure, womit i.A. das Erreichen eines bestimmten Konsistenzgrades gemeint ist).

...^5.27

C ist die Menge aller Constraints des CSP (vgl. Definition 5.2.1).

...^5.28

Das Ergebnis ist die Schnittmenge der beiden Matrizen, wobei die composition-Operation vorrangig vor der UND-Verknüpfung ist und eine höhere Bindungsstärke aufweist. Die logische UND-Verknüpfung zweier Matrizen garantiert, dass sich in der Ergebnismatrix nur konsistente Wertekombinationen befinden, die in beiden Constraints bzw. Matrizen erlaubt sind.

...^5.29

PC-3 ist inkorrekt und entfernt u.U. konsistente Werte aus den Domänen der Constraint-Variablen.

...^5.30

Zit. nach Chmeiss und Jégou (1996a, S. 196); Chmeiss und Jégou (1996b, S. 286); Chmeiss und Jégou (1998, S. 122).