Sam-Haroud und Faltings setzen die Anwendung von
totalen
Constraints voraus, d.h. sämtliche Relationen bzgl. einer Menge
von Variablen werden jeweils in einem einzigen Constraint
zusammengefasst (vgl. Definition 4.1.2).
In Bezug auf -Bäume gestaltet sich diese
Berechnung einfach, da lediglich die einzelnen
-Bäume erstellt und hiervon die Schnittmenge
gebildet werden muss (vgl. Sam-Haroud und Faltings, 1996a, S. 95). Der
resultierende Baum beschreibt den Lösungsraum des benötigten
totalen
Constraints. In Abbildung 5.27 ist
beispielhaft dargestellt, wie ein
-Baum
generiert wird:
![]() |
Die entstehenden -Bäume
repräsentieren jeweils die Relationen
. Auf ihnen können
Weiterentwicklungen des
Waltz-Filteralgorithmus zur
Herstellung von Kantenkonsistenz, Pfadkonsistenz, etc. angewendet
werden. In bestimmten Fällen, für konvexe,
binäre Constraints, führt Pfadkonsistenz innerhalb polynomialer
Laufzeitkomplexität gleichzeitig zu globaler
Konsistenz.5.111
Pfadkonsistenz wird durch die in
Abschnitt 5.2.3.4 f. beschriebenen
Operationen composition und intersection
erreicht. Sam-Haroud und Faltings (1996a, S. 98) stellen dies wie folgt
dar:
Ebenso kann bei Bedarf niedrigere Konsistenz hergestellt werden. Da Pfadkonsistenz eine Generalisierung der Kantenkonsistenz ist, kann analog Kantenkonsistenz folgendermaßen erreicht werden:
Während die intersection-Operation die
Überschneidung der Wertebereiche impliziert, was sich innerhalb der
-Baum-Repräsentation wiederum problemlos
durch Bildung der logischen Schnittmenge der betreffenden Bäume
durchführen lässt, muss zur Bestimmung der ,,Pfade`` im
Constraint-Netz durch die composition-Operation
eine komplexere Umwandlung vorgenommen werden. Anstatt die
composition, wie bei den klassischen
Pfadkonsistenz-Algorithmen, durch binäre Matrizen-Multiplikation zu
berechnen, werden in Bezug auf
-Bäume die
k-dimensionalen Constraints durch die Projektion
in den (k+1)-dimensionalen Raum und wieder zurück in die
k-te Dimension projiziert. Die Regeln dieser Projektionen
führen in diesem Fall zur Realisierung des
composition-Operators. Gegeben die Ordnung
sind die folgenden Regeln
anzuwenden (vgl. Sam-Haroud und Faltings, 1996a, S. 98):
In Abbildung 5.28 ist ein Würfel zu sehen, dessen 3-dimensionale Knoten aus deren 2-dimensionalen Facetten abgeleitet werden können. Umgedreht ist es möglich, Informationen über eine Facette zu erhalten, indem die 3-dimensionale Ausprägung über eine ihrer Facetten projiziert wird. Die Operatoren zur Herstellung von Kantenkonsistenz, Pfadkonsistenz und weiteren Generalisierungen benötigen somit ausschließlich logische anstatt numerische Operationen zu ihrer Durchführung vgl. Haroud und Faltings, 1994, S. 43; Sam-Haroud und Faltings, 1996a, S. 98.