Worldlex Wiki
Article de reference

Programmation par contraintes

La programmation par contraintes (PC) est un paradigme de résolution de problèmes combinatoires qui s'appuie sur un large éventail de techniques issues de l'intelligence artific...

Worldlex WikiContenu en francaisLecture gratuite
combinatoires qui s'appuie sur un large éventail de techniques issues de l'intelligence artificielle , de l'informatique et de la recherche opérationnelle . En PC, les utilisateurs énoncent de manière déclarative les contraintes sur les solutions admissibles pour un ensemble de variables de décision. Les contraintes diffèrent des primitives classiques des langages de programmation impératifs en ce qu'elles ne spécifient pas une étape ou une séquence d'étapes à exécuter, mais plutôt les propriétés d'une solution à trouver. Outre les contraintes, les utilisateurs doivent également spécifier une méthode pour les résoudre. Celle-ci s'appuie généralement sur des méthodes standard telles que le retour arrière chronologique et la propagation des contraintes , mais peut également utiliser du code personnalisé, comme une heuristique de branchement spécifique au problème .

La programmation par contraintes trouve son origine dans la programmation logique par contraintes , sous laquelle elle peut être exprimée. Cette dernière intègre des contraintes dans un programme logique . Cette variante de la programmation logique est due à Jaffar et Lassez , qui ont étendu en 1987 une classe spécifique de contraintes introduite dans Prolog II . Les premières implémentations de la programmation logique par contraintes furent Prolog III , CLP(R) et CHIP .

Au lieu de la programmation logique, les contraintes peuvent être combinées avec la programmation fonctionnelle , la réécriture de termes et les langages impératifs . Parmi les langages de programmation intégrant la gestion des contraintes, on trouve Oz (programmation fonctionnelle) et Kaleidoscope (programmation impérative). Le plus souvent, les contraintes sont implémentées dans les langages impératifs via des bibliothèques dédiées à la résolution de contraintes , qui sont des modules complémentaires pour un langage impératif existant.

de programmation logique ; le domaine a donc été initialement appelé programmation logique par contraintes . Les deux paradigmes partagent de nombreuses caractéristiques importantes, comme les variables logiques et le retour arrière . Aujourd'hui, la plupart des implémentations de Prolog incluent une ou plusieurs bibliothèques pour la programmation logique par contraintes.

La différence entre les deux réside principalement dans leurs styles et leurs approches de la modélisation du monde. Certains problèmes se prêtent plus naturellement (et donc plus simples) à la programmation logique, tandis que d'autres se prêtent mieux à la programmation par contraintes.

La programmation par contraintes consiste à rechercher un état du monde où un grand nombre de contraintes sont satisfaites simultanément. Un problème est généralement formulé comme un état du monde contenant plusieurs variables inconnues. Le programme de programmation par contraintes recherche alors les valeurs de toutes ces variables.

La programmation par contraintes concurrentes temporelles (TCC) et la programmation par contraintes concurrentes temporelles non déterministes (MJV) sont des variantes de la programmation par contraintes qui peuvent gérer le temps.

Problème de satisfaction de contraintes

Il existe trois catégories de contraintes :

  • contraintes extensionnelles : les contraintes sont définies en énumérant l’ensemble des valeurs qui les satisferaient ;
  • contraintes arithmétiques : les contraintes sont définies par une expression arithmétique, c'est-à-dire en utilisant ;
  • Contraintes logiques : les contraintes sont définies avec une sémantique explicite, par exemple : AllDifferent , AtMost , ...

L'affectation consiste à associer une variable à une valeur de son domaine. On parle d'affectation partielle lorsqu'un sous-ensemble des variables du problème est affecté. L'affectation est totale lorsque toutes les variables du problème sont affectées.

prouver l'insatisfiabilité du problème.

problème d'optimisation sous contraintes

La propagation des contraintes dans les problèmes de satisfaction de contraintes est un exemple typique de modèle de raffinement, et l'évaluation des formules dans les tableurs est un exemple typique de modèle de perturbation.

Le modèle de raffinement est plus général, car il ne restreint pas les variables à une seule valeur ; il peut donc mener à plusieurs solutions pour un même problème. Cependant, le modèle de perturbation est plus intuitif pour les programmeurs utilisant des langages orientés objet à contraintes impératives mixtes.

Domaines

Les contraintes utilisées en programmation par contraintes portent généralement sur des domaines spécifiques. Voici quelques domaines d'application courants :

Les domaines finis constituent l'un des domaines d'application les plus fructueux de la programmation par contraintes. Dans certains domaines (comme la recherche opérationnelle ), la programmation par contraintes est souvent assimilée à la programmation par contraintes sur des domaines finis.

Propagation des contraintes

problèmes de satisfaction de contraintes liées à la cohérence de sous-ensembles de variables ou de contraintes. Elles permettent de réduire l'espace de recherche et de simplifier la résolution du problème. Différents types de conditions de cohérence locale sont utilisés, notamment la cohérence des nœuds , la cohérence des arcs et la cohérence des chemins .

Toute condition de cohérence locale peut être imposée par une transformation qui modifie le problème sans en changer les solutions. Une telle transformation est appelée propagation de contraintes . La propagation de contraintes agit en réduisant les domaines des variables, en renforçant les contraintes ou en en créant de nouvelles. Ceci conduit à une réduction de l'espace de recherche, facilitant ainsi la résolution du problème par certains algorithmes. La propagation de contraintes peut également servir de vérificateur d'insatisfiabilité ; elle est généralement incomplète, mais complète dans certains cas particuliers.

Résolution de contraintes

Il existe trois principales techniques algorithmiques pour résoudre les problèmes de satisfaction de contraintes : la recherche par retour arrière, la recherche locale et la programmation dynamique.

Recherche avec retour arrière

algorithme général permettant de trouver toutes (ou certaines) solutions à certains problèmes de calcul , notamment les problèmes de satisfaction de contraintes , qui construit progressivement des candidats aux solutions et abandonne un candidat (« retour arrière ») dès qu’il détermine que le candidat ne peut pas être complété en une solution valide.

Recherche locale

problèmes . Elle repose sur l'amélioration itérative d'une affectation de variables jusqu'à ce que toutes les contraintes soient satisfaites. Plus précisément, les algorithmes de recherche locale modifient généralement la valeur d'une variable dans une affectation à chaque étape. La nouvelle affectation est proche de la précédente dans l'espace des affectations, d'où le nom de recherche locale .

Programmation dynamique

d'optimisation mathématique et une méthode de programmation informatique. Elle consiste à simplifier un problème complexe en le décomposant en sous-problèmes plus simples de manière récursive . Si certains problèmes de décision ne peuvent être décomposés ainsi, les décisions qui s'étendent sur plusieurs instants s'y prêtent souvent. De même, en informatique, si un problème peut être résolu de manière optimale en le décomposant en sous-problèmes, puis en trouvant récursivement les solutions optimales de ces sous-problèmes, alors on dit qu'il possède une sous-structure optimale .

Exemple

La syntaxe pour exprimer les contraintes sur des domaines finis dépend du langage hôte. Voici un programme Prolog qui résout le problème alphamétique classique SEND+MORE=MONEY en programmation logique par contraintes :

la propagation de la contrainte sur la all_differentcontrainte supprime la valeur 1 du domaine de toutes les variables restantes. La propagation des contraintes peut résoudre le problème en réduisant tous les domaines à une seule valeur, elle peut prouver que le problème n'a pas de solution en réduisant un domaine à l'ensemble vide, mais elle peut aussi s'arrêter sans prouver la satisfaisabilité ou l'insatisfiabilité. Les littéraux d'étiquettes servent à effectuer la recherche d'une solution.