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.
Allgemein formuliert: Ein Pfad in einem Constraint-Graph ist pfadkonsistent, wenn sich für alle Wertepaare für , die das binäre Constraint erfüllen, Werte für die dazwischenliegenden Variablen finden lassen, so dass die entsprechenden Constraints entlang des Pfades erfüllt sind (siehe Abbildung 5.8). Formal kann dies wie folgt ausgedrückt werden (vgl. Mackworth, 1977a, S. 103):
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 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.):
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 , welches die Ungleichheit
von spezifiziert, wobei die beiden identischen Domänen
und
jeweils nur zwei Werte enthalten,
wird z.B. durch die folgende Matrix repräsentiert:
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 dargestellt, wobei dazu auf der
Diagonalen der Matrix jeweils der Wert 1 eingetragen wird. Der
Wertebereich
einer Variable wird demnach
z.B. durch die folgende Matrix repräsentiert:
Wobei die -te Zeile, die -te Spalte und die
Kardinalität von bezeichnet. Ein Beispiel für eine derartige
Operation:
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 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).