WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

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


par Gharsalli Sami Souibgui Mohamed Ali
Université de Monastir - Licence fondamentale en informatique  2015
  

sommaire suivant

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

sommaire suivant