Problèmes de satisfaction de contraintes (CSP)
2. Définition d'un CSP
Ensemble des problèmes, définis par
des contraintes, et consistant à chercher une solution les respectant.
Un
CSP
P = (X, D, C) est
défini par :
- des variables : X = { X1, X2 … Xn }
- des domaines : D = { D1, D2 … Dn } , Xi prend ses valeurs dans l ’ensemble fini discret Di
- des contraintes : C = { C1, C2 … Cm },
la
contrainte Ci est
une relation Ri définie
sur un sous ensemble de variables.
Une contrainte est une relation
logique établie entre différentes variables, chacune prenant sa valeur dans un
ensemble qui lui est propre, appelé domaine.
Une contrainte est déclarative et
relationnelle puisqu’elle définit une relation entre les variables sans
spécifier de procédure opérationnelle pour assurer cette relation.
L'ordre
dans lequel sont posées les contraintes n'est pas significatif : la seule chose importante à
la fin est que toutes les contraintes soient satisfaites