Fiche de Révision : Principles Lecture 1 PPC

Introduction

Cette fiche présente les fondamentaux de la Programmation par Contraintes (PPC), méthode pour résoudre des problèmes en satisfaisant un ensemble de contraintes entre variables.

1. Qu’est-ce que la Programmation par Contraintes (PPC) ?

Définition : Technique où un solveur cherche des solutions qui satisfont toutes les contraintes exprimées entre variables.

1.1 Objectif principal

Trouver des valeurs pour des variables
Respectant des contraintes
Utile en planification, affectation, optimisation.

2. Les Composantes Clés d’un problème PPC

Composante	Description
Variables	Inconnues avec des domaines possibles.
Domaines	Valeurs possibles pour chaque variable.
Contraintes	Règles limitant les combinaisons de valeurs.

Exemple simple

Variables : X, Y
Domaines : X ∈ {1, 2, 3}, Y ∈ {2, 3, 4}
Contraintes : X < Y, X + Y = 5

3. Types de Contraintes

Égalité : ex. X + Y = 10
Inégalité : ex. X < Y
Globales : ex. all-different (variables distinctes)

4. Processus de Résolution d’un Problème PPC

[Diagramme]

5. Concepts complémentaires essentiels

5.1 Formulation d’un problème CSP

Triplet (X, D, C) : variables, domaines, contraintes.

5.2 Notion de Consistance

Arc-consistency : chaque valeur a un support compatible dans les variables liées.

6. Exemples Concrets

6.1 Coloriage de carte

Variables : régions
Domaines : couleurs
Contraintes : régions adjacentes de couleurs différentes

6.2 Planification

Variables : plages horaires
Domaines : activités
Contraintes : pas de chevauchement, disponibilités.

7. Liens entre concepts

Les types de contraintes influencent les techniques de résolution.
Le degré de consistance améliore l’efficacité.
La structure des variables/domaine impacte la taille du problème.

8. Synthèse

Point clé	Description
PPC	Programmation fondée sur contraintes
Composantes	Variables, Domaines, Contraintes
Contraintes globales	Restreignent plusieurs variables
Résolution	Assignation → Vérification → Réduction → Backtracking
Consistance	Réduction des domaines
Applications	Planification, configuration

Conclusion

Le PPC modélise et résout efficacement des problèmes complexes par contraintes. Comprendre variables, domaines, contraintes et mécanismes comme le backtracking est essentiel.

Annexes : Diagramme résumé de la résolution PPC