Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Problème de satisfaction de contraintes
Résumé
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. Ils sont notamment au cœur de la programmation par contraintes, un domaine fournissant des langages de modélisation de problèmes et des outils informatiques les résolvant.
Formellement, un problème de satisfaction de contraintes est défini par un triplet , où est un ensemble de variables, est un ensemble de domaines de valeurs tels qu'un de ses éléments soit le domaine d'une variable de , et est un ensemble de contraintes. Chaque contrainte est à son tour une paire , où est un N-uplet de variables et est un ensemble de N-uplets de valeurs ; tous ces N-uplets ayant le même nombre d'éléments ; ainsi définit une relation. Une évaluation des variables est une fonction des variables vers les domaines, . Une telle évaluation satisfait une contrainte si . Une solution est une évaluation qui satisfait toutes les contraintes.
Les CSP 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 CSP 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 CSP 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 le théorème de Ladner. La dichotomie est connue pour des CSP où le domaine de valeurs est de taille 2 ou 3.
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.
Publications associées (36)
Personnes associées (14)
Unités associées (1)
Concepts associés (21)
Retour sur trace
En informatique, plus précisément en algorithmique, le retour sur trace ou retour arrière (appelé aussi backtracking en anglais) est une famille d'algorithmes pour trouver des solutions à des problèmes algorithmiques, notamment de satisfaction de contraintes. Contrairement à une recherche exhaustive, un algorithme de retour sur trace construit incrémentalement des solutions candidates. Il abandonne la construction lorsqu'il ne peut compléter le candidat courant en solution valide.
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 variable afin de maintenir l'ensemble des valeurs possibles cohérent avec les contraintes du problème. La propagation de contraintes permet ainsi de résoudre un problème si la propagation permet d'établir la cohérence du problème. Les techniques de propagation de contraintes sont utilisées pour réduire la taille de l'espace de recherche lors de la résolution d'un problème de satisfaction de contraintes par un algorithme de recherche arborescente.
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.
Cours associés (49)
ME-104: Introduction to structural mechanics
The student will acquire the basis for the analysis of static structures and deformation of simple structural elements. The focus is given to problem-solving skills in the context of engineering desig
PHYS-202: Analytical mechanics (for SPH)
Présentation des méthodes de la mécanique analytique (équations de Lagrange et de Hamilton) et introduction aux notions de modes normaux et de stabilité.
PHYS-101(g): General physics : mechanics
Le but du cours de physique générale est de donner à l'étudiant les notions de base nécessaires à la compréhension des phénomènes physiques. L'objectif est atteint lorsque l'étudiant est capable de pr
Séances de cours associées (387)
Propagation de l'enquête: Méthode de la cavité
Explore l'algorithme de propagation de l'enquête et son application pour résoudre les problèmes de satisfaction des contraintes.
Optimisation avec contraintes: Algorithme de point d'intérieur
Explore l'optimisation avec des contraintes en utilisant les conditions KKT et l'algorithme de point intérieur sur deux exemples de programmation quadratique.
Optimisation avec contraintes : conditions KKT
Couvre les conditions KKT pour l'optimisation avec des contraintes, essentielles pour résoudre efficacement les problèmes d'optimisation.
MOOCs associés (2)
L'Art des Structures I - Câbles et arcs
L'art des structures propose une découverte du fonctionnement des structures porteuses, telles que les bâtiments, les toitures ou les ponts. Ce cours présente les principes du dimensionnement et les s
L'Art des Structures II - Structures en treillis, poutres et cadres
Les structures en treillis, en poutre, en dalles et en cadre sont essentielles pour une grande partie des constructions modernes : immeubles pour l'habitation ou de bureaux, halles et usines, ponts, o