Résolution d'un problème de satisfaction de contraintes sur les intervalles

Résolution d'un problème de satisfaction de contraintes sur les

intervalles

Mohamed Ali Souibgui
Sami Gharsalli

e-mail :dali922011@ gmail.com

12 juin 2015

1

Remerciements

Nous tenons à remercier toutes les personnes qui ont contribuéau succès de notre projet et qui nous ont aidélors de la rédaction de ce rapport.

Nos premiers remerciements sont pour notre encadrant Mr. Wady Naanaa qui nous a guidépendant l'élaboration de ce projet, sans lui la tache serait plus difficile.

Nous remercions également les membres de jurys, merci au professeur Ayeb Béchir qui nous a fait l'honneur d'être le président des jurys, et merci à Mme El Kamel Hager pour la lecture détaillée du rapport.

Enfin, nous tenons à remercier nos familles et nos amis pour leurs valeureux soutien.

2

Table des matières

1 Introduction genérale 2 Problèmes de satisfaction de contraintes					6 8
2.1		Qu'est-ce qu'une contrainte?			8
		2.1.1		Quelques caractéristiques des contraintes	8
		2.1.2		Définition d'une contrainte	9
		2.1.3		Aritéd'une contrainte	9
		2.1.4		Différents types de contraintes	9
2.2		Problèmes de satisfaction des contraintes			10
		2.2.1		Définition informelle	10
		2.2.2		Définition formelle	11
		2.2.3		Les variables du CSP	11
		2.2.4		Graphe de contraintes	12
		2.2.5		Solution d'un CSP	13
		2.2.6		Notion de CSP surcontraint ou souscontraint	14
2.3		Modélisation de quelques problèmes sous la forme d'un CSP			14
		2.3.1		Exemple 1 : Problème du zèbre	14
		2.3.2		Problème de Coloriage d'une carte	16
2.4		Quelques algorithmes de résolution de CSP			19
		2.4.1		L'algorithme »génère et teste»	19
		2.4.2		L'algorithme »simple retour-arrière»	21
		2.4.3		L'algorithme »anticipation»	23

3

	2.5 2.6	Intégration d'heuristiques Réseaux de contraintes temporelles 2.6.1 Quelques éléments sur la représentation du temps 2.6.2 Contraintes temporelles qualitatives	28 29 29 29
	2.7	Les problèmes de planification	34
		2.7.1 Contraintes de précédence	35
		2.7.2 Le graphe de contraintes temporelles	35
	2.8	Conclusion	36
3	Résolution d'un problème de satisfaction de contraintes		37
	3.1	Introduction	37
	3.2	Description du problème	37
	3.3	Exemple d'un problème	38
	3.4	Modélisation sous la forme d'un CSP	38
	3.5	Résolution du problème	38
		3.5.1 Résolution par l'algorithme génère et teste 38
		3.5.2 Résolution par l'algorithme simple retour arrière (ou backtrack)	39
		3.5.3 Résolution par l'algorithme d'anticipation	39
		3.5.4 Résolution proposée	40
	3.6	Algorithme proposé	43
		3.6.1 algorithme	43
		3.6.2 Exemple	45
	3.7	Outils d'implémentation	53
	3.8	Expérimentation	54
		3.8.1 Complexitéde l'algorithme proposé	54
		3.8.2 Satisfaction des contraintes	55
	3.9	Conclusion	57
4	Conclusion générale		58

4

Table des figures

2.1 Graphe vs hypergraphe 12

2.2 gouvernorat de Kasserine 17

2.3 Coloriage correcte du gouvernorat de Kasserine 18

2.4 Exécution de génère et teste sur un CSP simple 21

2.5 Exécution de SimpleRetourArrière (cette image est empruntée au »Guide to Constraint Pro-

gramming» de Roman Bartak) 23
2.6 Exécution d'anticipation (cette image est empruntée au »Guide to Constraint Programming»

de Roman Bartak) 27
2.7 Exécution d'anticipation 2 (cette image est empruntée au »Guide to Constraint Programming»

de Roman Bartak) 27

2.8 Les treize relations de Allen entre deux intervalles de temps X et Y 30

2.9 Relations qualitatives entre les intervalles 31

2.10 Scénario possible pour l'exemple 32

2.11 Représentation des relations qualitatives entre les points : (a) Exemple Béchir a mis le papier

vers le bas et bu le dernier de son café. (b) Un scénario possible 34

2.12 Un graphe de contraintes temporelles de précédence 36

3.1 Pourcentage des contraintes satisfaites par rapport au nombre de contraintes sur problème

impliquant 100 variables 55
3.2 Pourcentage des contraintes satisfaites par rapport au nombre de contraintes sur problème

impliquant 300 variables 56

5

3.3 Pourcentage des contraintes satisfaites par rapport au nombre de contraintes sur problème

impliquant 600 variables 56

3.4 contraintes satisfaites par rapport au nombre de variables 57

6

Chapitre 1