Problème de satisfaction de contraintes


Problème de satisfaction de contraintes

Les problèmes de satisfaction de contraintes ou CSP (Constraint Satisfaction Problem) sont des problèmes mathématiques où l'on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou de critères. Les CSP font l'objet de recherches intenses à la fois en intelligence artificielle et en recherche opérationnelle. De nombreux CSP nécessitent la combinaison d'heuristiques et de méthodes d'optimisation combinatoire pour être résolus en un temps raisonnable.

Sommaire

Exemples

Exemples de problèmes qui peuvent être modélisés par un problème de satisfaction de contraintes :

Les algorithmes utilisés pour résoudre des problèmes de satisfaction de contraintes incluent l'AC-3, le retour sur trace, et l'algorithme des conflits minimaux.

Définition formelle

Formellement, un problème de satisfaction de contraintes est défini par un triplet \langle X,D,C \rangle, où X est un ensemble de variables, D est un domaine de valeurs, et C est un ensemble de contraintes. Chaque contrainte est à son tour une paire \langle t,R \rangle, où t est un N-uplet de variables et R est un ensemble de N-uplets de valeurs; tous ces N-uplets ayant le même nombre d'éléments; ainsi R définit une relation. Une évaluation des variables est une fonction des variables vers les domaines, v:X \rightarrow D. Une telle évaluation satisfait une contrainte \langle (x_1,\ldots,x_n),R \rangle si (v(x_1),\ldots,v(x_n)) \in R. Une solution est une évaluation qui satisfait toutes les contraintes.

Aspects théoriques des CSPs

Les CSPs sont aussi étudiés en théorie de la complexité des algorithmes et en théorie des modèles finis. Une question importante est de savoir si pour chaque ensemble de relations, l'ensemble de tous les CSPs qui peuvent être représentés uniquement par des relations choisies à partir de cet ensemble est soit de classe P soit NP-complet (en présumant P ≠ NP). Si une telle dichotomie est vraie, alors les CSPs fournissent l'un des plus larges ensembles connus de NP, évitant les problèmes qui ne sont ni résolubles en un temps polynomial ni NP-complets, dont l'existence fut démontrée par Ladner. Les résultats de la dichotomie sont connus pour des CSPs où le domaine de valeurs est de taille 2 ou 3 mais le cas général est toujours en question.

La plupart des CSPs connus pour être faciles à aborder sont ceux où l'hypergraphe de contraintes a une largeur arborescente limitée (et où il n'y a aucune restriction sur l'ensemble des relations représentant les contraintes), ou alors, les contraintes ont une forme arbitraire mais il existe essentiellement des polymorphismes non-unaires de cet ensemble de relations de contrainte.

Voir aussi

Notes et références


Bibliographie


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Problème de satisfaction de contraintes de Wikipédia en français (auteurs)

Regardez d'autres dictionnaires:

  • Problème de satisfaction de contrainte — Problème de satisfaction de contraintes Les problèmes de satisfaction de contrainte ou CSP (Constraint Satisfaction Problem) sont des problèmes mathématiques où l on cherche des états ou des objets satisfaisant un certain nombre de contraintes ou …   Wikipédia en Français

  • Probleme de la couverture exacte — Problème de la couverture exacte Le problème de la couverture exacte est un problème d optimisation combinatoire NP complet qui fait partie des 21 problèmes NP complets de Karp. Sommaire 1 Énoncé 1.1 Exemple 1 1.2 Exemple 2 …   Wikipédia en Français

  • Problème de la couverture exacte — Le problème de la couverture exacte est un problème d optimisation combinatoire NP complet qui fait partie des 21 problèmes NP complets de Karp. Sommaire 1 Énoncé 1.1 Exemple 1 1.2 Exemple 2 …   Wikipédia en Français

  • Programmation par contraintes — La programmation par contraintes (PPC, ou CP pour Constraint Programming en anglais) est un paradigme de programmation apparu dans les années 1980[1],[2] permettant de résoudre des problèmes combinatoires de grandes tailles tels que les problèmes …   Wikipédia en Français

  • Propagation de contraintes — La propagation de contraintes dans le domaine de la programmation par contraintes est le fait de réduire le domaine d une contrainte afin de maintenir l ensemble de valeur possible cohérent avec les contraintes du problème. La propagation de… …   Wikipédia en Français

  • Survol de la Programmation par Contraintes — Programmation par contraintes La programmation par contraintes (PPC, ou CP pour Constraint Programming en anglais) consiste à poser un problème sous forme de relations logiques (appelées contraintes) entre plusieurs variables. Un problème formulé …   Wikipédia en Français

  • Couverture exacte — Problème de la couverture exacte Le problème de la couverture exacte est un problème d optimisation combinatoire NP complet qui fait partie des 21 problèmes NP complets de Karp. Sommaire 1 Énoncé 1.1 Exemple 1 1.2 Exemple 2 …   Wikipédia en Français

  • Intelligence artificielle — Pour les articles homonymes, voir A.I. Intelligence artificielle (film), IA. Le robot humanoïde ASIMO L intelligence artificielle est la …   Wikipédia en Français

  • I.A. — Intelligence artificielle Pour les articles homonymes, voir A.I. Intelligence artificielle (film),IA. Le robot humanoïde ASIMO …   Wikipédia en Français

  • Intelligence Artificielle — Pour les articles homonymes, voir A.I. Intelligence artificielle (film),IA. Le robot humanoïde ASIMO …   Wikipédia en Français