13
2.2.5 Solution d'un CSP
Etant donnéun CSP (X, D, C), sa
résolution consiste à affecter des valeurs aux variables, de
telle sorte que toutes les contraintes soient satisfaites. On introduit pour
cela les notations et définitions suivantes :
· On appelle affectation le
fait d'instancier certaines variables par des valeurs (évidemment prises
dans les domaines des variables). On notera A = {
(X1,V1), (X2,V2), ...,
(Xr, Vr)} l'affectation qui instancie
la variable X1 par la valeur V1, la variable X2 par
la valeur V2, ..., et la variable Xr par la valeur
Vr. Par exemple, sur le CSP précédent (voir
l'exemple dans 2.2.2 ), A = {(b, 0), (c, 1)} est
l'affectation qui instancie b à 0 et c à 1.
· Une affectation est dite totale
si elle instancie toutes les variables du
problème, elle est dite partielle si elle n'en
instancie qu'une partie.
Dans notre exemple, A1= {(a, 1), (b, 0), (c, 0),
(d, 0)} est une affectation totale, A2= {(a, 0), (b, 0)}
est une affectation partielle.
· Une affectation A viole une
contrainte Ck si toutes les variables de Ck sont
instanciées dans A, et si la relation définie par Ck
n'est pas vérifiée pour les valeurs des variables de Ck
définies dans A. Dans notre exemple, l'affectation
partielle A2= {(a,0), (b,0)} viole la contrainte a6=b,
en revanche, elle ne viole pas les deux autres contraintes dans la mesure
oùcertaines de leurs variables ne sont pas instanciées dans
A2 .
· Une affectation (totale ou partielle) est
consistante si elle ne viole aucune
contrainte, et inconsistante si elle viole
une ou plusieurs contraintes.
Dans notre exemple, l'affectation partielle {(c,
0), (d, 1)} est consistante, tandis que l'affectation partielle
(a, 0), (b, 0) est inconsistante.
· Une solution est une
affectation totale consistante, c'est-à-dire une valuation de toutes les
variables du problème qui ne viole aucune contrainte.
Dans notre exemple, A = {(a, 0), (b, 1), (c, 0),
(d, 1)} est une affectation totale consistante : c'est une solution.
14
2.2.6 Notion de CSP surcontraint ou souscontraint
Lorsqu'un CSP n'a pas de solution, on dit qu'il est
surcontraint : il y a trop de contraintes et
on ne peut pas toutes les satisfaire. Dans ce cas, on peut souhaiter trouver
l'affectation totale qui viole le moins de contraintes possibles. Un tel CSP
est appelémax-CSP (max car on cherche à maximiser le nombre de
contraintes satisfaites).
Une autre possibilitéest d'affecter un poids à
chaque contrainte (une valeur proportionnelle à l'importance de cette
contrainte, et de chercher l'affectation totale qui minimise la somme des poids
des contraintes violées. Un tel CSP est appeléCSP
valué(VCSP).
Il existe encore d'autre types de CSPs, appelés CSPs
basés sur les semi-anneaux (semiring based CSPs), permettant de
définir plus finement des préférences entre les
contraintes.
Inversement, lorsqu'un CSP admet beaucoup de solutions
différentes, on dit qu'il est sous-contraint.
Si les différentes solutions ne sont pas toutes
équivalentes, dans le sens oùcertaines sont mieux que d'autres,
on peut exprimer des préférences entre les différentes
solutions. Pour cela, on ajoute une fonction qui associe une valeur
numérique à chaque solution, valeur dépendante de la
qualitéde cette solution. L'objectif est alors de trouver la solution du
CSP qui maximise cette fonction. Un tel CSP est appeléCSOP (Constraint
Satisfaction Optimisation Problem) [2].
2.3 Modélisation de quelques problèmes sous la
forme d'un CSP
Modéliser un problème en termes CSP, c'est
identifier les variables, fixer leurs domaines de valeur et
définir les contraintes à satisfaire.
Généralement, une modélisation CSP très aboutie du
problème mène àune meilleure résolution,
c'est -à-dire, à une solution ayant le meilleur cout en termes de
temps et de mémoire.
| 
