Problèmes de Satisfaction de

Contraintes
(CSP)
Définitions & exemples
 Un CSP P = (X, D, C) est défini par :
 des variables : X = { X1, X2 … Xn }
 des domaines : D = { D1, D2 … Dn } , Xi prend ses valeurs dans
l ’ensemble fini discret Di
 des contraintes : C = { C1, C2 … Cm },

la contrainte Ci est une relation Ri définie sur un sous ensemble de

variables Si :
 Si  X , l ’ensemble des variables sur lesquelles elle porte: S i = {Xi1, Xi2, … Xini}

 Ri, l ’ensemble des combinaisons de valeurs satisfaisant Ci : Ri  Di1 x Di2 x… xDini

 Ci = <Si, Ri>. | Si | est appelée l ’arité de Ci

 Une solution est une instanciation des variables satisfaisant toutes les
contraintes.
Définitions & exemples

 Soit P= (X, D,C) avec X = { X1, X2, X3, X4} et C = { C1, C2, C3}
 (X,C) : graphe (ou hypergraphe) de contraintes
 CSP binaire : contraintes d ’arité 2 (graphes)
 CSP n-aires : contraintes d ’arité quelconque (hypergraphes)

X2 X3

C1 C2

X1 X4
C3
Définitions & exemples
 Soit P= (X, D,C)
 X = { X1, X2, X3, X4} et
 D = { D1, D2, D3, D4}, D1= D2= D3= D4= {a,b}
 C = { C1, C2, C3},
 C1= < S1 , R1> C2= < S2 , R2> C3= < S3 , R3>

R1 R2 R3
X1 X2 X3 X2 X3 X4 X1 X4
b a a a b a a a
a a b b a a b a
a b a b a b b b
Définitions & exemples
 Représentations des contraintes
contraintes binaires
X Y
Ck
 En intension : Y = X 2 , X  Y
 En extension (par table) : Rk Rk
DX DY y1 y2 y3
x1 y1
x1 1 0 0
x2 y1  
x3 y2 x2 1 0 0
x3 0 1 0 

Dx Dy
 Par graphes : x1 y1
x2 y2
x3 y3
 D(X1) =

Exemple X1
{FRITES,
COUSCOUS,
RIZ, SALADE}
• Problème des mots croisés
X1 L12 = L21 L15 = L35
F
X2 R C L
I
T X2 X3
X3 M O U L E S
D(X2) = D(X3) =
S
{MOULES,
{RCL, OM, PSG, LOSC, CRIL} SARDINES,
CREVETTES,
VIANDE,
MAYONNAISE,
VINAIGRE}

Lij : jème lettre de Xi

Exemple 1: problème des 4-
Reines
Placer 4 Reines sur un échiquier de Formulation standard du problème:
4x4 tq. deux Reines ne soit pas sur la • Variables: chaque ligne est une variable.
même ligne, colonne, ou diagonale.
1 2 3 4
Q Q X1 Q
Q Q X2 Q
Q Q X3 Q
Q Q X4 Q
• Domaines: Di {1,2,3,4}.

• Contraintes: Il y a ( 4 ) = 6 contraintes: i  j , Xi  Xj  j  i
2
R12 {(1,3)(1,4)(2,4)(3,1)(4,1)(4,2)} • Graphe de contraintes :
R13 {(1,2)(1,4)(2,1)(2,3)(3,2)(3,4)(4,1)(4,3)} X1 X3
R14 {(1,2)(1,3)(2,1)(2,3)(2,4)(3,1)(3,2)(3,4)(4,2)(4,3)}
R23 {(1,3)(1,4)(2,4)(3,1)(4,1)(4,2)} X2 X4
R24 {(1,2)(1,4)(2,1)(2,3)(3,2)(3,4)(4,1)(4,3)}
R34 {(1,3)(1,4)(2,4)(3,1)(4,1)(4,2)}
Exemple 2: Coloriage de
graphes
 Colorier une carte géographique tq. Deux régions (pays)
adjacents soient de différentes couleurs

(R,V,B)
X1
 

X2 X3

(R,V,B) (R,V,B)
Exemple 3 :Conception
 Les contraintes sur les parties du véhicule
 par-chocs blanc (white)
 toit ouvrant rouge (red)
 enjoliveurs rose (pink) ou rouge
 capot et portières rose, rouge ou noir (black)
 carrosserie blanc , rose, rouge ou noir
 Les contraintes du concepteurs…
 pare-chocs, toit ouvrant et enjoliveurs plus clairs que la
carrosserie
 portières, carrosseries et capot de la même couleur
 Trouver une configuration possible du véhicule
satisfaisant les contraintes.
Exemple 3 :Conception
portières
pare-chocs
(w,p) (p,p)
w (w,r) p, r, b
(r,r)
(w,b) (b,b)
toit ouvrant (p,p)
(r,b) (r,r)
r w, p, r, b (b,b)
enjoliveurs carrosserie (p,p)
(p,r)
(r,r)
p, r (p,b)
(b,b)
p, r, b
(r,b)
capot
plus clair que
de la même couleur
 Exemple 3 : Vision [Walz:75]
Problème :
reconnaître des objets 3D
en interprétant les lignes sur un dessin 2D

D
Exemple 3 : Vision [Walz:75]
Sur le schéma ci-dessous, il existe quatre types de
jonctions (points de rencontre entre les arêtes) :
Exemple 3 : Vision [Walz:75]

En suivant la flèche dans cette direction l’objet est sur la droite;

sur votre gauche l ’espace est vide.

+
Une arête extérieure, l ’objet est sur les deux cotés :
arêtes intérieures convexes

-
Une arête intérieure : arêtes intérieures concaves
 Exemple 3 : Vision [Walz:75]
On distingue les cas suivants : (seules certaines combinaisons sont
possibles pour des arêtes adjacentes à une jonction)
+ - -
L +

Y + - -
+ - -
+ - -

T
+ -

- - + +
Flèche + -
+
 Exemple 3 : Vision [Walz:75]
Formalisation :
• variables : les arêtes
• domaines : les labels
• jonctions : les contraintes

+ +
+ -
-
+ + +
+ + +
- +
+ - + +
- -
+

Un étiquetage consistant est une interprétation possible

CSP
Enoncés possibles

Existe t-il une solution?

Trouver une solution
Trouver toutes les solutions
Trouver le nombre de solutions
Telle valeur figure-t-elle dans une solution?
Trouver toutes les valeurs possible pour une variable
Trouver une valeur figurant dans toute les solutions
Trouver une solution optimale
…

Le problème de décision est NP-Complet

Transformations CSP-naires vers
CSP binaires
 La transformation est obtenue en utilisant des variables
auxiliaire .
 Pour une contrainte portant sur 3 variables X, Y, Z on crée une
variable U, tq :
Dx = {1,2}; Du = {(1,3,5), (1,3,6), (1,4,5), (1,4,6),
Dy={3,4}, (2,3,5), (2,3,6), (2,4,5),(2,4,6)}
Dz={5,6}
 Exemple : Soit la contrainte :
 X+Y=Z
Dx = {1,2}; Du = {(1,4,5), (2,3,5), (2,4,6)}
Dy={3,4},
Dz={5,6}
Transformations CSP-naires vers
CSP binaires
1) en gardant les variables originales :
Introduire une nouvelle contrainte : X = ième argument de
(U)
Z {5,6}
X+Y=Z, X<Y
Dx = {1,2}; Z= arg3(U)
Dy={3,4}, U= {(X,Y,Z) & X+Y=Z}
U {1,4,5), (2,3,5), (2,4,6)}
Dz={5,6} X= arg1(U) Y= arg2(U)

X X<Y Y
{1,2} {3,4}
Transformations CSP-naires vers
CSP binaires
1) Sans les variables originales :
Introduire une nouvelle contrainte :
ième arguments de(U) = jème argument de (V)
X+Y=Z, X<Y
Dx = {1,2};
U= {(X,Y,Z) & X+Y=Z} U {1,4,5), (2,3,5), (2,4,6)}
Dy={3,4},
Dz={5,6} Arg1(U)= arg1(V) Arg2(U)= arg2(V)
V= {(X,Y) & X<Y} V {1,3), (1,4), (2,3), (2,4)}
Méthode standard de
résolution : le backtrack
 A chaque étape, l ’instanciation partielle courante est étendue en
instanciant un nouvelle variable par une valeur compatible avec
l ’instanciation courante :
X1 X2 … Xk-1 Xk

d1 d2 … dk-1 dk  Dk
 Si aucune valeur dk  Dk n ’est compatible, alors il y a un retour en
arrière (chronologique) sur la variable précédente Xk-1 pour essayer
une autre valeur d’k-1  Dk-1

X1 X2 … Xk-1

d1 d2 … d’k-1 Dk-1
Approche fortement combinatoire : O(dn)
Filtrages et prétraitements
 Consistance (ou cohérence)
propriété liée à la compatibilité entre valeurs de domaines et
contraintes
 Filtrage
élimination d ’éléments dont on est assuré qu ’ils ne peuvent figurer
dans une solution (valeurs ou n-uplets de relations)
P = (X,D,C) P ’= (X, D’, C’)
 Propriété d ’un filtrage
 simplification du problème par réduction de l ’espace de recherche
 dans certains cas détection de l ’inconsistance
 Plusieurs niveaux de consistances
consistance locales ou partielles jusqu ’à consistance globale
 coût du filtrage plus ou moins élevé
(obtention consistance globale  résolution du problème)
La consistance d ’arc (AC)
 Définition

Di  D est AC ssi, a  Di , x j  X t.q. Cij  C ,
b  D j t.q. Rij (a, b)
 Un CSP est AC ssi Di  D, Di  et Di est AC
x1
1 2 C13

1 2

x2 1 C23 x3
2
Arc Consistant
Inconsistant
La consistance d ’arc (AC) : AC1
 Filtrage par consistance d ’arc : suppression des valeurs
qui ne vérifient pas la propriété (AC)
L’algorithme AC1 (Macworth
1977)

Algorithme AC-1
répéter
pour chaque contrainte Ck faire
Réviser(Ck)
jusqu’à plus de changement

Réviser(Ck) { Ck = (Xi,Xj)}
pour tout di  Di faire
si  dj  Dj telle que (di,dj)  Rk
alors supprimer di de Di
pour tout dj  Dj faire
si  di  Di telle que (di,dj)  Rk
alors supprimer dj de Dj
L’algorithme AC1 (Macworth
1977)
procédure Réviser((i,j))
changement  faux
pour di  Di faire
si  dj  Dj telle que (di,dj)  Rk
alors supprimer di de Di
changement  vrai
fin si
fin pour
retourner changement
fin

procédure AC-1(G)
répéter
changement  faux
pour chaque arc (i,j)  G faire
changement  réviser((i,j)) ou changement
fin pour
jusqu ’à non (changement)
fin AC-1
L’algorithme AC1
 Quels sont les défaut de AC-1?
 Si un domaine est réduit alors tout les arcs sont testés
(révisés) même si le domaine touché n ’a aucune influence sur
la plus part des arcs
 Quels sont les arcs à reconsidérer ?
 Les arcs affectés par le filtrage du domaine
i.e., les arcs reliés à la variable touchée (arcs entrants).
 Ignorer les arcs incident de la variable touché (arcs sortants)

Variable touché

Arc dont la révision

a provoqué la réduction
du domaine
L’algorithme AC3 [Mackworth
1977]
 utiliser une file pour mémoriser les arcs à (re-)réviser
 enfiler uniquement les arcs affectés par la réduction des
domaines.

procedure AC-3(G)
Q  {(i,j) | (i,j)  arcs(G), i < j} % file pour les arcs à réviser
tant que Q non vide faire
sélectionner et supprimer (k,m) de Q
si réviser((k,m)) alors
Q  Q {(i,k) | (i,k)  arcs(G), i  k, i  m}
fin si
fin tant que
fin

 AC3 est l ’algorithme le plus utilisé

L ’algorithme AC3 : observations
 Révision d ’un arc : de nombreuses paires de valeurs sont testées
 Ces tests sont répétés à chaque fois qu ’un arc est révisé

1. Quand l’arc <X2,X1> est révisé, la valeur a

a a a est supprimé du domaine de X2
b b b 2. le domaine de X3 doit être exploré pour
déterminer si les valeurs a,b,c et d
c c c perdent leur support dans X2
d d d
X1
 Observation :
X2 X3
 il n ’est pas nécessaire d ’examiner les valeurs a, b et c de X3 (elles
admettent un autre support autre que a dans X2)
 L ’ensemble support de a Di est l ’ensemble {<j,b> | b  Dj , (a,b) Rij}
Calcul et utilisation des
ensembles supports
 L ’ensemble des valeurs supportés par une valeur donnée (si la valeur est
supprimée alors ses valeurs perdent un support) et le nombre de ces
valeurs supports sont calculés.
procédure Initialiser(G)
Q  {} , S  {} % initialiser les structures de données
pour chaque arc (Xi,Xj)  arcs(G) faire
pour a  Di faire
total  0
pour b  Dj faire
si (a,b)  Rij alors
total  total + 1 • Sj,b - l ’ensemble des pairs <i,a> tq.
Sj,b  Sj,b  {<i,a>} <j,b> les supportent i.e. (a,b)  Rij
fin si • compteur[(i,j),a] - nombre de supports
fin pour
compteur[(i,j),a]  total pour une valeur a  Di dans Dj
si compteur[(i,j),a] = 0 alors
supprimer a de Di
Q  Q  {<i,a>}
fin si
fin pour
fin pour
retourner Q
fin % Initialiser
Calcul et utilisation des supports
Compteur(i,j) i j Sj...

2 a1 b1 <i,a1>,<i,a2>
2 a2 b2 <i,a1>
1 a3 b3 <i,a2>, <i,a3>

 Utilisation des ensembles supports :

1. soit b3 une valeur supprimée du domaine de j.
2. Pour chaque élément de Sj,b3 (i.e. <i,a2>,<i,a3>).
 Décrémenter les compteurs de ses valeurs (i.e. elles ont perdues un support)
(compteur[(i,j),a2] et compteur[(i,j),a3] )
3. Si un compteur devient nul (a3) alors supprimer la valeur et aller en 1.

Compteur(i,j) i j Sj...

2 a1 b1 <i,a1>,<i,a2>
1 a2 b2 <i,a1>
0 a3 b3
Algorithme AC4 [Mohr &Henderson
1986]
procedure AC-4(G)
Q  Initialiser(G)
tant que Q est non vide faire
sélectionner et supprimer une pair <j,b> de Q
pour chaque <i,a> de Sj,b faire
compteur[(i,j),a]  compteur[(i,j),a] - 1
si compteur[(i,j),a] = 0 & a  Di alors
supprimer a de Di
Q  Q  {<i,a>}
fin si
fin pour
fin tant que
fin AC-4
Inconvéniant : complexité en espace élevée
Autres algorithmes d ’AC

 AC-5 (Hentenryck, Deville, Teng 1992)

 un algorithme d ’AC générique

 peut être réduit à AC-3 et AC-4

 exploite la sémantique des contraintes (e.g. fonctionnelle )

 AC-6 (Bessiere 1994)

 maintient un seul support pour une valeur, le prochain support est calculé au

moment de la suppression de ce support

 améliore la complexité en espace et la complexité en moyenne d ’AC4

 AC-7 (Bessiere, Freuder, Regin 1999)

 basé sur le calcul et l ’exploitation des supports (comme AC-4 et AC-6)

 exploite la symétrie des contraintes

Arc consistance directionnelle
(DAC)
 Observation : les algorithmes d ’AC effectuent des
révisons répétées des arcs; le nombre total de révisions
dépends du nombre d ’arc mais aussi de la taille des
domaines (présence de cycles).
 Est-il possible d ’affaiblir AC de manière à réviser chaque
arc une seule fois?

 Définition : un CSP est arc consistent directionnelle (DAC)

étant donné un ordre sur les variables ssi tout arc (i,j) tq.
i<j est arc consistant.
 Chaque arc est révisé, mais uniquement dans une seule
direction
Algorithme DAC
1. Les arcs sont considérés dans une seule direction
2. Les variables sont ordonnées
 pas de cycle dans le graphe !

procedure DAC(G)
pour j = |noeuds(G)| à 1 faire
pour chaque arc (i,j) dans G tq. i<j faire
Réviser((i,j))
fin pour
fin pour
fin
Quand et comment utiliser DAC
 AC est plus général que DAC (si un CSP est AC alors il est aussi
DAC
 DAC est-il utile ?
 DAC est plus rapide que tout algorithme AC-x
 Il existe des problèmes pour lesquels DAC est suffisant
 Exemple: Si le graphe de contraintes du CSP forme un arbre alors
DAC est suffisant pour résoudre le CSP sans retours arrières
 Quel ordre utiliser pour DAC?
 Appliquer DAC de la racine aux feuilles de l ’arbre.
 DAC assure pour chaque valeur du fils
l ’existence d ’une valeur compatible
avec son père
 Relation entre AC et DAC
 Exemple:
V ={X,Y,Z}
Dx = Dz= {1,2}, Dy = {1}
C = {X Z,Y<Z}

• En utilisant l‘ordre X,Y,Z : •En utilisant l ’ordre Z,Y,X :

pas de suppression de valeurs une valeur est supprimée du domaine de Z,
le CSP obtenue est DAC mais pas AC
{1,2}
Z {2}
XZ Y<Z
Z
XZ Y<Z
{1,2} X Y {1} Y {1}
{1,2} X
• Si l ’ordre X, Y, Z est encore utilisé alors le CSP deviendra aussi AC
De Dac à AC pour les CSP
structurés en arbre
 Si on applique DAC à un CSP structuré en arbre :
1. en utilisant l ’ordre de la racine aux feuilles
2. et dans l ’ordre inverse.
On obtient un CSP arc consistent
 Preuve :
 chaque valeur admet un support dans les nœuds fils (1.)
 chaque valeur admet un support dans le nœud parent (2. ),
 on obtient un CSP AC
Est-ce que AC est suffisant pour
résoudre un CSP?
 En appliquant les algorithmes AC on peut supprimer de nombreuses valeurs
incompatibles
– Peut-on obtenir une solution?
– Ou déterminer qu’une telle solution existe?
 Malheureusement, la réponse est NON!
Exemple : {1,2}
 Le CSP est arc consistent Z
mais n ’admet aucune solution XZ YZ
 Alors quel est le rôle de AC ?
 Dans certains cas on obtient une solution après l ’application de ACX
{1,2} Y {1,2}
 si on obtient un domaine vide (par AC) alors le CSP est inconsistant XY
 Si tout les domaines ont été réduit à une seul valeur (singleton) alors on obtient une solution du
CSP
 Dans le cas général AC supprime des valeurs
 réduit la taille de l ’espace de recherche
La consistance de chemin (PC)
Définition :
 ( xi , x j ) est PC ssi, (a, b)  Rij , xk  X ,
c  Dk t.q. (a, c)  Rik et (b, c)  R jk

Un CSP est PC ssi, xi , x j  X , ( xi , x j ) est PC
x1

1 2 C13

Chemin
CheminInconsistant
Consistant
1 2

x2 1 C23 x3
2
Chemin consistance directionnelle
(DPC)

 un CSP P est DPC par rapport à un ordre (x1 , x 2 , ..., x n )

si ( xi , x j ) et (a, b)  Rij , k , k  i, j ,
c  Dk t.q. (a, c)  Rik et (b, c)  R jk
x1 2 2 x3
1 1

 DPC pour (x1, x2, x3), pas 1 (x3, x2, x1)

x pour
2 2
Relation entre PC et AC
 Est-ce que PC subsume AC ?
i.e. si un CSP est PC, est-il aussi AC?
 un arc (i, j) est consistent (AC) si le chemin (i,j,i) est PC
 PC implique AC
 est-ce que PC est plus fort que AC (y a t ’il un CSP AC mais pas PC)?
 Exemple : P= (X,D,C)
 V= {X,Y,Z}
 Dx = Dy= Dz ={1,2},
 C = {XZ, X  Y, Y  Z}
P est AC, mais pas PC (X=1, Z=2 ne peut être étendu à Y et Z)
 AC supprime des valeurs des domaines ,
 PC supprime des pairs de valeurs (tuples dans les relations)
 PC rend les contraintes explicites (A<B,B<C  A+1<C)
Contraintes : représentation
matricielle
 Pour supprimer des couples de valeurs
 les contraintes doivent être représenté en extension
contraintes binaires = matrice de 0 et 1
0 - les valeurs sont incompatibles
1 - les valeurs sont compatibles
 Opérations sur les contraintes :
Intersection Rij & R‘ij composition Rik * Rkj  Rij
(et bit à bit) (multiplication binaire de matrice)
Composition des contraintes
d ’un chemin
 Exemple : P = (V,D,C)
V={A,B,C}
Da = Db = Dc = {1,2,3},
C= { B>1, A<C, A=B, B>C-2}

 Comment rendre consistent le chemin (i,k,j) ?

 Rij  Rij & Rik * Rkk * Rkj
Algorithme PC1
 procédure Réviser( (x, y), z) )
pour chaque pair (a,b)  Rxy faire
si ( c  Dz tq. (a,c)  Rxz et (b,c)  Ryz )

alors supprimer (a,b) de Rxy
fin si
fin pour
fin
 procédure PC-1(P= (X, D, C) )
n  |X|
répéter
pour k = 1 à n faire
pour i = 1 à n faire Rii  Rii & (Rik * Rkk * Rki)
pour j = 1 à n faire  AC1
Rij  Rij & (Rik * Rkk * Rkj) /* Reviser( (i,j), k) */
jusqu’à (non (changement) )
fin
 Remarque : L ’absence de contrainte entre x et y, peut être vu comme une contrainte
universelle (Rxy = Dx x Dy)
Algorithmes PC
 PC1, PC-2 [Macworth 77]
 PC-3 [Mohr & Anderson 86
 PC-4 [ Han Lee 88]
 PC-5 [Singh 95]
 …
 PC8 [Chmeiss & Jégou : 96]
 Inconvénients de PC :
 Complexité en espace
 PC élimine des pairs de valeurs
maintenir un CSP en extension (e.g. utiliser une matrice de 0 et 1)
 modification du graphe de contraintes
PC : suffit-elle à résoudre un CSP
 PC ne suffit pas a résoudre un CSP

Exemple : soit un CSP P= (V,D,C)

 V={B,C,D}
 Db =Dc = Dd = {1,2,3}
 A  B, A  C, A  D, B  C, B  D, C  D
P est PC mais n ’admet pas de solutions

1 2 3 1 2 3
 
 

1 2 3 1 2 3

Chemin consistance restreinte
(RPC)
 Peut-on obtenir un algorithme de filtrage (entre AC et PC)?
 plus fort que AC
 sans les inconvénients de PC (espace mémoire, modification du
CSP)
 Chemin consistance restreinte (Berlandier 1995)
 basé sur AC-4 (utilise les ensembles supports)
 des qu ’une valeur admet uniquement un support dans une
autre variable, PC est appliqué sur cette pair de valeurs
K-consistance
 Y a t ’il un formulation commune à AC et PC?
 AC: une valeur est étendue à une autre variable
 PC: une pair de valeurs est étendue à une autre variable
 … on peut continuer
 Définition : un CSP est k-consistent ssi toute instanciation consistante de
(k-1) différentes variables peut être étendue à une instanciation consistante
avec une variable supplémentaire (k)

CSP 4-consistant
K-consistance forte

3-consistant mais pas 2-consistant

Définition : un CSP P est fortement k-consistant ssi P est j-consistant pour

tout j  k.
 k-consistance forte  k-consistance
 k-consistance forte  j-consistance pour tout j  k

 NC (consistance de noeuds) = 1-consistance forte = 1-consistance

 AC = 2-consistance forte
 PC = 3-consistance forte
 Portés des différentes
consistances
X< 3
NC 12 3

<
AC 12 12

12
= =
PC
12 12

12

4-consistance 12 12
12
12
Techniques de consistance:
modifications apportées au CSP

AC

PC

4-(forte)consistance

Contrainte ternaire
k-consistance & résolution de CSP

 Pour un CSP à n variable, quelle k-consistance est suffisante

pour résoudre un CSP?

 n-consistance forte pour un CSP à n variables!

Un CSP P de n
variable
de domaines {1…n-1}

P est k-fortement consistant (k<n)

mais P est inconsistant

D(AC) est suffisant

P est un arbre
k-consistance & résolution de CSP
 Définition : un CSP est résolut par un algorithme glouton (sans
retour arrière : « backtrack free » ) si pour un certain ordre des
variables, on peut trouver une valeur pour chaque variable
compatible avec les variables déjà affectées

 Trouver un niveau de consistance suffisant (le plus petit) pour

résoudre un CSP?
k-consistance & résolution de CSP
 Quelques observations :
 pour éviter un retour arrière, une variable non instancié doit être
compatible avec les variables instanciés.
 si au cours de la recherche de solution, toute variable non
instancié est contrainte avec au plus k variables instanciés , on a
besoin de la (k+1)-consistance forte pour résoudre le CSP (sans
backtrack)
 le nombre maximum de contraintes entre une variable non
instancié et celles instanciés dépend de l’ordre des variables.
 Il est intéressant de trouver l ’ordre minimisant k
k-consistance & résolution de CSP
 un graphe ordonné est un graphe muni d ’un ordre total sur les
sommets
 Largeur d ’un sommet étant donné un graphe ordonné est le nombre
sommets qui lui sont reliés et qui le précédent dans l’ordre.
 Largeur du graphe ordonnée est le maximum des largeurs de ses
sommets.
 Largeur d ’un graphe est le minimum des largeurs de ces graphes
ordonnés.

Largeur du graphe 1
k-consistance & résolution de CSP

 Théorème : soit w la largeur du graphe de contraintes. Si le

CSP est k-fortement consistant pour k>w alors il existe un ordre
des variables tq. le CSP peut être résolu par un algorithme
glouton(sans retour arrière).

 Idée de preuve :

Au plus w
D ’autres forme de
consistances : (i,j)-Consistance
 k-consistance étends l ’instanciation des (k-1) variables à une nouvelle variable
 on supprime des (k-1)- tuples ne pouvant pas être étendu à une autre variable.

 Définition:
 un CSP est (i,j)-consistent ssi toute instanciation consistante de i variables peut être
étendue à j nouvelles variables.

 Un CSP est (i,j)-fortement consistant, ssi il est (k,j)-consistant pour tout k i

 Remarque :
 k-consistance = (k-1,1)-consistance; AC = (1,1)-consistance forte
 PC = (2,1)-consistance forte
Formes de consistances inverse
 Définition : (1,k-1)-consistance est appelée k-consistance inverse
 On supprime les valeurs qui ne peuvent pas être étendues de
manière consistante à (k-1) nouvelles variables

 Chemin consistance inverse (PIC) = (1,2)-consistance

 Consistance de voisinage inverse (NIC) (Freuder , Elfe 1996)
 On supprime les valeurs de la variable V ne pouvant pas être
étendues de manière consistante aux variables directement reliés à V
Filtrage pour les CSP généraux (n-
aires)
 Toutes les méthodes de filtrages se généralisent aux CSP généraux;
parmi elles :
 la consistance d ’arc
 une généralisation de la 2 consistance : l ’interconsistance
 P = (X,D, C) est interconsistant ssi les contraintes sont
compatibles 2 à 2 :
1.  Ci, Cj/ Ci  Cj , Ri[Ci  Cj ] = Rj [Ci  Cj ] 
2.  Ri, Ri 
issue des travaux sur les bases de données relationnelles[Beeri & al 83]
 Intérêt :
 condition plus forte que la consistance d ’arc
 consistance plus adaptée aux CSP n-aires (hypergraphes)
Filtrage par consistance d ’arc
généralisé
 Soit P= (X, D,C) a b X2 X3 a b d
 X = { X1, X2, X3, X4} et
C1 C2
 D = { D1, D2, D3, D4},

D1= D2= D3= D4= {a,b} abc X1 X4 ab

 C = { C1, C2, C3}, C3

 C1= < S1 , R1> C2= < S2 , R2> C3= < S3 , R3>

R1 R2 R3
X1 X2 X3 X2 X3 X4 X1 X4
b a a a b a a a
a a b b a a b a
a b a b a b b b
Filtrage par interconsistance
 Soit P= (X, D,C) a b X2 X3 a b d
 X = { X1, X2, X3, X4} et
C1 C2
 D = { D1, D2, D3, D4},

D1= D2= D3= D4= {a,b} abc X1 X4 ab

 C = { C1, C2, C3}, C3

 C1= < S1 , R1> C2= < S2 , R2> C3= < S3 , R3>

R1 R2 R3
X1 X2 X3 X2 X3 X4 X1 X4
b a a a b a a a
a a b b a a b a
a b a b a b b b
Filtrages : sommaire
 Diminution de l ’espace de recherche
 Coût raisonnable pour les consistances faibles (k3)
 Le filtrage par k-consistance (k>=3) peut entraîner une modification de la
structure du CSP
 Compromis : il est souvent nécessaire de trouver le bon compromis
entre le prétraitement et la recherche effective
complexité du filtrage :
 Efficacité pratique :
Bonne dans certains cas :
 consistance d ’arc : Vision [Waltz]
 consistances de chemin : contraintes temporelles
Faible parfois : problèmes des 8 reines
Résolution de CSP
 Algorithme de base : Backtrack
 Améliorer le Backtrack :
 avant la recherche
 filtrages (consistance d ’arc, de chemin, …)
 guider la recherche
 ordre de choix des variables
 ordre de choix des valeurs
 ordre de test des contraintes
 pendant la recherche
 approches prospectives («look-ahead») : emploi de filtres
 approches rétrospectives («look-back») : revenir à la cause d’échec

 Critères d ’évaluation :
 taille de l ’arbre de recherche & nombre de tests de consistance
 Les défauts du «backtrack»
classique
 Parcours inutile de certaines zones de l ’espace de recherche
(des valeurs trivialement incompatibles avec l ’instanciation courantes
ne sont pas supprimées)
 Le retour arrière chronologique peut entraîner des répétitions d ’échecs
causés par une même raison

L’instanciation (a,b) pour X1, X2

ab X3 provoquera des échecs répétés sur X3
alors que la cause réelle d ’échecs est

l ’incompatibilité avec X4
ab X4
 la taille de l  
’espace de recherche dépend de l ’ordre
d ’instanciation choisi
X1 ab ab X2
Heuristiques d ’ordonnancement
 Principe du «First-fail »
 Ordres :
 vertical : choix des variables
 horizontal : choix de valeurs
 ordre de test des contraintes

 statique : préétabli
 dynamique : évolue pendant la recherche
 Heuristiques classiques :
 choix de valeurs
recherche d ’une solution : choix les moins contraints
recherche de toutes les solutions : choix les plus contraints
 choix de variables
en fonction de critères structurels : degré, tailles des domaines ,
satisfiabilité des contraintes...
Heuristiques d’ordonnancement
 Choix de l’ordre des variables - un exemple [Nadel]
X3
C23: X2  X3 123 C34: X3 = X4+2
s23 = 5/6 s34 = 1/12
C24: X2 x X4 >1
X2 12 s24 = 7/8 1234 X4
C12: X1 X2
 s12 le
sij est = 1taux de satisfiabilité
1 X1de la contrainte Cij :
sij = |Rij| / |Di| x |Dj|
Trois heuristiques d ’ordonnancement des variables :
 H1 : le plus petit domaines d ’abord
 (X1, X2, X3, X4)
 H2 : la variable de degré max d ’abord
 (X2, X3, X4, X1) ou (X2, X4, X3, X1)
 H3 : contrainte la moins satisfiable d ’abord
 (X4, X3, X2, X1) ou (X3, X4, X2, X1)
Exemple : suite
H1 H1  29 noeuds
X1 1
X2 1 2
X3 1 2 3 1 2 3
X4 1234 1234 1234 1234 1234
H2  32 noeuds
H2
X2 1 2
X4 1 2 3 4 1 2 3 4
X3 123 123 1 2 3 1 2 31 2 3 123 123
X1
1
Exemple : suite
H3  19 noeuds
H3
X4 1 2 3 4
X3 123 123 123 123
X2 1 2
X1
1

Nécessité de compromis entre les différents critères

Exemples :
1. dom + degre : min dom, en cas d’égalité appliquer max degre
2. dom/degre : minimiser le rapport dom/degre [Régin & bessière]
Heuristiques: une approche multi-
niveaux
[Bessière-Chmeiss-Saïs]
 Objectif :
 tenir compte des voisinages des variables
 orienter la recherche vers la partie dense du CSP (difficile)

0 xi
1
2 xj
Heuristiques: une approche multi-
niveaux
 Formulation général
 x j  ( xi )
W ( Rij )
 W ( xi ) 
( xi )
W ( xi )
 H ( xi ) 
( xi )

 calcul deW ( Rij ) ? Peut être coûteux !!

 paramètre syntaxique simple ( ):

W ( Rij )  ( xi )   ( x j )
 1  x j ( xi )  ( x j )
 H ( xi )  ( ( xi )  )
( xi ) ( xi )
Heuristiques: une approche multi-
niveaux
 Généralisation : (niveaux)
 H 0 ( xi )  ( xi )
 1 xj  ( x )
H 
k 1(x j )

H k ( xi )  ( ( xi )  i
)
( xi ) ( xi )
 Instanciation de ( xi ) :
  ( x )  D( x ) :
i i
 H 0dom ( xi )  D ( xi )
D ( xi )  x j  ( xi )
D( x j )
 H 1dom ( xi )   2
( xi ) ( xi )
D ( xi )
 ( xi )  :  H dom / deg
H
,
dom / deg

( xi ) 0 1
Heuristiques: une approche multi-
niveaux

 Ordonnancement des variables

 une formulation générale
 paramétrable
 récupère la plus part des heuristiques connues
 multi-niveaux (notion de distance)
 calcul simple du poids des contraintes
 propriétés syntaxique

 pas de tests de consistance

 possibilité d ’utiliser différentes fonctions pour le calcul du poids

des contraintes
 amélioration significative des heuristiques connues
Ordre de test des contraintes
Ordre lexicographique : 47 tests de contraintes

H2
1 2
X2
1 2 3 4 1 2 3 4
X4 X2 x X4 >1        
1 2 3 1 2 3 1 2 3 1 2 31 2 3 123 123
X2 X3           
X3 X3 = X4+2 
X1 1
X1 X2


La contraintes la moins satisfiable d’abord : X3 = X4+2 31 tests

X2 X3
Améliorer le backtrack : emploi
de filtres
 Principe :
à chaque étape (1, …,k,…n),
 on instancie une nouvelle variable Xk
 On filtre : des valeurs devenues impossibles sont éliminées des domaines Di pour
i>k
Si un domaine Di devient vide, il y a alors retour arrière sur la variable
précédente
 Plusieurs niveaux de filtrages :
 Forward Checking (FC) (valeurs directement inconsistantes )
 Real Full Lookahead (RFL) , il exite deux version plus faible :
 Partial Lookahead (PL),
 Full Lookahead (FL)
 Maintaining Arc Consistency = FC +AC
 AC est appliqué avant la recherche et à chaque étape(RFL)
 choix couple (var, valeur)
Forward Checking (FC) [Haralick
80]
 L ’étape de filtrage, quand on a instancié Xk par dk ne
concerne que les variables Xi voisines de Xk avec i>k :
on supprime des Di les valeurs incompatibles avec dk.
X1
X2
. Variables déjà instanciées
.
Xk-1
Xk d

Filtrage : élimination des valeurs

incompatibles avec d
FC : schéma d’algorithme
 Procédure Forward-cheking (D, , k)
{D = (D1, …, Dn),  = (d1,…,dk) }
si k = n alors  est solution
sinon
pour tout Xi, i>k, Xi voisin de Xk faire
D’i := Di
pour tout di de D’i faire
si di et dk incompatibles alors
D’i := Di-{di}
fsi
fpour
fpour
si pour tout i >k, D’i   alors
pour tout dk+1 de D’k+1 faire
 := (d1,…,dk,dk+1)
forward-Checking(D ’, k+1)
fpour
fsi
fsi
Real Full Lookahead (RFL) [Harlick
80]
 L ’étape de filtrage, quand on a instancié la k-ième
variable, correspond à la suppression des valeurs des
domaines qui ne vérifient pas la consistance d ’arc.
 Appelé aussi MAC (Maintaining Arc Consistency)
AC est aussi appliqué avant la recherche

Variables instanciées Variables non instanciées

Backtracking Forward Cheking Real Full Lokahead

Comparaison sur les 4-Reines

Forward cheking
Backtraking

Real Full Lookahead

M(AC+)
[Chmeiss & Saïs 2000]

 Utilisation dynamique de PC ?
 Coût prohibitif !

 exploiter partiellement PC  DPC

M(AC+) = M(AC + DPC)
 Propriété :
Soit P ( X , D, C ) un CSP,
x i X ( xi ) 2 , Cij , Cik  C , si ( x j , xk , xi ) vérifie DPC
alors P est consistant ssi,
P' (X / xi , D/Di , C/ Cij ,Cik , R/ Rij ,Rik  ) est consistant
M(AC+) : un exemple

graphe de
largeur 2 arbre
M(AC+): schéma général
M(AC+) : schéma général

1. Maintenir l’arc consistance

2. Déconnecter singletons variable (str. arbre)
3. Maintenir la chemin consistance directionnelle
4. Déconnecter doubletons variables (str. Graphe lg. 2)
5. Choix d’un couple (variable, valeur)
6. Aller à 1.
Efficacité expérimentale
BT FC … RFL MAC

#noeuds

#tests

 Compromis à établir entre filtrage et recherche

 un filtre puissant entraine :
 diminution en taille de l ’espace de recherche

 mais aussi ralentissement de recherche

Retour arrière « intelligent »
 Backjumping basé sur la structure [Dechter 90]
En cas d ’échec sur une variable Xk, retour sur la
variable voisine de Xk la plus récemment instanciée.

En cas d ’échecs sur X6

X1

X2 Puis ici

X3 Revenir d ’abord ici

X4

X5
X6
Constraint recording [Dechter 90]
[Bruynooghe 84]

 En cas d ’échecs, l ’instanciation courante constitue un ensemble

de valeurs incompatibles (une contrainte mais il est possible que
des sous instanciation soient également incompatibles)
 enregistrer les incompatibilités sous forme de contraintes
(nogoods)
 limitation nécessaire : car problème fortement combinatoire
 limiter la taille des nogoods

 ceci revient à obtenir la consistance partielle pendant la recherche et

quand c ’est nécessaire

 similaire à dependency directed backtracking (voir partie SAT)

Constraint recording
X1 abc abc X2 X Y
X3
ab Les valeurs de x sont inférieurs
à celles de Y dans l ’ordre
X4 ab ab X5 lexicographique strict
 Soit l ’instanciation : X1 = b, X2 = b, X3 = a, X4 = b , X5 ?
 Ensemble conflit :
S1 = { X1=b, X2 = b, X3=a, X4 =b}
 après simplification :
S2 = {X3=a, X4 =b} car X1 et X2 ne sont pas connectés à X5
 suppression d ’un tuple de la contrainte (X3, X4)
 un ensemble de conflit minimal : S3 = {X4=b}
 On peut être amené à modifier la structure du graphe de
contraintes
Autres algorithmes
 Backjump [Nadel 89]
 Dependency directed backtraking [Stallman 77]
 Backmark [Gaching 79]
 etc.
Des questions
 Étude d ’algorithmes hybrides (filtre de puissance
variable au cours de la recherche)

 problème d ’adaptation : le filtre optimale n ’est pas le

même suivant le problème testé

 plus généralement :

choix d ’heuristique et d ’algorithme devrait s ’adapter à

l ’instance traitée
Classes polynomiales et
méthodes de décompositions

 CSP binaires

 CSP généraux
Conditions liées à la structure
 Largeur d ’un graphe de contraintes
 graphe ordonnée : ordre sur les sommets
 largeur d ’un sommet : nombre de prédécesseurs
 largeur d ’un ordre : largeur max des sommets
 largeur d ’un graphe : largeur min des ordres
X3

X4

X1 X5
X5
X3
X2
X2 X4
X1
Graphe de largeur 2
Un ordre de largeur 2
Conditions liées à la structure
 Théorème [Freuder 82]
Si le graphe de contraintes est de largeur k et le CSP est
fortement (k+1)-consistant alors le CSP est consistant et il
existe un ordre d ’instanciation glouton

 Corollaire
Si le graphe de contraintes est sans cycle et le CSP vérifie la
consistance d ’arc alors le CSP est consistant et il existe un
ordre d ’instanciation glouton
 Méthode
 filtrage par consistance d ’arc
 instanciation des variables selon un ordre de largeur 1
CSP structurés en k-arbre
 Un graphe G est un k-arbre si :
 G est le graphe complet à k sommets, ou
 G a un sommet x de degré k dont le voisinage est un graphe complet, et
le graphe obtenu en enlevant x et les arêtes qui lui sont incidentes est un
k-arbre

Un 2-arbre
 Théorème : un CSP structuré en k-arbre peut être résolu en O(n.d k+1)
Cas polynomiaux : CSP généraux
 Hypergraphes acycliques [Beeri & al 82]
 la 2-section de l ’hypergraphe est triangulée et l ’hypergraphe
est conforme (cliques max de la 2-section = arêtes de
l ’hypergraphe)
 Algorithme de [Graham 79]
on peut supprimer tous les sommets de l ’hypergraphe en
appliquant les 2 opérations :
 supprimer les sommets appartenant à une seule arête
 supprimer les arêtes incluses dans une autre arête
 Existence d ’un arbre de jointure X2 X3
c1
c1 X3
c2 X2, X4
X1 X2 X1
c2
X4 X5 X4 X5

c3 c3 X4, X5
X6 X6

Hypergraphe acyclique 2-section Arbre de jointure

Théorème de Freuder généralisé
 Théorème :

si l ’hypergraphe de contraintes est acyclique et le CSP

est inter-consistant alors le CSP est consistant et il
existe un ordre d ’instanciation glouton

 Méthode :
 filtrage par inter-consistance
 instanciation selon un arbre de jointure
Méthodes de décomposition
 Basées sur la structure du (hyper)graphe de contraintes
 Idée : se ramener à un (hyper)graphe acyclique

 3 méthodes :
 la méthode de l ’ensemble coupe-cycle
 la méthode du regroupement en arbre
 la méthode du regroupement cyclique
Methode de l ’ensemble coupe-
cycle [Dechter& Pearl 87]
 Ensemble coupe-cycle : ensemble de sommets d ’un graphe dont la
suppression rend le sous-graphe induit acyclique
 Principe : l ’instanciation d ’une variable correspond à sa suppression dans le
sous-problème résultant
 si les variables du coupe-cycle sont instanciées, le sous-problème
résultant est acyclique
 Méthode :
 déterminer un ensemble coupe-cycle E  X
 trouver une instanciation consistante des variables de E

 filtrer par consistance d ’arc le sous-problème induit par cette instanciation

 si le CSP obtenu est non vide, appliquer la méthode de résolution relative aux

arbres
 complexité : exponentielle en E
 Problèmes :
 calcul d ’un E de taille minimale est NP-difficile
 taille du coupe-cycle peut être grande
Regroupement en arbre [Dechter
& Pearl89]
 Principe : recouvrement d ’un graphe de contraintes par les arêtes d ’un
hypergraphe acyclique
 création d ’un CSP n-aire acyclique équivalent
 Méthode :
 triangulation du graphe de contraintes
 recherche des cliques maximales sur le graphe triangulé
 génération de l ’hypergraphe associé aux cliques
 obtention d ’un CSP n-aire en définissant des contraintes à partir des
arêtes de l ’hypergraphe par la résolution des cliques (sous problèmes)
 résolution du CSP n-aire acyclique (polynomial)
 Complexité: O(n |A| d|A| ) si |A| est la plus grande arête
 Problèmes :
 minimiser la taille de A est NP-difficile,
 la taille de A peut être grande
Regroupement en arbre
Regroupement cyclique
 Constations :
 ensemble coupe-cycle inefficace face aux cliques
 regroupement en arbre modifie la structure du problème

 méthode mixte:
 ensemble coupe-cycle et regroupement en arbre
 s ’adapter à la structure du problème sans la modifier
 méthode : pour un graphe de contrainte G = (X,C)
 recherche d ’un sous graphe G= (X ’, C ’) triangulé maximal
 recherche et résolution des cliques max de G ’
 obtention d ’un CSP n-aire en prenant comme contraintes les cliques
max de G ’ et les contraintes C-C ’
 résolution du CSP n-aire par la méthode de l ’ensemble coupe-cycle
avec X-X ’
Regroupement cyclique
Extensions

 CSP « standard » :
 ne suppose aucune propriété sur les domaines et les
contraintes
 ensemble complet et rigide de contraintes données a-priori

 deux types d ’extensions

Extensions
 Tenir compte des propriétés des domaines et des contraintes - dépend des
applications :
 autres méthodes de propagation
 rendre plus efficaces les algorithmes existants
 exemples :

 contraintes sur des intervalles [Davis 87]

 Contraintes sur des domaines continues (CSP continus)
 Contraintes hiérarchique (e.g. préférences i.e. contraintes forte & faible)
 contraintes d’inégalité
 contraintes fonctionnelles [David 92]
 …
 Lever les obligations de satisfaire toutes les contraintes ou de connaître a-
priori toutes les contraintes
 souvent changement d ’énoncé
 Max-CSP[Verfaillie & Scheix], Partial CSP, [Freuder & Wallace],optimisation
 CSP probabiliste [Rosenfeld 76], CSP floue [Fargier & al 92] [Schiex 92]...
 CSP dynamiques[Bessière 91] [Prosser 92] ...
CSP flou « Fuzzy CSP » (FCSP)
 A CSP flou (FCSP) est définit par :
 un ensemble de variables X={x1,...,xn},
 un ensemble de domaines D={D1, …, Dn}, fini et discret
 un ensemble de contraintes : chaque contrainte c est définit par
une fonction floue fl (c, A), qui associe un réel entre 0 et 1 pour
chaque tuple de valeurs compatible.
 La fonction floue fl associe un niveau de préférence entre 0 et 1 aux
tuples de valeurs : 0 représente le tuple le moins préféré et 1 le tuple
le plus préféré.

 Une solution pour un FCSP est une affectation de valeurs aux

variables, maximisant l ’expression min{fl(c,A)} | c une
contrainte du FCSP} pour toute les affectations A possible.
CSP probabiliste « Prob CSP »
 Un CSP probabiliste (Prob-CSP) est définit par :
 un ensemble de variables X={x1,...,xn},
 un ensemble de domaines D={D1, …, Dn} fini discret
 un ensemble de contraintes, chaque contrainte c admet une probabilité
p(c) de faire partie du CSP.
 P(c) signifie que la contrainte apparaît dans le CSP probabiliste avec
une probabilité P.
 remarque : la probabilité d ’une contrainte est indépendante des autres
contraintes.
 Une solution pour un Prob-CSP est une affectation de valeurs aux
variables de manière :
À maximiser la somme{produit{p(c)) | c une contrainte de S} | S est
un sous ensemble de l ’ensemble de contraintes satisfaite par A} pour
toutes les affectations A possible.
Weighted CSP (WCSP)
 Un WCSP est définit par :
 un ensemble de variables X={x1,...,xn},
 un ensemble de domaines D={D1, …, Dn} fini discret
 un ensemble de contraintes, chaque contrainte c est définit par
une fonction coût(c,A), affectant un réel positif pour chaque tuple
de valeurs.

 Une solution du WCSP une affectation de valeurs aux

variables maximisant la somme{w(c,A) | c est une
contrainte du FCSP} pour toutes les affectations
possible A.
Max CSP
 Un Max CSP est un CSP classique pour lequel on
cherche une affectation satisfaisant le maximum de
contraintes.

 Algorithme utilisée :
 incomplets: recherche local
 complets : branch & bound
Autres techniques de
simplifications
 Substituabilité de Voisinage :[Freuder 91]
 Définition : soient P= (X,C,D) une CSP, et a, b  Dxi , a est dite
voisinage substituable à b ssi pour tout Xj tq. (Xi,Xj)  C, l ’ensemble
des valeurs de Dxj compatible avec b sont aussi compatible avec a.

a b

 Théorème : soient P= (X,C,D) une CSP, et a, b  Dxi , a est dite

voisinage substituable à b, alors le CSP P’ obtenu en supprimant b de
Dxi est consistant ssi P est consistant
 Peut-on étendre la voisinage substituabilité ?
Conditions liées aux domaines
 Conditions liées aux domaines [Dechter 89]
 Théorème :

Si la taille maximum des domaines est k et si le CSP est

fortement (k+1) consistant alors le CSP est consistant et il

existe un ordre d’instanciation glouton

 Corollaire : Algorithme polynomiale si la taille des

domaines est 2