Ê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 Graph Search.
Concept
Programmation par contraintes
Résumé
La programmation par contraintes (PPC, ou CP pour constraint programming en anglais) est un paradigme de programmation apparu dans les années 1970 et 1980 permettant de résoudre des problèmes combinatoires de grande taille tels que les problèmes de planification et d'ordonnancement. En programmation par contraintes, on sépare la partie modélisation à l'aide de problèmes de satisfaction de contraintes (ou CSP pour Constraint Satisfaction Problem), de la partie résolution dont la particularité réside dans l'utilisation active des contraintes du problème pour réduire la taille de l'espace des solutions à parcourir (on parle de propagation de contraintes).
Dans le cadre de la programmation par contraintes, les problèmes sont modélisés à l'aide de variables de décision et de contraintes, où une contrainte est une relation entre une ou plusieurs variables qui limite les valeurs que peuvent prendre simultanément chacune des variables liées par la contrainte. Les algorithmes de recherche de solution, en PPC, s'appuient généralement sur la propagation de contraintes, pour réduire le nombre de solutions candidates à explorer, ainsi que sur une recherche systématique parmi les différentes affectations possibles de chacune des variables. De tels algorithmes garantissent de trouver une solution, quand elle existe, et permettent de prouver qu'il n'existe pas de solution à un problème s'ils n'ont pas trouvé de solution à la fin de la recherche exhaustive.
Un des premiers solveur de contraintes est ALICE écrit en 1976 par Jean-Louis Laurière.
Problème de satisfaction de contraintes
Une contrainte est une relation entre plusieurs variables qui limitent l'ensemble des valeurs que peuvent prendre ces variables simultanément.
Lorsque l'on définit une contrainte en énumérant l'ensemble des valeurs qui satisfont cette contrainte, on dit que la contrainte est définie en extension. On trouve aussi d'autres représentations de contraintes telles que:
contraintes arithmétiques () sur des expressions ;
contraintes logiques (disjonction, implication, etc.
Source officielle
À 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.