Mise en uvre

On considère tous les sous-problèmes triangulaires de notre instance fermée et on peut définir le sous-problème $T_{ijk}$ en ajoutant des contraintes redondantes, mettant en jeu le centre de gravité du triangle. On peut le faire uniquement si l'instance est fermée et donc que les distances vérifient les inégalités triangulaires. Voici comment on construit l'instance de $T_{ijk}$ :

• $\mathcal{X}= \{ x_i, y_i, x_j, y_j, x_k, y_k, x_G, y_G \}$
• $\mathcal{D}= \{ D_{x_i}, D_{y_i}, D_{x_j}, D_{y_j}, D_{x_k}, D_{y_k}, D_{x_G}, D_{y_G} \}$ tels que $D_{x_G} = \frac{1}{3}( D_{x_i}+D_{x_j}+D_{x_k} )$ et $D_{y_G} = \frac{1}{3}( D_{y_i}+D_{y_j}+D_{y_k} )$.
• $\mathcal{C}= \left\{ \begin{tabular}{rcl} $(x_i-x_j)^2 + (y_i-y_j)^2$ & = & $... ..._k )$\\ $y_G$ & = & $\frac{1}{3}( y_i + y_j + y_k )$\\ \end{tabular}\right.$

Cet exemple, dérivé de l'exemple 2.2, illustre l'amélioration du filtrage que l'on peut faire en ajoutant ces contraintes redondantes.

Exemple 4.1   Soient 3 points $A(x_A,y_A)$, $B(x_B,y_B)$ et $C(x_C,y_C)$ tels que :

$AB=BC=8$ et $AC=16$
$D_{x_A}=[0,4]$, $D_{x_B}=[8,12]$ et $D_{x_C}=[16,20]$. $D_{y_A}=[0,4]$, $D_{y_B}=[8,12]$ et $D_{y_C}=[0,4]$.

Nos inconnues sont donc $x_A$, $x_B$ et $x_C$ et les contraintes :
$C_1$ : $(x_A-x_B)^2+(y_A-y_B)^2=8^2$
$C_2$ : $(x_B-x_C)^2+(y_B-y_C)^2=8^2$
$C_3$ : $(x_A-x_C)^2+(y_A-y_C)^2=16^2$
On remarque que $AB+BC=AC$, ce qui veut dire que les 3 points sont alignés. Ce système n'a pas de solutions puisqu'on ne peut pas aligner les 3 points s'il sont instanciés dans leurs domaines.
Ici le $\mathcal{CSP}$ est 2B-consistant car les domaines vérifient localement toutes les contraintes, pourtant le système n'a pas de solutions.
Voici l'instance $T_{ABC}$ correspondante, on a :

• $\mathcal{X} = \{ x_A, y_A, x_B, y_B, x_C, y_C, x_G, y_G \}$.
• $\mathcal{D} = \{ D_{x_A}, D_{y_A}, D_{x_B}, D_{y_B}, D_{x_C}, D_{y_C}, D_{x_G}, D_{y_G} \}$, avec :
  
  • $D_{x_G} = \frac{1}{3}( D_{x_A} + D_{x_B} + D_{x_C} ) = \frac{1}{3}( [0,4]+[8,12]+[16,20]) = [8,12]$
  • $D_{y_G} = \frac{1}{3}( D_{y_A} + D_{y_B} + D_{y_C} ) = \frac{1}{3}( [0,4]+[8,12]+[0,4]) = [2.7,6.7]$
• Grâce aux formules de la propriété 4.1, on calcule les distances $GA$, $GB$ et $GC$ :
  $GA=\sqrt{ \frac{1}{9} \left( 2AB^2 + 2AC^2 - BC^2 \right)} = \sqrt{ \frac{1}{9} \left( 2 \times 8^2 + 2 \times 16^2 - 8^2 \right)} = 8$
  $GB=\sqrt{ \frac{1}{9} \left( 2AB^2 + 2BC^2 - AC^2 \right)} = \sqrt{ \frac{1}{9} \left( 2 \times 8^2 + 2 \times 8^2 - 16^2 \right)} = 0$
  $GC=\sqrt{ \frac{1}{9} \left( 2AC^2 + 2BC^2 - AB^2 \right)} = \sqrt{ \frac{1}{9} \left( 2 \times 16^2 + 2 \times 8^2 - 8^2 \right)} = 8$
  On ajoute aux contraintes ci-dessus, les contraintes suivantes :
  $C_4$ : $(x_G-x_A)^2+(y_G-y_A)^2=8^2$
  $C_5$ : $(x_G-x_B)^2+(y_G-y_B)^2=0$
  $C_6$ : $(x_G-x_C)^2+(y_G-y_C)^2=8^2$
  

Lorsqu'on veut résoudre cette instance par la 2B, on a la réponse immédiatement puisque la contrainte $C_5$ est violée. En effet, elle signifie que les points $B$ et $G$ sont confondus, or leurs domaines en $y$ ont une intersection vide.

On peut donc remplacer la procedure FILTER-DOMAINS par une méthode qui calcule les données de l'instance $T_{ijk}$, puis la résout par 3B, avec effets de bord sur l'instance du problème initial. On appelle cette procédure Floyd-3B :

procedure Floyd-3B( $\mathcal{I}=(\mathcal{P},\:\mathcal{D},\:\Delta)$ )
pour k $\rightarrow$ 1 à $n$ faire
pour j $\rightarrow$ 1 à $n$ faire
pour i $\rightarrow$ 1 à $n$ faire
si $u_{ij} > u_{ik} + u_{jk}$ alors $u_{ij} = u_{ik} + u_{jk}$
si $l_{ij} < l_{ik} - u_{jk}$ alors $l_{ij} = l_{ik} - u_{jk}$
sinon si $l_{ij} < l_{jk} - u_{ik}$ alors $l_{ij} = l_{jk} - u_{ik}$
si $l_{ij} > u_{ij}$ alors Erreur
3B($T_{ijk}$)
finpour
finpour
finpour
retourner $\mathcal{I}$