Problèmes de satisfaction de contraintes (CSP)

3. Modélisation d'un CSP

  • Identifier les variables : les inconnues
  • Identifier les domaines de valeur de ces variables
  • Identifier les contraintes

Il faut savoir qu'un même problème peut généralement être modélisé par différents CSP.
    • Efficacité : taille de l’espace de recherche de solutions
On va prendre l'exemple de coloriage des nœuds d’un graphe.
•Quelle est le nombre minimal de couleur tel que deux nœuds adjacents reçoivent des couleurs différentes?




 Il y a 6 nœuds, donc un maximum de 6 couleurs: 


•Etape 1 :  Identifier les variables

  Donner à chaque nœud un nom : A, B, C, D, E, F.

•Etape 2 : Identifier les domaines

  Initialement tous les nœuds peuvent être {rouge, bleu, vert, jaune, bleu ciel, violet}

•Etape 3 : Identifier les contraintes

  Déclarer que deux nœuds adjacents ne peuvent prendre la même couleur