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

Cohérence/consistance par arcs (arc consistency)[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 cohérence. Plusieurs types de cohérences, plus ou moins fortes peuvent être considérées.

La cohérence par arcs est définie ainsi :

  • Une contrainte binaire est cohérente par arcs (AC: arc consistent) si pour toute valeur du domaine de , il existe au moins une valeur du domaine de telle que la contrainte soit satisfaite, et vice-versa.
  • Une contrainte à plus de deux variables est AC si pour toute variable impliquée dans la contrainte, et pour toute valeur du domaine de , 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 cohérence par arcs généralisée (GAC).
  • Un problème est AC si toutes ses contraintes sont AC

Une définition plus mathématique :

Exemple[modifier | modifier le code]

Soit le CSP défini par les variables avec les contraintes suivantes:


Pour chacune des valeurs du domaine de , il existe une valeur du domaine de qui satisfait la contrainte . En effet, pour (resp. ), l'instanciation (resp. ) satisfait la contrainte . La contrainte est donc cohérente par arc. De la même façon et sont cohérentes par arcs.

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.

AC3[modifier | modifier le code]

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

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

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

  • Une contrainte est examinée au plus 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 valeurs du domaine).
  • Il y a donc au plus examens de contraintes
  • Chaque examen de contrainte nécessite vérifications.
  • L'algorithme a donc une complexité en .

AC2001[modifier | modifier le code]

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

On peut montrer que cet algorithme a une complexité temporelle en dans le pire des cas et une complexité spatiale en . Ça en fait l'algorithme le plus performant à 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 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 du domaine de uniquement lorsque le domaine de a été réduit au singleton .

Pour des contraintes de type , la propagation de contrainte efficace consiste à ne considérer que les bornes des domaines des variables : si la borne supérieure de a diminué, il faut diminuer celle de en conséquence. Mais si c'est la borne inférieure de 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 .

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)