5.3.5.1 Hull-Konsistenz

Die 2B- bzw. Hull-Konsistenz ist vergleichbar mit der lokalen Konsistenz, die beim Label Inference von Davis (1987) bzw. bei der lokalen Toleranzpropagation von Hyvönen (1992) bzgl. ununterbrochener Intervalle hergestellt wird. Lhomme (1993, S. 235) definiert 2B-Konsistenz folgendermaßen:

Definition 5.3.13   (2B-Konsistenz/arc B-consistency)
Sei P ein ICSP, $v_i$, $i \in \{1,\dots,n\}$ eine Variable von P, $I_i=[a,b]$ und $C_j$, $j \in \{1,\ldots,m\}$ ein Constraint in P. $I_i$ ist 2B-konsistent, gdw. $\forall C_j(v_i, v_1,\ldots,v_k)$ ein Constraint über $v_i$

$\exists v_1,\ldots,v_k \in I_1 \times \ldots \times I_k \mid C_j(a,v_1,\ldots,v_k)$ ist erfüllt,

$\exists v_1,\ldots,v_k \in I_1 \times \ldots \times I_k \mid C_j(b,v_1,\ldots,v_k)$ ist erfüllt.

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

Ein Constraint $C_j$ ist demnach 2B-konsistent, wenn es für jede Variable $v_i$ für alle anderen Variablen aus $C_j$ mögliche Belegungen gibt, die $C_j$ erfüllen, wenn $v_i$ jeweils mit seiner oberen und unteren Grenze belegt wird. Dies entspricht einer auf die Intervallgrenzen der Wertebereiche bezogenen Form von Kantenkonsistenz.

Um die Wertebereichseinschränkungen, eingebettet in eine Art Waltz-Filteralgorithmus, vornehmen zu können, müssen wiederum Funktionen für jede Variable eines Constraints abgeleitet werden. Lhomme (1993, S. 234) nennt dies ,,Projektion``:

Definition 5.3.14   (Projektion eines Constraints)
Seien $(v_1,\ldots,v_k)$ k Variablen, sei die Box $B^\Box = I_1 \times \cdots \times I_k$. Die Projektion über $v_i$ des Constraints $C_j(v_1,\ldots,v_k)$ bzgl. der Domänen $I_1,\ldots,I_k$, die mit $\Pi_i(C_j(v_1,\ldots,v_k),B)$ benannt wird, ist die Menge: { $x_i \in I_i \mid \exists (x_1,\ldots,x_{i-1},x_{i+1},\ldots,x_k) \in I_i \times \cdots \times I_{i-1} \times I_{i+1} \times \cdots \times I_k$, so dass $C_j(x_1,\ldots,x_k)$ erfüllt wird}.

Der Wertebereich einer Variablen $v_i$ wird demnach eingeschränkt durch die Berechnung einer Projektion $\Pi_i$ von einem Constraint $C_j$ über die Variable $v_i$ im Lösungsraum, der von den in $C_j$ vorkommenden Variablen außer $v_i$ aufgespannt wird. Diese Projektionen entsprechen den impliziten solution functions von Hyvönen (vgl. Abschnitt 5.3.4.1).^5.102 Sie liefern bzgl. einzelner Constraints konsistente Ergebnismengen für die jeweiligen Variablen. Um diese Berechnungen vornehmen zu können, nimmt Lhomme (1993) ebenso wie Hyvönen (1992) eine Zerlegung komplexer Ausdrücke in ternäre basic constraints vor.^5.103 Für diese basic constraints lassen sich Projektionen auf triviale Art und Weise erstellen.

Fußnoten

...^5.102

Von Lhomme et al. (1998,1996) auch narrowing functions genannt, von to narrow (engl.): eingrenzen, schmälern, verengen.

...^5.103

Bei Hyvönen ,,primitive`` Constraints genannt.