Ê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
Propagation de contraintes
Résumé
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.
La propagation de contraintes consiste à modifier (i.e. réduire) le domaine des variables impliquées dans une contrainte, dans le but de rétablir la cohérence. Plusieurs types de cohérences, plus ou moins fortes peuvent être considérées.
La cohérence d'arcs est définie ainsi :
Une contrainte binaire est cohérente par arc (abrégé en AC pour arc consistent) si pour toute valeur du domaine de , il existe au moins une valeur du domaine de telle que la contrainte soit satisfaite, et vice-versa. La description symbolique de la cohérence par arc d'une contrainte est : où et désignent respectivement les domaines de et de .
La cohérence d'arcs d'un problème est satisfaite si chaque contrainte binaire est cohérente par arc.
Une généralisation de la cohérence d'arcs pour les contraintes sur plus de deux variables est décrite en termes de cohérence d'hyperarcs ou cohérence d'arcs généralisée.
Soit le CSP défini par les variables avec les contraintes suivantes :
Pour chacune des valeurs du domaine de , il existe une valeur du domaine de qui satisfait la contrainte . En effet, pour (resp. ), l'instanciation (resp. ) satisfait la contrainte . La contrainte est donc cohérente par arc. De la même façon et sont cohérentes par arc.
On s'aperçoit ainsi qu'il ne suffit pas qu'un problème soit AC pour admettre une solution.
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.
Proximité ontologique
Cours associés (2)
CS-330: Artificial intelligence
Introduction aux techniques de l'Intelligence Artificielle, complémentée par des exercices de programmation qui montrent les algorithmes et des exemples de leur application à des problèmes pratiques.
MATH-329: Continuous optimization
This course introduces students to continuous, nonlinear optimization. We study the theory of optimization with continuous variables (with full proofs), and we analyze and implement important algorith
Publications associées (80)
Personnes associées (24)
Unités associées (2)
Concepts associés (5)
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.
Constraint logic programming
Constraint logic programming is a form of constraint programming, in which logic programming is extended to include concepts from constraint satisfaction. A constraint logic program is a logic program that contains constraints in the body of clauses. An example of a clause including a constraint is . In this clause, is a constraint; A(X,Y), B(X), and C(Y) are literals as in regular logic programming. This clause states one condition under which the statement A(X,Y) holds: X+Y is greater than zero and both B(X) and C(Y) are true.
Constraint satisfaction
In artificial intelligence and operations research, constraint satisfaction is the process of finding a solution through a set of constraints that impose conditions that the variables must satisfy. A solution is therefore a set of values for the variables that satisfies all constraints—that is, a point in the feasible region. The techniques used in constraint satisfaction depend on the kind of constraints being considered.