Propagation de contraintes

Propagation de contraintes

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 de valeur possible 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.

Sommaire

Consistance par arcs

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

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

  • x \neq y (c1)
  • y \neq z (c2)
  • x \neq z (c2)


Pour chacune des valeurs du domaine de x il existe une valeur du domaine de y qui satisfait la contrainte c1, effet pour x = 1 (resp. 2), l'instanciation y = 2 (resp. 1) satisfait la contrainte c1, la contrainte c1 est donc arc consistant; de la même façon c2 et c3 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

  • 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

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é en O( n · m² ), et qu'il est optimal.

Utilisation de la sémantique de la contrainte

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 lorsque il devient certain que C1 ne sera pas satisfaite et réciproquement).

Consistance de nœud

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

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 impliquent 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

Elle consiste à considérer k variables, et de 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

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é ( X < Y ), la consistance de bornes est très proche, voire équivalente, à la consistance d'arc.

Notes et références



Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Propagation de contraintes de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Propagation — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Propagation », sur le Wiktionnaire (dictionnaire universel) Le mot propagation désigne l action de se… …   Wikipédia en Français

  • Programmation par contraintes — La programmation par contraintes (PPC, ou CP pour Constraint Programming en anglais) est un paradigme de programmation apparu dans les années 1980[1],[2] permettant de résoudre des problèmes combinatoires de grandes tailles tels que les problèmes …   Wikipédia en Français

  • Survol de la Programmation par Contraintes — Programmation par contraintes La programmation par contraintes (PPC, ou CP pour Constraint Programming en anglais) consiste à poser un problème sous forme de relations logiques (appelées contraintes) entre plusieurs variables. Un problème formulé …   Wikipédia en Français

  • Problème de satisfaction de contraintes — Les problèmes de satisfaction de contraintes ou CSP (Constraint Satisfaction Problem) sont des problèmes mathématiques où l on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Les CSP font l objet de… …   Wikipédia en Français

  • Programmation par contrainte — Programmation par contraintes La programmation par contraintes (PPC, ou CP pour Constraint Programming en anglais) consiste à poser un problème sous forme de relations logiques (appelées contraintes) entre plusieurs variables. Un problème formulé …   Wikipédia en Français

  • Classification sous contrainte — En intelligence artificielle, la classification sous contrainte désigne une famille d algorithmes d apprentissage semi supervisée. Cette dernière occupe une place intermédiaire entre l apprentissage supervisé (pour laquelle les étiquettes de… …   Wikipédia en Français

  • Moteur D'inférence — Un moteur d inférence (du verbe inférer = déduire) est un logiciel correspondant à un algorithme de simulation des raisonnements déductifs. Un moteur d inférence permet aux systèmes experts de conduire des raisonnements logiques et de dériver des …   Wikipédia en Français

  • Moteur d'inference — Moteur d inférence Un moteur d inférence (du verbe inférer = déduire) est un logiciel correspondant à un algorithme de simulation des raisonnements déductifs. Un moteur d inférence permet aux systèmes experts de conduire des raisonnements… …   Wikipédia en Français

  • Moteur d'inférence — Un moteur d inférence (du verbe « inférer » qui signifie « déduire ») est un logiciel correspondant à un algorithme de simulation des raisonnements déductifs. Un moteur d inférence permet aux systèmes experts de conduire des… …   Wikipédia en Français

  • Consistance — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Consistance », sur le Wiktionnaire (dictionnaire universel) La consistance caractérise le degré de… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”