Fichier PDF

Partage, hébergement, conversion et archivage facile de documents au format PDF

Partager un fichier Mes fichiers Convertir un fichier Boite à outils PDF Recherche PDF Aide Contact



TD2 .pdf


Nom original: TD2.pdf
Auteur: isli

Ce document au format PDF 1.5 a été généré par Microsoft® Office Word 2007, et a été envoyé sur fichier-pdf.fr le 03/05/2011 à 18:06, depuis l'adresse IP 41.104.x.x. La présente page de téléchargement du fichier a été vue 1085 fois.
Taille du document: 338 Ko (2 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Université des Sciences et de la Technologie Houari Boumediène
Faculté d’Electronique et d’Informatique
Département d’Informatique
LMD Master 2 ‘’Systèmes Informatiques Intelligents’’ 2010/2011
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}
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


TD2.pdf - page 1/2
TD2.pdf - page 2/2

Documents similaires


Fichier PDF td2 1
Fichier PDF tp info
Fichier PDF examen de rattrapage
Fichier PDF exercices pascal fenni 2014
Fichier PDF conception de base de algorithme
Fichier PDF 19221855 exercices corriges dalgorithmique


Sur le même sujet..