Problmes de Satisfaction de

Contraintes
(CSP)

Dfinitions & exemples

Un CSP P = (X, D, C) est dfini par :

des variables : X = { X1, X2 Xn }

des domaines : D = { D1, D2 Dn } , Xi prend ses valeurs dans

lensemble fini discret Di

des contraintes : C = { C1, C2 Cm },

la contrainte Ci est une relation Ri dfinie sur un sous ensemble de
variables Si :
Si X , lensemble des variables sur lesquelles elle porte: S i = {Xi1, Xi2, Xini}
Ri, lensemble des combinaisons de valeurs satisfaisant Ci : Ri Di1 x Di2 x xDini

Ci = <Si, Ri>. | Si | est appele larit de Ci

Une solution est une instanciation des variables satisfaisant toutes

les contraintes.

Dfinitions & 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 darit 2 (graphes)

CSP n-aires : contraintes darit quelconque (hypergraphes)

X2

X3

C1

C2
X4

X1
C3

Dfinitions & 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>

X1
b
a
a

R1

X2
a
a
b

X3
a
b
a

C2= < S2 , R2>

X2
a
b
b

R2

X3
b
a
a

X4
a
a
b

C3= < S3 , R3>

X1
a
b
b

R3

X4
a
a
b

Dfinitions & exemples

Reprsentations des contraintes
contraintes binaires

Ck

En intension : Y = X 2 , X Y
En extension (par table) : Rk
DX
x1
x2
x3

Par graphes :

Dx
x1
x2
x3

Rk

DY
y1
y1
y2

y1

Dy
y1
y2
y3

x1
x2
x3

1
0

y2
0
0
1

y3
0

0
0

Exemple

X1

Problme des mots croiss

X1

D(X1) =
{FRITES,
COUSCOUS,
RIZ, SALADE}

L12 = L21

F
X2 R C L
I
X2
T
X3 M O U L E S
D(X2) =
S

L15 = L35
X3

{RCL, OM, PSG, LOSC, CRIL}

D(X3) =
{MOULES,
SARDINES,
CREVETTES,
VIANDE,
MAYONNAISE,
VINAIGRE}

Lij : jme lettre de Xi

Exemple 1: problme des 4Formulation standard du problme:

Placer 4 Reines sur un chiquier de
Reines
4x4 tq. deux Reines ne soit pas sur la Variables: chaque ligne est une variable.
mme ligne, colonne, ou diagonale.

Q
Q

Q
Q

Q
Q

1
X1

X2
X3
X4

Q
Q

Domaines: Di {1,2,3,4}.
Contraintes: Il y a ( 4 ) = 6 contraintes: i j , Xi Xj j i
2
Graphe de contraintes :
R12 {(1,3)(1,4)(2,4)(3,1)(4,1)(4,2)}
X1
R13 {(1,2)(1,4)(2,1)(2,3)(3,2)(3,4)(4,1)(4,3)}
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 gographique tq. Deux rgions (pays)
adjacents soient de diffrentes couleurs

(R,V,B)
X1

X2
(R,V,B)

X3
(R,V,B)

Exemple 3 :Conception
Les contraintes sur les parties du vhicule

par-chocs

blanc (white)

toit ouvrant

rouge (red)

enjoliveurs

rose (pink) ou rouge

capot et portires

carrosserie

rose, rouge ou noir (black)

blanc , rose, rouge ou noir

Les contraintes du concepteurs

pare-chocs, toit ouvrant et enjoliveurs plus clairs que la

carrosserie

portires, carrosseries et capot de la mme couleur

Trouver une configuration possible du vhicule satisfaisant

les contraintes.

Exemple 3 :Conception
portires

pare-chocs

(w,p)
(w,r)
(w,b)

(p,p)
(r,r)
(b,b)

toit ouvrant

(r,b)

enjoliveurs

p, r

(p,p)
(r,r)
(b,b)

w, p, r, b
carrosserie

(p,r)
(p,b)
(r,b)
plus clair que
de la mme couleur

p, r, b

(p,p)
(r,r)
(b,b)

p, r, b
capot

Exemple 3 : Vision [Walz:75]

Problme :
reconnatre des objets 3D
en interprtant les lignes sur un dessin 2D

Exemple 3 : Vision [Walz:75]

Sur le schma ci-dessous, il existe quatre types de
jonctions (points de rencontre entre les artes) :

Exemple 3 : Vision [Walz:75]

En suivant la flche dans cette direction lobjet est sur la droite;
sur votre gauche lespace est vide.

+
Une arte extrieure, lobjet est sur les deux cots :
artes intrieures convexes

Une arte intrieure : artes intrieures concaves

Exemple 3 : Vision [Walz:75]

On distingue les cas suivants : (seules certaines combinaisons sont
possibles pour des artes adjacentes une jonction)

L
Y

+
+
+

T
+

Flche

+
-

Exemple 3 : Vision [Walz:75]

Formalisation :
variables : les artes
domaines : les labels
jonctions : les contraintes

+
+ +
+

+ +
+

+
+

Un tiquetage consistant est une interprtation possible

CSP
Enoncs 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 problme de dcision 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 cre 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};
Dy={3,4},
Dz={5,6}

Du = {(1,4,5), (2,3,5), (2,4,6)}

Transformations CSP-naires vers

CSP binaires
1) en gardant les variables originales :
Introduire une nouvelle contrainte : X = ime argument de
(U)
{5,6}
Z
X+Y=Z, X<Y
Dx = {1,2};
Dy={3,4},
Dz={5,6}

Z= arg3(U)
U= {(X,Y,Z) & X+Y=Z}

U {1,4,5), (2,3,5), (2,4,6)}

X= arg1(U)

{1,2}

Y= arg2(U)
X<Y

{3,4}

Transformations CSP-naires vers

CSP binaires
1) Sans les variables originales :
Introduire une nouvelle contrainte :
ime arguments de(U) = jme argument de (V)
X+Y=Z, X<Y
Dx = {1,2};
Dy={3,4},
Dz={5,6}

U= {(X,Y,Z) & X+Y=Z}

Arg1(U)= arg1(V)
V= {(X,Y) & X<Y}

{1,4,5), (2,3,5), (2,4,6)}

Arg2(U)= arg2(V)

V {1,3), (1,4), (2,3), (2,4)}

Mthode standard de
rsolution : le backtrack
A chaque tape, linstanciation partielle courante est tendue en
instanciant un nouvelle variable par une valeur compatible avec
linstanciation courante :
X1

X2

Xk-1

Xk

d1

d2

dk-1

dk D k

Si aucune valeur dk Dk nest compatible, alors il y a un retour en

arrire (chronologique) sur la variable prcdente X k-1 pour essayer
une autre valeur dk-1 Dk-1
X1

X2

Xk-1

d1

d2

dk-1 Dk-1

Approche fortement combinatoire : O(dn)

Filtrages et prtraitements
Consistance (ou cohrence)
proprit lie la compatibilit entre valeurs de domaines et contraintes

Filtrage
limination dlments dont on est assur quils ne peuvent figurer
dans une solution (valeurs ou n-uplets de relations)
P = (X,D,C) P= (X, D, C)

Proprit dun filtrage

simplification du problme par rduction de lespace de recherche

dans certains cas dtection de linconsistance

Plusieurs niveaux de consistances

consistance locales ou partielles jusqu consistance globale
cot du filtrage plus ou moins lev
(obtention consistance globale rsolution du problme)

La consistance darc (AC)

Dfinition

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
x2

C23

Arc Consistant
Inconsistant

x3

La consistance darc (AC) : AC1

Filtrage par consistance darc : suppression des valeurs
qui ne vrifient pas la proprit (AC)

Lalgorithme AC1 (Macworth

1977)
Algorithme AC-1
rpter
pour chaque contrainte Ck faire
Rviser(Ck)
jusqu plus de changement
Rviser(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

Lalgorithme AC1 (Macworth

1977)
procdure Rviser((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
procdure AC-1(G)
rpter
changement faux
pour chaque arc (i,j) G faire
changement rviser((i,j)) ou changement
fin pour
jusqu non (changement)
fin AC-1

Lalgorithme AC1
Quels sont les dfaut de AC-1?

Si un domaine est rduit alors tout les arcs sont tests

(rviss) mme si le domaine touch n a aucune influence sur
la plus part des arcs

Quels sont les arcs reconsidrer ?

Les arcs affects par le filtrage du domaine

i.e., les arcs relis la variable touche (arcs entrants).

Ignorer les arcs incident de la variable touch (arcs sortants)

Variable touch

Arc dont la rvision

a provoqu la rduction
du domaine

Lalgorithme AC3 [Mackworth

1977]
utiliser une file pour mmoriser les arcs (re-)rviser
enfiler uniquement les arcs affects par la rduction des
domaines.
procedure AC-3(G)
Q {(i,j) | (i,j) arcs(G), ij}
% file pour les arcs rviser
tant que Q non vide faire
slectionner et supprimer (k,m) de Q
si rviser((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

Lalgorithme AC3 : observations

Rvision dun arc : de nombreuses paires de valeurs sont testes
Ces tests sont rpts chaque fois quun arc est rvis

a
b
c
d

a
b
c
d

a
b
c
d

X1

X2

X3

1. Quand larc <X2,X1> est rvis, la valeur a

est supprim du domaine de X2
2. le domaine de X3 doit tre explor pour
dterminer si les valeurs a,b,c et d
perdent leur support dans X2

Observation :
il nest pas ncessaire dexaminer les valeurs a, b et c de X3 (elles
admettent un autre support autre que a dans X2)

Lensemble support de a Di est lensemble {<j,b> | b Dj , (a,b) Rij}

Calcul et utilisation des

ensembles supports
L ensemble des valeurs supports par une valeur donne (si la valeur est
supprime alors ses valeurs perdent un support) et le nombre de ces
valeurs supports sont calculs.
procdure Initialiser(G)
Q {} , S {}
% initialiser les structures de donnes
pour chaque arc (Xi,Xj) arcs(G) faire
pour a Di faire
total 0
pour b Dj faire
si (a,b) Rij alors
Sj,b - l ensemble des pairs <i,a> tq.
total total + 1
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
pour une valeur a Di dans Dj
compteur[(i,j),a] total
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)
2
2
1

Sj...

a1
a2
a3

b1
b2
b3

<i,a1>,<i,a2>
<i,a1>
<i,a2>, <i,a3>

Utilisation des ensembles supports :

1. soit b3 une valeur supprime du domaine de j.
2. Pour chaque lment de Sj,b3 (i.e. <i,a2>,<i,a3>).

Dcrmenter 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)
2
1
0

Sj...

a1
a2
a3

b1
b2
b3

<i,a1>,<i,a2>
<i,a1>

Algorithme AC4 [Mohr &Henderson

1986]
procedure AC-4(G)
Q Initialiser(G)
tant que Q est non vide faire
slectionner 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
Inconvniant : complexit en espace leve

Autres algorithmes dAC

AC-5 (Hentenryck, Deville, Teng 1992)

un algorithme dAC gnrique

peut tre rduit AC-3 et AC-4

exploite la smantique 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

amliore la complexit en espace et la complexit en moyenne dAC4

AC-7 (Bessiere, Freuder, Regin 1999)

bas sur le calcul et lexploitation des supports (comme AC-4 et AC-6)

exploite la symtrie des contraintes

Arc consistance directionnelle

(DAC)
Observation : les algorithmes dAC effectuent des rvisons
rptes des arcs; le nombre total de rvisions dpends du
nombre darc mais aussi de la taille des domaines
(prsence de cycles).

Est-il possible daffaiblir AC de manire rviser chaque

arc une seule fois?

Dfinition : 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 rvis, mais uniquement dans une seule

direction

Algorithme DAC
1. Les arcs sont considrs dans une seule direction
2. Les variables sont ordonnes
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
Rviser((i,j))
fin pour
fin pour
fin

Quand et comment utiliser DAC

AC est plus gnral 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 problmes pour lesquels DAC est suffisant

Exemple: Si le graphe de contraintes du CSP forme un arbre alors

DAC est suffisant pour rsoudre le CSP sans retours arrires

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 pre

Relation entre AC et DAC

Exemple:
V ={X,Y,Z}
Dx = Dz= {1,2}, Dy = {1}
C = {XZ,Y<Z}

En utilisant lordre X,Y,Z :

pas de suppression de valeurs

XZ
{1,2}

En utilisant l ordre Z,Y,X :

une valeur est supprime du domaine de Z,
le CSP obtenue est DAC mais pas AC

{1,2}
Y<Z

Y {1}

XZ
{1,2}

{2}
Y<Z

Y {1}

Si l ordre X, Y, Z est encore utilis alors le CSP deviendra aussi AC

De Dac AC pour les CSP

structurs 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 nuds fils (1.)
chaque valeur admet un support dans le nud parent (2. ),
on obtient un CSP AC

Est-ce que AC est suffisant pour

rsoudre un CSP?
En appliquant les algorithmes AC on peut supprimer de nombreuses valeurs
incompatibles
Peut-on obtenir une solution?
Ou dterminer quune telle solution existe?
Malheureusement, la rponse est NON!

Exemple :
Le CSP est arc consistent
mais n admet aucune solution

XZ

Alors quel est le rle de AC ?

Dans certains cas on obtient une solution aprs l application de AC

{1,2}

{1,2}

XY

YZ

Y {1,2}

si on obtient un domaine vide (par AC) alors le CSP est inconsistant

Si tout les domaines ont t rduit une seul valeur (singleton) alors on obtient une solution du
CSP

Dans le cas gnral AC supprime des valeurs

rduit la taille de l espace de recherche

La consistance de chemin (PC)

Dfinition :

( 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
2

1
x2

C23

x3

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

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

x2

x3

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 = {XZ, 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 : reprsentation
matricielle
Pour supprimer des couples de valeurs
les contraintes doivent tre reprsent en extension
contraintes binaires = matrice de 0 et 1
0 - les valeurs sont incompatibles
1 - les valeurs sont compatibles

Oprations sur les contraintes :

Intersection Rij & Rij
(et bit bit)

composition Rik * Rkj Rij

(multiplication binaire de matrice)

Composition des contraintes

dun 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
procdure Rviser( (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
procdure PC-1(P= (X, D, C) )
n |X|
rpter
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 & Jgou : 96]

Inconvnients 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 rsoudre un CSP

PC ne suffit pas a rsoudre 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 inconvnients de PC (espace mmoire, 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

Dfinition : un CSP est k-consistent ssi toute instanciation consistante de

(k-1) diffrentes variables peut tre tendue une instanciation consistante
avec une variable supplmentaire (k)

CSP 4-consistant

K-consistance forte
3-consistant mais pas 2-consistant

Dfinition : un CSP P est fortement k-consistant ssi P est j-consistant pour tout
jk.

k-consistance forte k-consistance

k-consistance forte j-consistance pour toutjk

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

AC = 2-consistance forte

PC = 3-consistance forte

Ports des diffrentes

consistances
X< 3
12 3

NC
AC

PC

12

<
12

12

12

=
12

12
4-consistance

12

12
12

12

Techniques de consistance:
modifications apportes au CSP
AC

PC

4-(forte)consistance

Contrainte ternaire

k-consistance & rsolution de CSP

Pour un CSP n variable, quelle k-consistance est suffisante
pour rsoudre un CSP?

n-consistance forte pour un CSP n variables!

Un CSP P de n variable
de domaines {1n-1}
P est k-fortement consistant (k<n)
mais P est inconsistant
D(AC) est suffisant
P est un arbre

k-consistance & rsolution de CSP

Dfinition : un CSP est rsolut par un algorithme glouton (sans
retour arrire : backtrack free ) si pour un certain ordre des
variables, on peut trouver une valeur pour chaque variable
compatible avec les variables dj affectes

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

rsoudre un CSP?

k-consistance & rsolution de CSP

Quelques observations :

pour viter un retour arrire, une variable non instanci doit tre
compatible avec les variables instancis.

si au cours de la recherche de solution, toute variable non

instanci est contrainte avec au plus k variables instancis , on a
besoin de la (k+1)-consistance forte pour rsoudre le CSP (sans
backtrack)

le nombre maximum de contraintes entre une variable non

instanci et celles instancis dpend de lordre des variables.

Il est intressant de trouver l ordre minimisant k

k-consistance & rsolution 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 relis et qui le prcdent dans lordre.

Largeur du graphe ordonne est le maximum des largeurs de ses

sommets.

Largeur d un graphe est le minimum des largeurs de ces graphes

ordonns.

Largeur du graphe 1

k-consistance & rsolution de CSP

Thorme : 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 rsolu par un algorithme
glouton(sans retour arrire).

Ide de preuve :

Au plus w

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

Dfinition:

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

Dfinition : (1,k-1)-consistance est appele k-consistance inverse

On supprime les valeurs qui ne peuvent pas tre tendues de

manire 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 manire consistante aux variables directement relis V

Filtrage pour les CSP gnraux (naires)

Toutes les mthodes de filtrages se gnralisent aux CSP gnraux;
parmi elles :

la consistance darc

une gnralisation de la 2 consistance : linterconsistance

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 donnes relationnelles[Beeri & al 83]

Intrt :

condition plus forte que la consistance darc

consistance plus adapte aux CSP n-aires (hypergraphes)

Filtrage par consistance darc

gnralis
Soit P= (X, D,C)

a b X2

X = { X1, X2, X3, X4} et

D = { D1, D2, D3, D4},

C1

D1= D2= D3= D4= {a,b}

C = { C1, C2, C3},

C1= < S1 , R1>

X1
b
a
a

R1

X2
a
a
b

X3
a
b
a

X3 a b d

abc

C2
X1

X4

C3
C2= < S2 , R2>
X2
a
b
b

R2

X3
b
a
a

X4
a
a
b

C3= < S3 , R3>

X1
a
b
b

R3

X4
a
a
b

ab

Filtrage par interconsistance

Soit P= (X, D,C)

a b X2

X = { X1, X2, X3, X4} et

D = { D1, D2, D3, D4},

C1

D1= D2= D3= D4= {a,b}

C = { C1, C2, C3},

C1= < S1 , R1>

X1
b
a
a

R1

X2
a
a
b

X3
a
b
a

X3 a b d

abc

C2
X1

X4

C3
C2= < S2 , R2>
X2
a
b
b

R2

X3
b
a
a

X4
a
a
b

C3= < S3 , R3>

X1
a
b
b

R3

X4
a
a
b

ab

Filtrages : sommaire
Diminution de lespace de recherche
Cot raisonnable pour les consistances faibles (k3)
Le filtrage par k-consistance (k>=3) peut entraner une modification de la
structure du CSP

Compromis : il est souvent ncessaire de trouver le bon compromis entre

le prtraitement et la recherche effective
complexit du filtrage :

Efficacit pratique :
Bonne dans certains cas :

consistance darc : Vision [Waltz]

consistances de chemin : contraintes temporelles

Faible parfois : problmes des 8 reines

Rsolution de CSP
Algorithme de base : Backtrack
Amliorer le Backtrack :

avant la recherche
filtrages (consistance darc, 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 rtrospectives (look-back) : revenir la cause dchec

Critres dvaluation :

taille de larbre de recherche & nombre de tests de consistance

Les dfauts du backtrack

classique
Parcours inutile de certaines zones de lespace de recherche
(des valeurs trivialement incompatibles avec linstanciation courantes ne
sont pas supprimes)

Le retour arrire chronologique peut entraner des rptitions dchecs

causs par une mme raison

ab

ab

X3

Linstanciation (a,b) pour X1, X2

provoquera des checs rpts sur X3
alors que la cause relle d checs est
l incompatibilit avec X4

X4
la taille de lespace de recherche
dpend de lordre

dinstanciation choisi

X1

ab

ab

X2

Heuristiques dordonnancement
Principe du First-fail

Ordres :
vertical : choix des variables
horizontal : choix de valeurs
ordre de test des contraintes
statique : prtabli
dynamique : volue pendant la recherche

Heuristiques classiques :
choix de valeurs

recherche dune solution : choix les moins contraints

recherche de toutes les solutions : choix les plus contraints
choix de variables

en fonction de critres structurels : degr, tailles des domaines , satisfiabilit

des contraintes...

Heuristiques dordonnancement
Choix de lordre des variables - un exemple [Nadel]
C23: X2 X3
s23 = 5/6
X2

12

123

X3

C34: X3 = X4+2
s34 = 1/12
C24: X2 x X4 >1
1234
s24 = 7/8

C12:
X2
sij est
le X1
taux
de satisfiabilit
1 X1de la contrainte Cij :
s12 = 1

sij = |Rij| / |Di| x |Dj|

Trois heuristiques dordonnancement des variables :

H1 : le plus petit domaines dabord

(X1, X2, X3, X4)

H2 : la variable de degr max dabord

(X2, X3, X4, X1) ou (X2, X4, X3, X1)

H3 : contrainte la moins satisfiable dabord

(X4, X3, X2, X1) ou (X3, X4, X2, X1)

X4

Exemple : suite
H1 29 noeuds

H1
X1

X2

X3

X4

1234

1234 1234

1234 1234

H2 32 noeuds
H2
X2
X4
X3
X1

1
1

123

123

1 2 3 1 2 31 2 3
1

123 123

Exemple : suite
H3 19 noeuds
H3
X4
X3
X2
X1

123 123

123

123

1 2
1

Ncessit de compromis entre les diffrents critres

Exemples :
1. dom + degre : min dom, en cas dgalit appliquer max degre
2. dom/degre : minimiser le rapport dom/degre [Rgin & bessire]

Heuristiques: une approche multiniveaux

[Bessire-Chmeiss-Sas]

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 multiniveaux

Formulation gnral
x ( x ) W ( Rij )
W ( xi )

( xi )
j

H ( xi )

W ( xi )
( xi )

calcul deW ( Rij ) ? Peut tre coteux !!

paramtre syntaxique simple ( ):

W ( Rij ) ( xi ) ( x j )

1
H ( xi )
( ( xi )
( xi )

x j ( xi )

(x j )

( xi )

Heuristiques: une approche multiniveaux

Gnralisation : (niveaux)

H 0 ( xi ) ( xi )
1
H k ( xi )
( ( xi )
( xi )
( xi )

Instanciation de
( xi ) D ( xi )

dom
0

( xi )

( xi )

: H dom / deg

( xi )

( xi )

D ( xi )

D ( xi )

xj

( xi ) D ( xi )

H 1dom ( xi )

H
k 1 ( x j )
( x )

x j ( xi )

D( x j )

( xi )

, dom / deg
H
1

Heuristiques: une approche multiniveaux

Ordonnancement des variables

une formulation gnrale

paramtrable

rcupre la plus part des heuristiques connues

multi-niveaux (notion de distance)

calcul simple du poids des contraintes

proprits syntaxique
pas de tests de consistance

possibilit dutiliser diffrentes fonctions pour le calcul du poids

des contraintes

amlioration significative des heuristiques connues

Ordre de test des contraintes

Ordre lexicographique : 47 tests de contraintes
H2
1

X2
X4
X3
X1

X2 x X4 >1

X2 X3
X3 = X4+2

2
3

123 123

1 2 3 1 2 31 2 3

X1 X2

La contraintes la moins satisfiable dabord :

123 123

X3 = X4+2
X2 X3

31 tests

Amliorer le backtrack : emploi

de filtres
Principe :
chaque tape (1, ,k,n),

on instancie une nouvelle variable Xk

On filtre : des valeurs devenues impossibles sont limines des domaines Di pour
i>k

Si un domaine Di devient vide, il y a alors retour arrire sur la variable

prcdente

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]
Ltape 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

Xk-1

.
.

Xk

Variables dj instancies

Filtrage : limination des valeurs

incompatibles avec d

FC : schma dalgorithme
Procdure 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
Di := Di
pour tout di de Di faire
si di et dk incompatibles alors
Di := Di-{di}
fsi
fpour
fpour
si pour tout i >k, Di alors
pour tout dk+1 de Dk+1 faire
:= (d1,,dk,dk+1)
forward-Checking(D, k+1)
fpour
fsi
fsi

Real Full Lookahead (RFL) [Harlick

80]
Ltape de filtrage, quand on a instanci la k-ime
variable, correspond la suppression des valeurs des
domaines qui ne vrifient pas la consistance darc.
Appel aussi MAC (Maintaining Arc Consistency)
AC est aussi appliqu avant la recherche

Variables instancies

Backtracking

Variables non instancies

Forward Cheking

Real Full Lokahead

Comparaison sur les 4-Reines

Forward cheking
Backtraking

Real Full Lookahead

M(AC+)
[Chmeiss & Sas 2000]

Utilisation dynamique de PC ?

Cot prohibitif !

exploiter partiellement PC DPC

M(AC+) = M(AC + DPC)

Proprit :

Soit P ( X , D, C ) un CSP,
x i X ( xi ) 2 , Cij , Cik C , si ( x j , xk , xi ) vrifie 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+): schma gnral

M(AC+) : schma gnral
1. Maintenir larc consistance
2. Dconnecter singletons variable (str. arbre)
3. Maintenir la chemin consistance directionnelle
4. Dconnecter doubletons variables (str. Graphe lg. 2)
5. Choix dun couple (variable, valeur)
6. Aller 1.

Efficacit exprimentale
BT

FC

RFL

MAC

#noeuds

#tests
Compromis tablir entre filtrage et recherche

un filtre puissant entraine :

diminution en taille de lespace de recherche
mais aussi ralentissement de recherche

Retour arrire intelligent

Backjumping bas sur la structure [Dechter 90]
En cas dchec sur une variable Xk, retour sur la
variable voisine de Xk la plus rcemment instancie.

En cas d checs sur X6

X1
X2
X3
X4
X5
X6

Puis ici
Revenir d abord ici

Constraint recording

[Dechter 90]

[Bruynooghe 84]
En cas dchecs, linstanciation courante constitue un ensemble
de valeurs incompatibles (une contrainte mais il est possible que
des sous instanciation soient galement incompatibles)
enregistrer les incompatibilits sous forme de contraintes
(nogoods)

limitation ncessaire : car problme fortement combinatoire

limiter la taille des nogoods
ceci revient obtenir la consistance partielle pendant la recherche et

quand cest ncessaire

similaire dependency directed backtracking (voir partie SAT)

Constraint recording
X1

abc
X3
ab

X4

ab

abc

ab

X2

X5

Les valeurs de x sont infrieurs

celles de Y dans l ordre

strict
Soit linstanciation : X1 = b, X2 = b, X3 = a, X4lexicographique
= b , X5 ?
Ensemble conflit :
S1 = { X1=b, X2 = b, X3=a, X4 =b}
aprs simplification :
S2 = {X3=a, X4 =b} car X1 et X2 ne sont pas connects X5
suppression dun 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 dalgorithmes hybrides (filtre de puissance
variable au cours de la recherche)

problme dadaptation : le filtre optimale nest pas le

mme suivant le problme test

plus gnralement :
choix dheuristique et dalgorithme devrait sadapter
linstance traite

Classes polynomiales et
mthodes de dcompositions
CSP binaires

CSP gnraux

Conditions lies la structure

Largeur dun graphe de contraintes

graphe ordonne : ordre sur les sommets

largeur dun sommet : nombre de prdcesseurs

largeur dun ordre : largeur max des sommets

largeur dun graphe : largeur min des ordres

X3
X4
X1

X5
X3

X2

X5
X2

X4

X1

Graphe de largeur 2
Un ordre de largeur 2

Conditions lies la structure

Thorme [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 dinstanciation glouton

Corollaire
Si le graphe de contraintes est sans cycle et le CSP vrifie la
consistance darc alors le CSP est consistant et il existe un
ordre dinstanciation glouton

Mthode

filtrage par consistance darc

instanciation des variables selon un ordre de largeur 1

CSP structurs 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 artes qui lui sont incidentes est un karbre

Thorme : un CSP structur en k-arbre peut tre rsolu en O(n.d k+1)

Un 2-arbre

Cas polynomiaux : CSP gnraux

Hypergraphes acycliques [Beeri & al 82]

la 2-section de lhypergraphe est triangule et lhypergraphe

est conforme (cliques max de la 2-section = artes de
lhypergraphe)

Algorithme de [Graham 79]

on peut supprimer tous les sommets de lhypergraphe en
appliquant les 2 oprations :
supprimer les sommets appartenant une seule arte
supprimer les artes incluses dans une autre arte

Existence dun arbre de jointure

c1

X1

X2
X4

X3

c2

X5

X2

X3

X1

c2

Hypergraphe acyclique

X2, X4

X5

X4

c3

c3
X6

c1

X4, X5

X6

2-section

Arbre de jointure

Thorme de Freuder gnralis

Thorme :
si lhypergraphe de contraintes est acyclique et le CSP
est inter-consistant alors le CSP est consistant et il
existe un ordre dinstanciation glouton

Mthode :

filtrage par inter-consistance

instanciation selon un arbre de jointure

Mthodes de dcomposition
Bases sur la structure du (hyper)graphe de contraintes
Ide : se ramener un (hyper)graphe acyclique

3 mthodes :

la mthode de lensemble coupe-cycle

la mthode du regroupement en arbre

la mthode du regroupement cyclique

Methode de lensemble coupecycle [Dechter& Pearl 87]

Ensemble coupe-cycle : ensemble de sommets dun graphe dont la suppression

rend le sous-graphe induit acyclique

Principe : linstanciation dune variable correspond sa suppression dans le
sous-problme rsultant
si les variables du coupe-cycle sont instancies, le sous-problme
rsultant est acyclique

Mthode :
dterminer un ensemble coupe-cycle E X
trouver une instanciation consistante des variables de E
filtrer par consistance darc le sous-problme induit par cette instanciation
si le CSP obtenu est non vide, appliquer la mthode de rsolution relative aux
arbres
complexit : exponentielle en E

Problmes :

calcul dun E de taille minimale est NP-difficile

taille du coupe-cycle peut tre grande

Regroupement en arbre [Dechter

& Pearl89]
Principe : recouvrement dun graphe de contraintes par les artes dun
hypergraphe acyclique

cration dun CSP n-aire acyclique quivalent

Mthode :

triangulation du graphe de contraintes

recherche des cliques maximales sur le graphe triangul

gnration de lhypergraphe associ aux cliques

obtention dun CSP n-aire en dfinissant des contraintes partir des

artes de lhypergraphe par la rsolution des cliques (sous problmes)

rsolution du CSP n-aire acyclique (polynomial)

Complexit: O(n |A| d|A| ) si |A| est la plus grande arte

Problmes :
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 problme

mthode mixte:

ensemble coupe-cycle et regroupement en arbre

sadapter la structure du problme sans la modifier

mthode : pour un graphe de contrainte G = (X,C)

recherche dun sous graphe G= (X, C) triangul maximal

recherche et rsolution des cliques max de G

obtention dun CSP n-aire en prenant comme contraintes les cliques max
de G et les contraintes C-C

rsolution du CSP n-aire par la mthode de lensemble coupe-cycle avec

X-X

Regroupement cyclique

Extensions
CSP standard :

ne suppose aucune proprit sur les domaines et les

contraintes

ensemble complet et rigide de contraintes donnes a-priori

deux types dextensions

Extensions
Tenir compte des proprits des domaines et des contraintes - dpend des applications
:
autres mthodes de propagation
rendre plus efficaces les algorithmes existants
exemples :

contraintes sur des intervalles [Davis 87]

Contraintes sur des domaines continues (CSP continus)
Contraintes hirarchique (e.g. prfrences i.e. contraintes forte & faible)
contraintes dingalit
contraintes fonctionnelles [David 92]

Lever les obligations de satisfaire toutes les contraintes ou de connatre apriori toutes les contraintes
souvent changement dnonc
Max-CSP[Verfaillie

& Scheix], Partial CSP, [Freuder & Wallace],optimisation

CSP probabiliste [Rosenfeld 76], CSP floue [Fargier & al 92] [Schiex 92]...
CSP dynamiques[Bessire 91] [Prosser 92] ...

CSP flou Fuzzy CSP (FCSP)

A CSP flou (FCSP) est dfinit 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 dfinit par

une fonction floue fl (c, A), qui associe un rel entre 0 et 1 pour
chaque tuple de valeurs compatible.
La fonction floue fl associe un niveau de prfrence entre 0 et 1 aux

tuples de valeurs : 0 reprsente le tuple le moins prfr et 1 le tuple

le plus prfr.

Une solution pour un FCSP est une affectation de valeurs aux

variables, maximisant lexpression 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 dfinit 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 apparat dans le CSP probabiliste avec une

probabilit P.
remarque : la probabilit dune contrainte est indpendante des autres

contraintes.

Une solution pour un Prob-CSP est une affectation de valeurs aux

variables de manire :
maximiser la somme{produit{p(c)) | c une contrainte de S} | S est un
sous ensemble de lensemble de contraintes satisfaite par A} pour
toutes les affectations A possible.

Weighted CSP (WCSP)

Un WCSP est dfinit 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 dfinit par

une fonction cot(c,A), affectant un rel 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 utilise :

incomplets: recherche local

complets : branch & bound

Autres techniques de
simplifications
Substituabilit de Voisinage :[Freuder 91]
Dfinition : 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, lensemble
des valeurs de Dxj compatible avec b sont aussi compatible avec a.

a b
Thorme : 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 lies aux domaines

Conditions lies aux domaines [Dechter 89]

Thorme :
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 dinstanciation glouton

Corollaire : Algorithme polynomiale si la taille des

domaines est 2