2.2 Problèmes de satisfaction des contraintes
2.2.1 Définition informelle
Les problèmes de satisfaction des contraintes
appartiennent à la catégorie des problèmes combinatoires
et constituent un cadre simple pour représenter et résoudre de
nombreux problèmes d'intelligence artificielle,
11
et de recherche opérationnelle. De manière
informelle, un CSP est définie par la question de l'existence d'un
assignement d'un ensemble de variables dont les valeurs sont contraintes par
des relations.
2.2.2 Définition formelle
Un CSP (Problème de Satisfaction de Contraintes) est
défini par un triplé(X, D, C) tel que
1. X = {X1, X2, ...,
Xn} est l'ensemble de variables (les inconnues) du
problème.
2. D est la fonction qui associe à chaque
variable Xi son domaine D(Xi), c'est-à-dire
l'ensemble des valeurs que peut prendre Xi.
3. C = {C1, C2, ...,
Ck} est l'ensemble des contraintes. Chaque contrainte
Cj est une relation entre certaines variables de X,
restreignant les valeurs que peuvent prendre simultanément ces variables
[2].
Par exemple, on peut définir le CSP (X, D, C)
suivant :
· X = {a,b,c,d}
· D(a) = D(b) = D(c) = D(d) = {0, 1}
· C = {a =6 b,c =6 d,a + c <b}
Ce CSP comporte 4 variables a, b, c et d,
chacune pouvant prendre deux valeurs (0 ou 1). Ces variables doivent
respecter les contraintes suivantes : a doit être
différente de b, c doit être différente de d
et la somme de a et c doit être inférieure
à b.
2.2.3 Les variables du CSP
Les variables d'un CSP sont généralement les
inconnues du problème dont on cherche à associer des valeurs.
Dans ce qui suit, nous étudierons exclusivement les CSPs à
domaines finis, ou chaque domaine de valeurs est un ensemble isomorphe à
une partie finis de l'ensemble des entiers naturelles N. Un domaine de valeur
peut se représenter comme un ensemble d'entier naturels
représentables en machines, des valeurs booléennes (faux , vrai
ou 0,1), des couleurs (Rouge , Vert , Bleu, Noir . . .), des jours de la
semaine (lundi, mardi, ..., dimanche), un ensemble fini de nombres (92, 82.8,
39.7, 94.252, . . .), etc...
12
2.2.4 Graphe de contraintes
On peut associer à un CSP un graphe ou un hypergraphe
de contrainte. Les CSP binaires (dont toutes les contraintes ont une
aritéinferieur ou égale à 2) sont
représentés par des graphes dont les sommets représentent
les variables et les arêtes représentent les contraintes, et pour
les CSP quelconques (non binaire), les arêtes sont remplacées par
des hyper-arêtes qui relient des sous-ensembles de variable
impliquées dans une même contrainte. Dans ce cas, on parle d'un
hyper graphe de contraintes. La Figure suivante montre la différence
entre un graphe et un hypergraphe de contraintes (Figure 2.1).
Graphe de contraintes
|
VS
|
Hypergraphe de contraintes
|
deux sommets par
arête
|
|
plusieurs sommets par
hyper-arête
|
V6 ? > V5
V4
?
V1
V3
V2
|
|
|
V = { V1, V2, V3, V4, V5}
E = {e1,e2,e3,e4,e5}
= {{V1, V5}, {V2, V5},
{V3, V4},{V4, V5}, {V4, V6}
tel que :
V1 ? V5
V2 < V5
V3 > V4
V4 > V5
V4 ? V6 }
|
|
V = { V1, V2, V3, V4, V5, V6, V7} E = {e1,e2,e3,e4}
= {{V1, V2, V3}, {V2, V3}, {V3, V5, V6}, {V4} tel que :
V1 < ( V2 / V3 )
V2 > V3
V3 +V5 = V6
V4 > 0
}
|
|
FIGURE 2.1 - Graphe vs hypergraphe
|
|
