Problème de satisfaction de contrainte

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 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ésolu en un temps raisonnable.

Jean-Louis Laurière, un chercheur de Paris 6 est un des pionniers des problèmes de satisfaction de contraintes, avec en particulier le Système et language ALICE [1] [2]


Sommaire

Exemples

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

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

Définition formelle

Formellement, un problème de satisfaction de contrainte est définit 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 est 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ésolus en un temps polynomial ni NP-complet, dont l'existence fut démontrée par Ladner. Les résultats de la dichotomie sont connus pour des CSPs où le domaine de valeur est de taille 2 ou 3 mais le cas général est toujours en question.

La plupart des CSPs connus pour être facile à 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

  1. [Laurière, 1978] J.-L. Laurière, “A Language and a Program for Stating and Solving Combinatorial Problems,” Artificial intelligence, vol. 10(1), pp. 29-127, 1978.
  2. Pierre Roy (1998). Satisfaction de Contraintes et Programmation par Objets, Thèse de Doctorat, Soutenue le 21 décembre 1998

Liens externes

Ce document provient de « Probl%C3%A8me de satisfaction de contraintes ».

Wikimedia Foundation. 2010.

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

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • 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… …   Wikipédia en Français

  • Contrainte morale — Contrainte Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Contrainte religieuse — Contrainte Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   Wikipédia en Français

  • Contrainte — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom. Sur les autres projets Wikimedia : « Contrainte », sur le Wiktionnaire (dictionnaire universel) Sommaire …   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 contrainte — 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

  • Névrose de contrainte — Névrose obsessionnelle (selon la psychanalyse) La névrose obsessionnelle (ou névrose de contrainte) est une forme majeure de névrose dégagée par Sigmund Freud en 1894. Selon la doctrine psychanalytique, elle est la deuxième grande maladie… …   Wikipédia en Français

  • Obligation religieuse — Contrainte Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom …   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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”