Propagation de contraintes

Soit le CSP ${\displaystyle {\mathcal {P}}}$ défini par les variables ${\displaystyle x,y,z\in \{1,2\}}$ avec les contraintes suivantes :

• ${\displaystyle x\neq y}$ ${\displaystyle (c_{1})}$
• ${\displaystyle y\neq z}$ ${\displaystyle (c_{2})}$
• ${\displaystyle x\neq z}$ ${\displaystyle (c_{3})}$

Pour chacune des valeurs du domaine de ${\displaystyle x}$, il existe une valeur du domaine de ${\displaystyle y}$ qui satisfait la contrainte ${\displaystyle c_{1}}$. En effet, pour ${\displaystyle x=1}$ (resp. ${\displaystyle 2}$), l'instanciation ${\displaystyle y=2}$ (resp. ${\displaystyle 1}$) satisfait la contrainte ${\displaystyle c_{1}}$. La contrainte ${\displaystyle c_{1}}$ est donc cohérente par arc. De la même façon ${\displaystyle c_{2}}$ et ${\displaystyle c_{3}}$ sont cohérentes par arc.

On s'aperçoit ainsi qu'il ne suffit pas qu'un problème soit AC pour admettre une solution. Ce point est en fait fondamental : on peut montrer que les algorithmes de rétablissement de la cohérence par arcs (dans le cas des contraintes binaires) ont une complexité temporelle polynomiale, alors qu'en règle générale, les algorithmes de rétablissement de la cohérence complète ont une complexité temporelle exponentielle.

• Soit la contrainte ${\displaystyle C_{i,j}}$
• ${\displaystyle x}$ parcourant toutes les valeurs possibles de la première variable ${\displaystyle V_{i}}$
• ${\displaystyle y}$ parcourant toutes les valeurs possibles de la seconde variable ${\displaystyle V_{j}}$
• Si, pour un ${\displaystyle x}$ donné, ${\displaystyle (x,y)}$ viole ${\displaystyle C_{i,j}}$ pour toutes les valeurs ${\displaystyle y}$ de la variable ${\displaystyle V_{j}}$, alors enlever ${\displaystyle x}$ du domaine de la variable ${\displaystyle V_{i}}$.
• Si une valeur ${\displaystyle x}$ a été enlevée de ${\displaystyle V_{i}}$, répéter ces vérifications pour toutes les contraintes impliquant la variable ${\displaystyle V_{i}}$

Cet algorithme nécessite donc de gérer une pile comprenant les variables dont le domaine est modifié.

On peut montrer que si ${\displaystyle m}$ est la taille maxi des domaines des variables et ${\displaystyle n}$ le nombre de contraintes, alors :

• Une contrainte ${\displaystyle C_{i,j}}$ est examinée au plus ${\displaystyle m}$ fois (car une contrainte est examinée à cause de la suppression d'une valeur dans le domaine de sa première variable, et qu'on ne peut pas supprimer plus de ${\displaystyle m}$ valeurs du domaine).
• Il y a donc au plus ${\displaystyle m\times n}$ examens de contraintes
• Chaque examen de contrainte nécessite ${\displaystyle m^{2}}$ vérifications.
• L'algorithme a donc une complexité en ${\displaystyle O(nm^{3})}$.

Cet algorithme est une optimisation de AC3. Dans AC3, le fait de faire parcourir tout le domaine de ${\displaystyle V_{i}}$ par x est inefficace lors de l'examen d'une contrainte qui a déjà été examinée. Si dans une étape précédente, la vérification a déjà été faite pour une valeur x et qu'elle n'a pas trouvé de violation, il est intéressant de conserver cette information. Lors d'une vérification ultérieure, il faut commencer la vérification par la valeur suivante de ${\displaystyle V_{i}}$.

On peut montrer que cet algorithme a une complexité temporelle en ${\displaystyle O(nm^{2})}$ dans le pire des cas et une complexité spatiale en ${\displaystyle O(nm)}$. Ça en fait l'algorithme le plus performant à l'heure actuelle[1].

Les algorithmes AC3 ou AC2001 sont adaptés aux contraintes qui ne sont définies que par la donnée des valeurs violant la contrainte. Cependant dans la majorité des problèmes concrets à résoudre, les contraintes sont définies par une expression symbolique : on définit une contrainte de différence sur [1..3] × [1..2] par ${\displaystyle V_{1}\neq V_{2}}$ plutôt que par la donnée des couples interdits : (1,1) et (2,2) et des couples autorisés : (1,2) (1,3) (2,1) (3,1).

En pratique, les systèmes de résolution des problèmes de PPC offrent par défaut un algorithme de type AC3 ou AC2001 pour les contraintes définies par des ensembles de valeurs permises et interdites (contraintes tabulaires), et une bibliothèque de contraintes particulières fournies avec leur algorithme efficace de propagation. De tels systèmes offrent également le moyen de combiner des contraintes entre elles et de les propager efficacement (par exemple : Et(C1,C2) se propage en propageant à la fois C1 et C2 ; Ou(C1,C2) se propage en ne propageant C2 que lorsqu'il devient certain que C1 ne sera pas satisfaite et réciproquement).