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.

Contrainte:
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