Propagation de contraintes
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

Dans les algorithmes de programmation par contraintes, la propagation de contraintes permet de réduire les domaines des variables, dans le but d'accélérer le parcours de l'arbre de recherche.

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 (En mathématiques et en logique, une variable est représentée par un symbole. Elle est utilisée pour marquer un rôle dans une formule, un prédicat ou un algorithme. ...) 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 (Une définition est un discours qui dit ce qu'est une chose ou ce que signifie un nom. D'où la division entre les définitions réelles et les définitions nominales.) plus mathématique : AC(Ci,j) = ∀x ∃y ( x ∈ Di ∧ y ∈ Dj ∧ Ci,j(x,y) )

Exemple

Le problème suivant :

  • x ∈ [1..2]
  • y ∈ [1..2]
  • z ∈ [1..2]
  • C1 : x ≠ y
  • C2 : y ≠ z
  • C3 : x ≠ z

Est AC, car chacune de ses contraintes C1, C2, ou C3 est AC. En effet, si x=1, alors y=2 et z=2 sont des valeurs qui respectent toutes les contraintes. De même si x=2, alors y=1 et z=1 respectent toutes les contraintes.

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 (Graphie) est en fait fondamental : on peut montrer que les algorithmes de rétablissement de la consistance par arcs (dans le cas des contraintes binaires) sont de complexité (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie...) polynomiale, alors qu'en règle générale, le rétablissement de la consistance complète est de complexité exponentielle (La fonction exponentielle est l'une des applications les plus importantes en analyse, ou plus généralement en mathématiques et dans ses domaines d'applications. Il existe plusieurs définitions équivalentes : un morphisme...).

Autres notions de consistance

La notion de consistance par arcs peut se généraliser : consistance par chemins par exemple.

On peut aussi considérer, lorsque les domaines sont des ensembles finis d'entiers, la consistance de bornes. Elle consiste à n'assurer l'AC que sur les bornes des domaines des variables. Ce type de consistance est particulièrement adapté aux contraintes linéaires avec les opérateurs de comparaison =, < ou ≠ .

Algorithmes AC

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 ( Seconde est le féminin de l'adjectif second, qui vient immédiatement après le premier ou qui s'ajoute à quelque chose de nature identique. La seconde est une unité de mesure du temps. La seconde...) variable Vj
  • Si (x,y) viole la contrainte, alors enlever y du domaine de la variable Vj
  • Répéter ces vérifications pour toutes les contraintes impliquant la variable Vj

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 (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) 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 seconde 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 tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) le domaine de Vj par y est inefficace. Si dans une étape précédente, la vérification a déjà été faite pour une valeur y 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 cette valeur y.

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 (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un événement, etc.) 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).

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 (Dans les algorithmes de programmation par contraintes, la propagation de contraintes permet de réduire les domaines des variables, dans le but d'accélérer le parcours de l'arbre de recherche.) 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éfault un algorithme de type AC3 ou AC2001 pour les contraintes définies par des ensembles de valeurs permises et interdites (contraintes tablulaires), 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).

Page générée en 0.073 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique