Imprimer tout le livreImprimer tout le livre

Problèmes de satisfaction de contraintes (CSP)

Site: Campus Numérique UABT
Cours: Intelligence Artificielle
Livre: Problèmes de satisfaction de contraintes (CSP)
Imprimé par: Visiteur anonyme
Date: jeudi 21 novembre 2024, 23:57

Table des matières

1. Exemples de CSP

La satisfaction de contraintes (Constraint Satisfaction Problem CSP)est une discipline purement algorithmique issue de la programmation logique et de l’intelligence artificielle et apparue à la fin des années 1970.
Beaucoup de problèmes algorithmiques de décision peuvent être reformulés en tant que problèmes de satisfaction de contraintes.

Exemples:




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

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






4. Résolution d'un CSP

  • La résolution de CSP est généralement combinatoire dans le sens où il faut envisager un très grand nombre de combinaisons avant d'en trouver une qui satisfasse toutes les contraintes.
  • Bien souvent, la puissance de calcul des ordinateurs ne suffit pas pour examiner toutes les combinaisons possibles en un temps acceptable, et il est nécessaire d'introduire des raisonnements et des heuristiques.

Algorithmes de résolution de CSP:

  • Recherche systématique
    • genere et teste (GET)
    • simple retour arrière (SRA) ou (backtracking (BT))
  • Techniques de filtrage
    • consistance de nœud (NC), d’arc (AC), de chemin (PC) · · ·
  • Techniques de propagation de contraintes
    • forward checking (FC)
    • look ahead (LH)
  • Techniques basées sur l’ordre des variables et des valeurs 
    • heuristiques



4.1. Approche générer et tester

  • C’est une méthode naïve de résolution de problèmes .
  • Consiste à générer et tester tous les ordres possibles.
  • Chaque combinaison de variables et de valeurs est systématiquement générée et testée pour voir si elle satisfait toutes les contraintes du problème.
  • La première combinaison satisfaisant toutes les contraintes est alors la solution du CSP.
Inconvénients:

Résoudre un problème de cette manière devient rapidement impossible lorsque la taille des problèmes augmente.


4.2. Approche simple retour arrière (backstracking)

Le retour en arrière est l'action de retourner vers une variable précédant la variable courante dans la sous-séquence d'instanciation, de modifier la valeur affectée à celle-ci et de poursuivre la résolution par la suite.

L'algorithme de BT est donc un algorithme à deux phases.
  1. Premièrement, une phase permettant d'avancer vers une prochaine variable à instancier et permettant d'étendre la sous-séquence et,
  2. Deuxièmement, une phase de retour en arrière consistant à choisir la variable vers laquelle sera fait le retour en arrière dans la sous-séquence.

Inconvénients:

  • Pas d’identification des causes de conflit
  • Redondance
  • Détection tardive des conflits