Propagation de contraintes

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

La propagation de contraintes dans le domaine de la programmation par contraintes est le fait de réduire le domaine d'une contrainte afin de maintenir l'ensemble des valeurs possibles cohérent avec les contraintes du problème. La propagation de contraintes permet ainsi de résoudre un problème si la propagation permet d'établir la cohérence du problème. Les techniques de propagation de contraintes sont utilisées pour réduire la taille de l'espace de recherche lors de la résolution d'un problème de satisfaction de contraintes par un algorithme de recherche arborescente.

Consistance par arcs[modifier | modifier le code]

La propagation de contraintes consiste à modifier (i.e. réduire) le domaine des variables impliquées dans une contrainte, dans le but de rétablir la consistance. Plusieurs types de consistances, plus ou moins fortes peuvent être considérées.

La consistance par arcs est définie ainsi :

  • Une contrainte binaire C(x, y) est consistante par arcs (AC) si pour toute valeur du domaine de x, il existe au moins une valeur du domaine de y telle que la contrainte soit satisfaite, et vice-versa.
  • Une contrainte à plus de deux variables C(x, y, ..., t) est AC si pour toute variable v impliquée dans la contrainte, et pour toute valeur du domaine de v, il existe au moins une valeur dans le domaine de chaque autre variable impliquée telle que la contrainte soit satisfaite. On parle alors de consistance par arcs généralisée (GAC).
  • Un problème est AC si toutes ses contraintes sont AC

Une définition plus mathématique : AC(Ci, j) = ∀x ∃y ( x ∈ Di ∧ y ∈ Dj ∧ Ci, j(x, y) )

Exemple[modifier | modifier le code]

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

  • x \neq y (c_1)
  • y \neq z (c_2)
  • x \neq z (c_3)


Pour chacune des valeurs du domaine de x il existe une valeur du domaine de y qui satisfait la contrainte c_1, effet pour x=1 (resp. 2), l'instanciation y=2 (resp. 1) satisfait la contrainte c_1, la contrainte c_1 est donc arc consistant; de la même façon c_2 et c_3 sont arc consistant.

On s'aperçoit ainsi qu'un problème AC n'est pas totalement consistant, puisque ce problème n'admet pas de solution. Ce point est en fait fondamental : on peut montrer que les algorithmes de rétablissement de la consistance 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 consistance complète ont une complexité temporelle exponentielle.

AC3[modifier | modifier le code]

  • Soit la contrainte Ci, j
  • x parcourant toutes les valeurs possibles de la première variable Vi
  • y parcourant toutes les valeurs possibles de la seconde variable Vj
  • Si, pour un x donné, (x, y) viole Ci, j pour toutes les valeurs y de la variable Vj, alors enlever x du domaine de la variable Vi
  • Si une valeur x a été enlevée de Vi, répéter ces vérifications pour toutes les contraintes impliquant la variable Vi

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

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

  • Une contrainte Ci, j est examinée au plus 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 m valeurs du domaine).
  • Il y a donc au plus (m × n) examen de contraintes
  • Chaque examen de contrainte nécessite m² vérifications.
  • L'algorithme a donc une complexité en O( n · m³ )

AC2001[modifier | modifier le code]

Cet algorithme est une optimisation de AC3. Dans AC3, le fait de faire parcourir tout le domaine de Vi 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 Vi.

On peut montrer que cet algorithme a une complexité temporelle en O( n · m² ) dans le pire des cas et une complexité spatiale en O( n · m ), et que c'est l'algorithme le plus optimal à l'heure actuelle[1].

Utilisation de la sémantique de la contrainte[modifier | modifier le code]

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 V1 ≠ V2 plutôt que par la donnée des couples interdits : (1,1) et (2,2) et des couples autorisés : (1,2) (2,1) (3,1).

Exemples —  Pour une telle contrainte de différence, un algorithme extrêmement simple consiste à supprimer x du domaine de V2 uniquement lorsque le domaine de V1 a été réduit au singleton {x}.

Pour des contraintes de type V1 ≤ V2, la propagation de contrainte efficace consiste à ne considérer que les bornes des domaines des variables : si la borne supérieure de V2 a diminué, il faut diminuer celle de V1 en conséquence. Mais si c'est la borne inférieure de V2 qui a augmenté, alors il n'y a pas de propagation à faire, car la contrainte ne permet pas de déduire une nouvelle information sur V1.

Pour la contrainte d'égalité, la propagation consiste à conserver les domaines des deux variables totalement identiques.

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).

Consistance de nœud[modifier | modifier le code]

Elle consiste à ne considérer qu'une seule variable. On retire alors toutes les valeurs pour lesquelles au moins une contrainte est impossible à satisfaire. Ce filtrage est très rapide, mais peu efficace (étant donné qu'on ne considère aucune autre variable impliquée dans la contrainte).


Consistance d'hyperarc[modifier | modifier le code]

Aussi appelée Hyperarc Consistency (HAC), c'est une généralisation de la consistance d'arc pour les contraintes non binaires. Elle a aussi été appelée consistance d'arc généralisée. Le principe est le même que pour les contraintes binaires : une contrainte est HAC si et seulement si chaque valeur de chaque variable appartient à une solution de la contrainte. On établit la consistance d'hyperarc en supprimant toutes les valeurs qui ne satisfont pas cette propriété.

Par exemple, la contrainte Alldiff implique que les variables sur lesquelles elle est définie prennent des valeurs deux à deux différentes. On sait établir efficacement la consistance d'hyperarc pour cette contrainte.

k-consistance[modifier | modifier le code]

Elle consiste à considérer k variables, et à tester tous les k-uplets de valeurs possibles afin de tester s'ils ne violent pas les contraintes. Plus k est grand, plus le filtrage sera efficace. Cependant, du fait du grand nombre de combinaisons à tester, cela reste souvent trop lourd. La 3-consistance donne de bons résultats, cependant du fait de la complexité de son implémentation, elle n'est que très rarement présente dans des solveurs de contraintes.

La 2-consistance est en fait une autre vue de la consistance d'arc. Si un problème contient n variables, alors la n-consistance consisterait à tester l'ensemble des possibilités.

Consistance de bornes[modifier | modifier le code]

Lorsque les domaines des variables sont trop grands (plusieurs milliers d'éléments), le fait de stocker l'appartenance ou non de chaque valeur au domaine de la variable peut se révéler trop lourd à traiter. On utilise dans ce cas la consistance de bornes, qui consiste à simplement raisonner sur les valeurs minimum et maximum que les variables peuvent prendre. Pour certaines contraintes, comme par exemple celles d'inégalités ( X < Y ), la consistance de bornes est très proche, voire équivalente, à la consistance d'arc.

Notes et références[modifier | modifier le code]

  1. An Optimal Coarse-grained Arc Consistency Algorithm, Bessiere et als, 2005 (description de AC-2001/3.1)