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: | lundi 20 mai 2024, 07:49 |
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.
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
•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:
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.
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.
- Premièrement, une phase permettant d'avancer vers une prochaine variable à instancier et permettant d'étendre la sous-séquence et,
- 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
