5.3.5.2 Höhere Konsistenzgrade

Da das Konzept von Lhomme ausschließlich die konvexen Intervallgrenzen berücksichtigt, ist 2B-Konsistenz grundsätzlich schwächer als Kantenkonsistenz. Wenn ein Constraint für eine Variable zu einem diskontinuierlichen Lösungsintervall führt, werden ausschließlich die obere und untere Grenze des Intervalls berücksichtigt, was lokale Inkonsistenzen innerhalb der Intervallgrenzen erlaubt. Nur für konvexe Constraints, die nicht zu diskontinuierlichen Ergebnisintervallen führen (engl. non-disjunctive Constraints), ist 2B-Konsistenz äquivalent zur Kantenkonsistenz. Höhere Konsistenzgrade lassen sich mittels 3B- und kB-Konsistenz erreichen. Ähnlich wie Kantenkonsistenz zur Pfadkonsistenz verallgemeinert wird, kann 3B-Konsistenz als eine Verallgemeinerung von 2B-Konsistenz gesehen werden. Entsprechend gilt dies für k-Konsistenz und kB-Konsistenz.

Zur Definition von 3B-Konsistenz ist die Einführung der folgenden Notation notwendig: Für jedes CSP gibt es einen Punkt $\Phi$, an dem der Filtervorgang abgeschlossen ist, wenn eine bestimmte Konsistenz $\lambda$ erreicht ist (engl. closure). Dieser konsistente Zustand $\Phi_\lambda$ ist für jede Konsistenzart und jedes CSP einzigartig. Der konsistente Zustand eines ICSP P für 2B-Konsistenz wird $\Phi_{2B}(P)$ genannt. Weiterhin wird die Vereinigung von einem ICSP $P = (V,I,C)$ und einem Constraint k (welches ausschließlich in P enthaltene Variablen beschränkt) definiert durch: $P'=P\cup\{K\}=(V,I,C\cup\{K\})$. Die Definition von 3B-Konsistenz nach Lhomme (1993, S. 237) lautet demnach folgendermaßen:

Definition 5.3.15   (3B-Konsistenz/3B-consistency)
Sei P ein ICSP, $v_i$, $i \in \{1,\dots,n\}$ eine Variable von P und $I_i=[a,b]$. $I_i$ ist 3B-konsistent, gdw. $P'$ und $P''$ beide nicht leer sind, wobei

$P'=\Phi_{2B}(P\cup\{v_i=a\})$ und $P''=\Phi_{2B}(P\cup\{v_i=b\})$.

Ein ICSP ist 3B-konsistent, gdw. alle Wertebereiche $I_i$ 3B-konsistent sind.

Verallgemeinert ausgedrückt wird 3B-Konsistenz erreicht, indem überprüft wird, ob 2B-Konsistenz für das gesamte ICSP hergestellt werden kann, wenn der Wertebereich einer Variable jeweils auf die untere und auf die obere Intervallgrenze gesetzt ist (vgl. Collavizza et al., 1999, S. 214).^5.104 Der Zustand von erreichter 3B-Konsistenz für das ICSP P wird $\Phi_{3B}(P)$ genannt.

Analog kann der Konsistenzbegriff auf die kB-Konsistenz verallgemeinert werden, um entsprechend höhere Grade lokaler Konsistenz bezogen auf die Intervallgrenzen zu erreichen (vgl. Lhomme, 1993, S. 238). Die Definition erfolgt rekursiv: So wie 3B-Konsistenz die 2B-Konsistenz nutzt, kann 3B-Konsistenz eingesetzt werden, um 4B-Konsistenz zu erreichen usw. vgl. Bordeaux et al., 2001, S. 305; Lebbah und Lhomme, 2002, S. 119.

Fußnoten

...^5.104

Ähnlich der singleton consistency (vgl. Abschnitt 5.2.3.6).