La 3B-consistance

Si la 2B garantit que l'instanciation d'une variable dans son domaine vérifie localement toutes les contraintes, la 3B le garantit pour l'instanciation de 2 variables. Ce principe se généralise à la $k$B-consisitance, pour l'instanciation de $k-1$ variables. Plus $k$ est proche du nombre de variables et plus on se rapproche de la consistance globale. Cependant ces méthodes, pour $k \geq 4$ sont très peu utilisées car elles sont gourmandes en temps de calcul. La 3B-consistance pallie au problème de la décomposition des points lorsqu'on travaille en dimension 2. En effet, cela signifie que l'instanciation d'un couple de coordonnées quelconques vérifie localement toutes les contraintes, donc y compris l'instanciation de deux coordonnées d'un même point. En dimension 3, il faudrait utiliser la 4B-consistance pour assurer cette propriété.

Définition 2.5 (3B-consistance d'un domaine)   Soit $P=(\mathcal{X,D,C})$ un $\mathcal{CSP}$ et $x$ une variable de $\mathcal{X}$ dont le domaine est $D_x=[a,b]$. Soient $Dinf_x =[a,a^+)$ et $Dsup_x =(b^-,b]$ et soient les sous-problèmes suivants :

• $P_{Dinf_x}$ le $\mathcal{CSP}$ dérivé de $P$ en substituant $D_x$ dans $\mathcal{D}$ par ${Dinf_x}$.
• $P_{Dsup_x}$ le $\mathcal{CSP}$ dérivé de $P$ en substituant $D_x$ dans $\mathcal{D}$ par ${Dsup_x}$.

On dit que $D_x$ est 3B-consistant ssi $\Phi_{2B}(P_{Dinf_x}) \neq \varnothing$ et $\Phi_{2B}(P_{Dsup_x}) \neq \varnothing$.

Définition 2.6 (3B-consistance d'un $\mathcal{CSP}$)   Un $\mathcal{CSP}$ est 3B-consistant ssi tous ses domaines sont 3B-consistants.

Le principe de la 3B est de vérifier si une borne d'un domaine vérifie localement chque contrainte du $\mathcal{CSP}$. De manière plus concrète, la 3B applique la 2B sur des sous-problèmes dans lesquels une variable est instanciée par l'une des bornes de son domaine. L'idée est de réfuter par dichotomie les bornes des domaines des variables. Ainsi, si $x_i$ est une variable d'un $\mathcal{CSP}$ $P$ et $D_{x_i}=[a,b]$ est son domaine, la 3B va commencer par chercher la borne inférieure de $D_{x_i}$ dans l'intervalle $[a,b]$ :

• Si le $\mathcal{CSP}$ équivalent à $P$ dans lequel on a remplacé toutes les occurrences de $x_i$ par $\frac{a+b}{2}$ est 2B-consistant alors la borne inférieure est dans l'intervalle $[a,\frac{a+b}{2})$.
• Si le $\mathcal{CSP}$ équivalent à $P$ dans lequel on a remplacé toutes les occurrences de $x_i$ par $\frac{a+b}{2}$ n'est pas 2B-consistant alors la borne inférieure est dans l'intervalle $(\frac{a+b}{2},b]$.
• Enfin si $b-a \leq \omega$ alors la borne inférieure est $a$.

Ensuite elle fait de même symétriquement pour la borne supérieure :

• Si le $\mathcal{CSP}$ équivalent à $P$ dans lequel on a remplacé toutes les occurrences de $x_i$ par $\frac{a+b}{2}$ est 2B-consistant alors la borne supérieure est dans l'intervalle $(\frac{a+b}{2},b]$.
• Si le $\mathcal{CSP}$ équivalent à $P$ dans lequel on a remplacé toutes les occurrences de $x_i$ par $\frac{a+b}{2}$ n'est pas 2B-consistant alors la borne supérieure est dans l'intervalle $[a,\frac{a+b}{2})$.
• Enfin si $b-a \leq \omega$ alors la borne supérieure est $b$.

Les divisions par 2 posent des problèmes d'approximations. Pour garantir qu'aucune solution réelle n'est perdue en cours de route, il faut arrondir à l'entier supérieur pour les bornes supérieures et à l'entier inférieur pour les bornes inférieures, et ce à chaque division par 2. $\omega$ est un paramètre de l'algorithme qui permet d'approcher les bornes des domaines des variables avec une précision donnée. La 3B-consistance est donc une méthode basée sur la 2B-consistance, permettant d'avoir une consistance locale plus forte que la 2B, mais qui hérite de ses difficultés, notemment en ce qui concerne la propagation de l'erreur et la convergence asymptotique. La localité est donc réduite, mais néanmoins toujours présente, et enfin le problème de la décomposition des points n'est que partiellement réglé. Dans ce domaine, il serait intéressant de chercher une méthode de filtrage inspirée par la 3B, mais garantissant la consistance locale non plus pour tout couples de variables mais uniquement pour tout couples de coordonnées d'un même point. Ceci pourra faire l'objet d'études complémentaires.