Problèmes de satisfaction de

contraintes
 Exemple : colorier une carte
On possède une carte d’Australie montrant ses territoires et
états. On a trois couleurs à notre disposition Rouge, Bleu et Vert.
Notre problème est de colorier chaque état de sorte que deux
états voisins n’aient jamais la même couleur.
 CSP

• Un CSP est défini par:

– Un ensemble de variables: X1, X2, …, Xn. Chaque variable Xi a un
domaine non vide de valeurs possibles.
– Un ensemble de contraintes: C1, C2, …, Cm
• Un état est une affectation de valeurs pour quelques unes
ou toutes les variables.
• Affectation consistante: aucune violation de contraintes.
• Affectation complète: toutes les variables ont une valeur.
• Solution: Affectation complète et consistante.
• Si solution optimale, il convient d’ajouter une fonction
objective
 Exemple CSP
• Ensemble des variables : X = {WA,NT,SA,Q,NSW,V,T}
• Domaine de chaque variable Di = {rouge, bleu, vert}
• Ensemble des contraintes C = {WA ≠NT, WA ≠ SA, NT≠ SA, SA ≠ Q, SA ≠
NSW,SA ≠ V,NT ≠ Q,Q ≠ NSW, NSW ≠ V}
• Une solution possible : {WA = rouge,NT = vert,Q = rouge,NSW =vert,V =
rouge,SA = bleu,T = rouge}
 Exemple CSP
• Ensemble des variables : X = {WA,NT,SA,Q,NSW,V,T}
• Domaine de chaque variable Di = {rouge, bleu, vert}
• Ensemble des contraintes C = {WA ≠NT, WA ≠ SA, NT≠ SA, SA ≠ Q, SA ≠
NSW,SA ≠ V,NT ≠ Q,Q ≠ NSW, NSW ≠ V}
• Une solution possible : {WA = rouge,NT = vert,Q = rouge,NSW =vert,V =
rouge,SA = bleu,T = rouge}
 Intérêt d’un CSP
• Utilisation des contraintes pour éliminer un bon nombre
d’états
• Par exemple dès que SA = bleu, aucun nœud voisin ne peut
prendre la couleur bleu.
• Au lieu de devoir considérer 35 = 243 allocations possibles une
fois que SA = bleu, il ne reste plus que 25 = 32 allocations
possibles !
• Dans les recherches dans les espaces d’états, on peut
simplement demander “cet état est-il oui ou non solution”
• Avec un CSP, si une solution partielle n’est pas solution, on n’a
pas besoin de considérer ses complétions
 Domaine
Le domaine d’une variable peut être:
• discret et fini: on pourrait énumérer toutes les possibilités
pour les contraintes
• infini : un langage de contraintes est nécessaire pour
représenter toutes les contraintes sans énumération
• continu : par exemple en programmation linéaire, les
contraintes sont des égalités ou inégalités de combinaisons
linéaires des variables
 Les contraintes
Les contraintes peuvent être:
• unaires : les contraintes ne concernent qu’une variable
• binaires : met en relations deux variables. Si toutes les
relations sont binaires, on peut représenter le problème avec
un graphe.
• complexes : la relation est entre trois variables ou plus
• globales : met en relation toutes les variables (par exemple,
une contrainte peut être que toutes les variables prennent
des valeurs différentes)
• pour des domaines discrets et finis, on peut toujours se
rapporter à un problème avec des relations binaires (en
introduisant des variables auxiliaires).
• certaines contraintes indiquent des préférences, ex : dans un
problème d’emploi du temps, professeur A préfère enseigner
le matin et professeur B l’après midi
 Applications des CSP

• Problèmes d’assignation
Ex: Qui enseigne quel cours?
• Problèmes d’horaire
Ex: Quelle classe, quand et où?
• Planification pour le transport
• Planification à l’intérieur d’une usine
 Exemple: Problème des n-reines
• On veut disposer n reines sur un échiquier de taille 𝑛 × 𝑛 sans
qu’aucune reine ne s’attaque :
– ensemble de variables est l’ensemble des reines : X = {R1, .
. . ,Rn}
– le domaine de chaque reine est l’ensemble des positions
sur l’échiquier
– les contraintes indiquent que les reines ne doivent pas
s’attaquer entre elles
• On peut aussi réduire le nombre d’états en ajoutant que la
reine i est placée sur la colonne i
 Exemple: Sudoku
• 81 variables
• cases vides : domaine {1, 2, 3, 4, 5, 6, 7, 8,9}
• cases remplies : domaine est un singleton contenant le chiffre
• Une contrainte allDiff par ligne, par colonne, et par carré
 Exemple: problème d’ordonnancement

• On a un ensemble de n tâches → variables X = {T1, . . . ,Tn}

• Chaque tâche Ti a une durée di
• Certaines tâches doivent être effectuées avant d’autres → contraintes
• Objectif : trouver un temps (par exemple en minute) où chaque tâche doit
commencer → domaine

Exemple1 : tâche T1 dure d1 = 10min et doit être effectuée avant tâche T2:
T1+d1 T2

Exemple2 : on veut dire que deux tâches T3 et T4 ne peuvent pas avoir lieu en
même temps (par exemple si les deux tâches utilisent un outil en commun).
Ici, on veut exprimer que: soit on fait T3 avant T4 ou l’inverse, mais on ne veut
satisfaire qu’une seule des deux contraintes
(T3+d3 ≤ T4) ∨(T4+d4 ≤ T3)
 Principe de résolution d’un CSP

• assigner une valeur à une variable va avoir un impact sur les

valeurs possibles pour les autres variables: c’est la
propagation

• essayer des affectations de variables: c’est la recherche

combiner recherche et propagation

 Recherche avec retours-arrière

• L’assignation des variables est commutative

Ex: [WA = rouge suivi de NT = vert] est la même chose que [NT =
vert suivi de WA = rouge]
• A chaque noeud, on a seulement besoin de considérer
l’affectation d’une seule variable.
Ex: si on a n variables pouvant chacune prendre b valeurs, il y a bn
feuilles
• on va effectuer une recherche en profondeur d’abord où à
chaque niveau, on cherche à affecter une variable, on fait
un retour-arrière( backtrack) à chaque fois qu’il n’y a plus
de valeurs disponibles pour affecter une variable, on
retourne à la variable précédente et on essaye une autre
valeur.
Exemple de recherche avec retours-arrière
 Ordre des variables et des valeurs
• Choix des variables: une astuce pour minimiser l'espace de recherche

– Heuristique du nombre de valeurs restantes minimum (minimum

remaining values (MRV)): Choisir la variable avec le moins de valeurs
possibles.

NT
WA
Q

SA
NSW
VV
VV
V
VV
V
T
 Ordre des variables et des valeurs
• Choix des variables:
– Heuristique du nombre de valeurs restantes minimum (minimum
remaining values (MRV)): Choisir la variable avec le moins de valeurs
possibles.

NT
WA
Q

SA
NSW
VV
VV
V
VV
V
T
 Ordre des variables et des valeurs
• Choix des variables:
– Heuristique du degré: Choisir la variable présente dans le plus de
contraintes.

NT
WA
Q

SA
NSW
VV
VV
V
VV
V
T
 Ordre des variables et valeurs
• Choix des valeurs:
– Heuristique des valeurs les moins contraignantes (least
constraining‐value): Choisir la valeur qui va enlever le
moins de choix pour les variables voisines.

NT
WA
Q

SA
NSW
VV
VV
V
VV
V
T
 Ordre des variables et valeurs
• Choix des valeurs:
– Heuristique des valeurs les moins contraignantes (least
constraining‐value): Choisir la valeur qui va enlever le
moins de choix pour les variables voisines.

NT on peut choisir bleu pour Q

WA
Q

SA
NSW
VV
VV
V
VV
V
T
 Ordre des variables et valeurs
• Choix des valeurs:
– Heuristique des valeurs les moins contraignantes (least
constraining‐value): Choisir la valeur qui va enlever le
moins de choix pour les variables voisines.

on préfère donc rouge à bleu car rouge

NT
laisse plus d’option pour SA
WA
Q

SA
NSW
VV
VV
V
VV
V
T
 Propagation de contraintes

Comment mettre à jour les domaines des variables voisines lorsqu’on a choisi
une valeur pour une variable ?

• Noeud cohérence : une variable est “noeud cohérente” si elle satisfait

toutes les contraintes unaires.
Il suffit de boucler sur chaque variable pour garantir cette cohérence.
• Arc cohérence : Un arc entre X et Y est cohérent si pour toutes les valeurs
x de X, il y a au moins une valeur possible y de Y. Ex:
– contrainte Y = X2
– domaine de X et Y : ce sont des chiffres DX = DY = {0, 1, 2, 3,4, 5, 6, 7, 8,9}
– pour que (X,Y) soit arc cohérent, réduction à DX = {0, 1, 2,3}
– pour que (Y,X) soit arc cohérent, réduction à DY = {0, 1, 4,9}
• Si X perd une valeur, les voisins de X doivent être revérifiés
• le CSP est arc cohérent si tous ses arcs sont cohérents
 Z<X Y=X2
Z X Y
queue DX DY DZ Paire
rajoutée

(X,Y) (Y,X) (X,Z) (Z,X) {0,1,2,3,4,5,6 {0,1,2,3,4,5,6, {0,1,2,3,4,5,6,7

,7,8,9} 7,8,9} ,8,9}

(Y,X) (X,Z) (Z,X) {0, 1, 2,3} {0,1,2,3,4,5,6, {0,1,2,3,4,5,6,7 (Z,X)

7,8,9} ,8,9}

(X,Z) (Z,X) {0, 1, 2,3} {0, 1, 4,9} {0,1,2,3,4,5,6,7

,8,9}

(Z,X)(Y,X) {1,2,3} {0,1,4,9} {0,1,2,3,4,5,6,7 (Y,X)

,8,9}
(Y,X) {1,2,3} {0,1,4,9} {0,1,2}

{1,2,3} {1,4,9} {0,1,2}

• après l’exécution de l’algorithme, on a un CSP équivalent
mais il peut y avoir moins de valeurs dans chaque domaine
la recherche pour résoudre le CSP sera sûrement
plus facile

• pour des contraintes binaires, la complexité de l’algorithme

est O(cd3) où d est le nombre de valeurs maximum dans
chaque domaine et c est le nombre de contraintes

• Remarque:Si on a seulement deux couleurs, le csp est arc-

cohérent mais il n’y a pas de solution !: WA, NT et SA se
touchant, il faut au moins 3 couleurs !
l’arc-cohérence ne peut détecter le problème
 Autres types de cohérence

• cohérence de chemin {Xi,Xj} est “chemin-cohérent” par rapport à

Xk si pour chaque affectation Xi = a et Xj = b cohérente avec les
contraintes sur {Xi, Xj}, il existe toujours une affectation de Xk
cohérente avec les contraintes sur {Xi,Xk} et {Xj,Xk}.
ex : Coloration de la carte avec deux couleur rouge et bleu.
Question : Peut-on rendre {WA,SA} chemin-cohérent par rapport à NT ?
affectation WA=bleu et SA=rouge.
→NT ne peut pas être affecté sans violer une contrainte (WA ≠NT ou SA≠
NT).
→ on détecte l’impossibilité.
• k-cohérence: (Notion plus forte) un CSP est k-cohérent si pour
chaque ensemble de k-1 variables et pour chaque affectation
cohérente de ces variables, une valeur cohérente peut toujours être
trouvée pour la kième variable.
si je teste la n cohérence avec n est le ombre de variable => j ai trouvé la solution
 Forward checking

On allie la recherche et la propagation des

contraintes selon le principe suivant :
• on effectue une recherche en profondeur d’abord
• un noeud de l’arbre de recherche correspond à
l’affectation d’une variable. A chaque affectation
d’une variable X:
– on vérifie l’arc-cohérence entre chacun des voisins de
X dans le graphe des contraintes et X
– on réduit le domaine des voisins de X
• Remarque: on ne continue pas avec les voisins
des voisins
Algorithme
Certaines inconsistances ne sont pas détectées par forward checking
(ligne 2, NT et SA n’ont plus qu’une valeur disponible alors qu’ils sont voisins !)
 Z<X X=Y2
Z X Y
Solution partielle DX DY DZ
{} {0,1,2,3,4, {0,1,2,3,4, {0,1,2,3,4,
5,6,7,8,9} 5,6,7,8,9} 5,6,7,8,9}

{X=0} {0} {0} {} Retour en

arrière
{X=1} {1} {1} {0}
{X=1,Y=1} {1} {1} {0}

{X=1,Y=1,Z=0} {1} {1} {0}

 Gestion de contraintes spécifiques

Contrainte toutes différentes

• Toutes les variables doivent avoir des valeurs distinctes.
• S’il y a m variables, n valeurs possibles et m > n, alors les
contraintes ne peuvent pas être satisfaites.
• Algorithme:
– Enlever toutes les variables qui n’ont qu’une valeur dans leur
domaine et enlever cette valeur de toutes les autres variables
restantes.
– Continuer tant qu’il y a des variables avec un domaine
contenant qu’une seule valeur.
– Si un domaine vide est produit, ou qu’il y a plus de variables que
de valeurs disponibles, alors une incohérence a été détectée.
 Exemple

On va étudier les variables: E6, I6, A6, …

Avec cet exemple, on peut résoudre entièrement le sudoku sans faire de
recherche !
 Autres contraintes spécifiques

Il existe d’autres types de contraintes globales

• contraintes sur les ressources :
– ex : au Plus on peut vouloir dire que la somme des
valeurs des variables A, B, C et D soit 10. Si les
domaines sont {2, 3, 4, 5,6} on peut enlever 5 et 6
de chaque domaine !
• contraintes avec des bornes:
– ex : si A+B = 420 et DA = [0,165], DB = [0,385], on
peut réduire le domaine à DA = [35,165], DB =
[255,385]
 Une approche différente : la recherche locale

Au lieu de construire une solution en affectant une à une les variables, on

peut partir d’une affectation complète (qui n’est pas cohérente) et essayer de
modifier l’affectation.
• Quelle variable corriger ? Elle peut être choisie au hasard
• Quelle valeur choisir ? heuristique du minimum de conflit : choisir la
valeur qui a le minimum de conflits avec les autres variables.