Problèmes CSP
• Définition
• Problème de N reines
• Problème de Zèbre
• Problème de sac à dos
• Résolution
Problèmes CSP
DÉFINITION
Problèmes CSP
3
Définition
Les problèmes de satisfaction de contraintes ou CSP (Constraint
Satisfaction Problem) sont des problèmes mathématiques où l'on cherche
des états ou des objets satisfaisant un certain nombre de contraintes ou de
critères.
Les CSP font l'objet de recherches intenses à la fois en intelligence
artificielle et en recherche opérationnelle.
De nombreux CSP nécessitent la combinaison d'heuristiques et de
méthodes d'optimisation combinatoire pour être résolus en un temps
raisonnable.
Ils sont notamment au cœur de la programmation par contraintes.
Dr. Youssef Elmir (
[email protected])
Problèmes CSP
4
Définition formelle
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: Si = {Xi1, Xi2, … Xini}
Ri, l ’ensemble des combinaisons de valeurs satisfaisant Ci : Ri Di1 x Di2 x… x Dini
Ci = <Si, Ri>. |Si| est appelée l arité de Ci
Une solution est une instanciation des variables satisfaisant toutes les
contraintes.
Dr. Youssef Elmir ([email protected])
Problèmes CSP
5
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
Dr. Youssef Elmir ([email protected])
Problèmes CSP
6
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
Problèmes CSP
7
Représentations des contraintes
contraintes binaires
X Y
Ck
En intension : Y = X 2, XY
Rk Rk
En extension (par table) :
DX DY y1 y2 y3
x1 y1
x1 1 0 0
x2 y1
x3 y2 x2 1 0 0
0 0
x3 1
Dx Dy
x1 y1
Par graphes :
x2 y2
x3 y3
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 Q
X4
• Domaines: Di {1,2,3,4}.
• Contraintes: Il y a 6 contraintes: i j , Xi Xj j i
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)}
Dr. Youssef Elmir ([email protected]) 8
Exemple 2: problème du Zèbre
On s'intéresse au problème suivant, posé initialement par Lewis Caroll :
Cinq maisons consécutives, de couleurs différentes, sont habitées par des hommes
de différentes nationalités. Chacun possède un animal différent, a une boisson
préférée différente et fume des cigarettes différentes. De plus, on sait que :
1. Le norvégien habite la première maison,
2. La maison à coté de celle du norvégien est bleue,
3. L'habitant de la troisième maison boit du lait,
4. L'anglais habite la maison rouge,
5. L'habitant de la maison verte boit du café,
6. L'habitant de la maison jaune fume des kools,
7. La maison blanche se trouve juste après la verte,
8. L'espagnol a un chien,
9. L'ukrainien boit du thé,
10. Le japonais fume des cravens,
11. Le fumeur de old golds a un escargot,
12. Le fumeur de gitanes boit de la tisane,
13. Le voisin du fumeur de Chesterfields a un renard,
14. Le voisin du fumeur de kools a un cheval.
Qui boit de l'eau ? A qui appartient le zèbre ?
Dr. Youssef Elmir (
[email protected]) 9
Exemple 2: problème du Zèbre
On définit le CSP (X,D,C) tel que
Variables du problème:
on associe une variable par attribut (couleur, animal, boisson, nationalité, cigarette)
X = {blanche, rouge, verte, jaune, bleue, norvégien, anglais, ukrainien, japonais,
espagnol, cheval, renard, zèbre, escargot, chien, thé, eau, lait, café, tisane, kools,
chesterfields, old_golds, cravens, gitanes}
Exemple 2: problème du Zèbre
On définit le CSP (X,D,C) tel que
Domaines des variables:
D(Xi) = {1,2,3,4,5}, pour toute variable Xi de X
Exemple 2: problème du Zèbre
On définit le CSP (X,D,C) tel que
Contraintes:
On pose tout d'abord une contrainte pour chaque assertion de l'énoncé
:
norvégien = 1,
bleue = norvégien + 1,
lait = 3,
anglais = rouge,
verte = café,
jaune = kools,
blanche = verte + 1,
espagnol = chien,
ukrainien = thé,
japonais = cravens,
old_golds = escargot,
gitanes = tisane,
(chesterfields = renard + 1) ou (chesterfields = renard - 1),
(kools = cheval + 1) ou (kools = cheval - 1)
Dr. Youssef Elmir ([email protected]) 12
Exemple 2: problème du Zèbre
On définit le CSP (X,D,C) tel que
Contraintes:
De plus, toutes les variables de même "type" doivent avoir des valeurs
différentes (il ne peut pas y avoir plusieurs maisons qui ont la même
couleur, ou un même animal, ...)
blanche ≠ rouge ≠ verte ≠ jaune ≠ bleue,
thé ≠ eau ≠ lait ≠ café ≠ tisane,
norvégien ≠ anglais ≠ ukrainien ≠ japonais ≠ espagnol,
cheval ≠ renard ≠ zèbre ≠ escargot ≠ chien,
kools ≠ chesterfields ≠ old_golds ≠ cravens ≠ gitanes
Exemple 3: problème du sac à dos
Il y a un sac à dos de taille M et il y a N articles de taille Si et de coût Ci donnés.
Choisissez les articles à placer dans le sac à dos pour maximiser le coût des articles
dans le sac à dos.
• sac à dos de la taille M
• articles de taille S1, . . . , SN et coût C1, . . . , CN
Exemple 3: problème du sac à dos
Il y a un sac à dos de taille M et il y a N articles de taille Si et de coût Ci donnés.
Choisissez les articles à placer dans le sac à dos pour maximiser le coût des articles
dans le sac à dos.
• sac à dos de la taille M
• articles de taille S1, . . . , SN et coût C1, . . . , CN
• Variables : X1, . . . , XN
• Domaines : domaine([X1, . . . , XN],0,1)
Exemple 3: problème du sac à dos
Il y a un sac à dos de taille M et il y a N articles de taille Si et de coût Ci donnés.
Choisissez les articles à placer dans le sac à dos pour maximiser le coût des articles
dans le sac à dos.
• sac à dos de la taille M
• articles de taille S1, . . . , SN et coût C1, . . . , CN
• Variables : X1, . . . , XN
• Domaines : domaine([X1, . . . , XN],0,1)
• Contrainte:
• produit_scalaire([S1, . . . , SN], [X1, . . . , XN], #=< , M)
Exemple 3: problème du sac à dos
Il y a un sac à dos de taille M et il y a N articles de taille Si et de coût Ci donnés.
Choisissez les articles à placer dans le sac à dos pour maximiser le coût des articles
dans le sac à dos.
• sac à dos de la taille M
• articles de taille S1, . . . , SN et coût C1, . . . , CN
• Variables : X1, . . . , XN
• Domaines : domaine([X1, . . . , XN],0,1)
• Contrainte:
• produit_scalaire([S1, . . . , SN], [X1, . . . , XN], #=< , M)
• Fonction objectif :
• produit_scalaire([C1, . . . , CN], [X1, . . . , XN], #= , F)
• Objectif : maximiser(F)
Problèmes CSP
18
Autres exemples
Problème de voyageur de commerce (pplus court chemin)
Théorème des quatre couleurs,
Le jeu de sudoku,
La satisfiabilité booléenne,
…
Problèmes CSP
19
Résolution
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
Dr. Youssef Elmir (
[email protected])
Problèmes CSP
20
Résolution
les algorithme de propagation de contraintes,
le retour sur trace (et son évolution non chronologique),
l’apprentissage de contraintes
l'algorithme des conflits minimaux
Problèmes CSP
21
• 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
Problèmes CSP
22
• 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
Dr. Youssef Elmir (
[email protected])
Problèmes CSP
23
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é
Dr. Youssef Elmir (
[email protected])
Problèmes CSP
24
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
Dr. Youssef Elmir ([email protected])
Problèmes CSP
25
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
Comparaison sur les 4-Reines
26
Backtraking Heuristique
