USTHB – FEI - Département d’Informatique
LMD Master 2 ‘‘Systèmes Informatiques Intelligents’’ 2016/2017
Module ‘‘Programmation Par Contraintes’’
Travaux Dirigés
Série numéro 2 : Résolution d’un CSP
Exercice 1
a) Donner une représentation graphique du CSP P=(X,D,C) suivant :
X = {X1,X2,X3,X4,X5}
D(X1)={1,2,5,7}
D(X2)={2,3,8,12}
D(X3)={5,6,7,8}
D(X4)={1,2,3,4,5}
D(X5)={1,2,3,4,5,6,7}
C = {c1,c2,c3,c4,c5,c6,c7,c8} avec
o c1 : X1=X4
o c2 : X5≤X4
o c3 : X2 ≥X3
o c4 : X2≠X5
o c5 : X1<X3
o c6 : X3>X4
o c7 : 3*X5≥X3
o c8 : 2*X5=X3
b) En utilisant la procédure de propagation incrémentale de contraintes dans l'ordre croissant des
indices des contraintes (c1, c2, …), rendre ce CSP consistant d’arc (arc-consistant). A chaque
étape de cette procédure donner la liste des valeurs supprimées, les contraintes à reposer.
Exercice 2
Calculer la complexité du pire cas de l’algorithme de consistance d’arc AC3.
Exercice 3
Soit le CSP binaire discret à variables entières P=(X,D,C) suivant :
X = {X1,X2,X3,X4,X5,X6}
D(X1)={ 0,1,2,3,9,10,11,12}
D(X2)= {-2,-1}
D(X3)={ 5,6,7}
D(X4) ={-11,-10,-9,-2,-1,0}
D(X5)={0,1,2,3}
D(X6)={0,1,2}
Page 1 sur 2
C = {c1, c2, c3, c4, c5, c6, c7, c8} avec
o c1 : X1 = 2*X4+3
o c2 : X6 = X1-2
o c3 : X5 > X2
o c4 : X4+2 ≥ X6
o c5 : X3 = X5+4
o c6 : X2 < X6
1) Donner une représentation graphique du CSP
2) Rendre le CSP arc-consistant. Donner les domaines arc-consistants obtenus
3) En partant des domaines rendus arc-consistants, trouver, si c'est possible, une solution de ce
CSP par l’algorithme SRA dans l'ordre d'instanciation X1, X2, X3, X4, X5, X6
Instancier les variables avec les valeurs choisies dans l'ordre croissant
Donner l'arbre de recherche de solution de l'algorithme sur ce problème
4) Même question en utilisant l'algorithme du forward-checking FC avec un ordonnancement
dynamique des variables construit en choisissant à chaque étape la variable Xi pour laquelle le
quotient cardinalité(domaine( Xi))/cardinalité(contraintes( Xi)) est le plus petit
5) Même question en utilisant l'algorithme Look_Ahead
Page 2 sur 2
