Chapitre 3
Résolution d'un problème de
satisfaction de contraintes
3.1 Introduction
Après avoir défini les problèmes de
satisfaction de contraintes et les algorithmes utilisés pour les
résoudre, nous proposons une modélisation par CSP d'un
problème particulier qui présente des points communs avec les
CSPs issus de l'algèbre des points, mais qui est plus complexe. Puis
nous présentons un algorithme pour le résoudre. Ensuite, nous
exposons une évaluation expérimentale de l'algorithme
proposé.
3.2 Description du problème
Le problème que nous nous proposons de résoudre
est un problème de satisfaction de contraintes impliquant un ensemble de
variables X={x1,x2,.....,xn},
chacune pouvant prendre une valeur distincte parmi les entiers naturels de 1
à n. Les contraintes du problème ont toutes la forme
suivante :
Min(xi1,xi2) <
Max(xi3,xi4), i1,i2,i3,i4?
{1..n} (3.1)
Il s'agit donc de trouver une permutation des nombres de 1
à n qui satisfait un ensemble de contraintes du type
donnée par l'Equation (3.1). Une permutation est consistante si elle ne
viole aucune contrainte, et inconsistante si elle viole une ou plusieurs
contraintes. Nous nous intéressons à trouver, en un temps
raisonnable, une solution qui satisfait le plus grand nombre possible de
contraintes.
38
3.3 Exemple d'un problème
Donner un ensemble de 10 nombres naturels distincts non
négatifs, supérieurs à zéro et inferieurs ou
égale à 10 sous la forme X={x1,x2,.....,x10}, qui
vérifient les 20 contraintes suivantes :
1. Min(x8,x5)<Max(x1,x10) 2. Min(x6,x2)<Max(x8,x2) 3.
Min(x2,x7)<Max(x9,x6)
4. Min(x7,x2)<Max(x9,x10) 5. Min(x8,x10)<Max(x6,x5) 6.
Min(x4,x2)<Max(x10,x9)
7. Min(x1,x6)<Max(x3,x9) 8. Min(x1,x3)<Max(x5,x9) 9.
Min(x3,x1)<Max(x2,x1)
10. Min(x7,x2)<Max(x4,x9) 11. Min(x4,x5)<Max(x5,x7) 12.
Min(x10,x7)<Max(x4,x8)
13. Min(x9,x3)<Max(x10,x2) 14. Min(x6,x10)<Max(x9,x5) 15.
Min(x8,x7)<Max(x4,x7)
16. Min(x6,x5)<Max(x3,x1) 17. Min(x8,x4)<Max(x8,x3) 18.
Min(x1,x2)<Max(x7,x6)
19. Min(x6,x5)<Max(x2,x3) 20. Min(x1,x2)<Max(x5,x7)
3.4 Modélisation sous la forme d'un
CSP
Modéliser le problème en terme CSP c'est de
déterminer le triplet (X,D,C) associé, nous proposons la
modélisation comme suit .
*Les variables et leurs domaines : On a n
variables distincts qui peuvent prendre les valeurs de 1 à n, donc :
- X={x1, x2,..., xn} l'ensemble des n variables du
problème.
- D (x1)=D(x2)= ...=D(xn) ={1..n} le domaine de
valeurs associés aux variables.
*Les contraintes : On va se limiter à
un seul type de contrainte dans ce problème, qui est : C={C1, C2,...,
Cm} tel que pour chaque Ci E C, Ci
=Min(xi1,xi2)<Max(xi3,xi4), tel que i1, i2, i3, i4 E {1..n}
| 
