Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Programmation par contraintes

No description
by

Mokded Mohamed Ali

on 25 November 2013

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Programmation par contraintes

Programmation par contraintes
Introduction(1)
Plan
Introduction

I. Problèmes en PPC
1- Présentation d’un problème
i. Le réseau de contraintes (CN)
ii. Les algorithmes de filtrage
iii. Un mécanisme de propagation
iv. Un mécanisme de recherche de solution
2- Méthodes de résolution
i. Recherche arborescente
ii. Consistance locale
II. Quelques modèles PPC pratiques
III. Solveurs PPC

Conclusion

Elaboré par : WETCHA Chaima
MOKDED Mohamed ALi


La programmation par contraintes (PPC) est un paradigme de programmation ou une technique de résolution des problèmes qui vient de l’Intelligence Artificielle et qui permettant de résoudre des problèmes combinatoires de grandes tailles tels que les problèmes de planification et d'ordonnancement.

Elle est inspirée de :
*.La programmation logique avec contraintes et principalement de Prolog.

*Des problèmes de satisfaction de contraintes (CSP).

*Des travaux sur les “General Problem Solvers”.

Introduction(2)
Problèmes en PPC
Présentation d’un problème(1)
Dans la PPC un problème est représenté par :

*
Des variables
 : appartenant à un domaine définissant l’ensemble de valeurs possibles de ces variables.

*
Des contraintes
 : Une contrainte est une relation entre plusieurs variables qui limitent l'ensemble des valeurs que peuvent prendre ces variables simultanément.
Présentation d’un problème(2)
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.) ;

*Contraintes dont la sémantique est décrite : « toutes différentes », etc.

Présentation d’un problème(3)
Un problème en PPC peut se décomposer aussi en des
sous-problèmes
simples ou complexes c’est à dire à une
conjonction
de sous-problèmes. Et chaque problème sera résolu d’une manière spécifique et en conséquent de cette composition pour chaque contrainte, le domaine de variables sera réduis.


C’est les mécanismes de filtrage et propagation


Présentation d’un problème(4)
La programmation par contraintes s’articule autour de quatre entités majeures :

* Le réseau de contraintes (CN)

* Les algorithmes de filtrage

* Un mécanisme de propagation

* Un mécanisme de recherche de solutions

Le réseau de contraintes
Un réseau de contrainte est défini par :

*Un ensemble de variables X={x1, x2,…, xn}

*Un ensemble de domaines D : est l’ensemble fini des valeurs possibles pour la variable xi

*Un ensemble des contraintes C entre les variables.



Les algorithmes de filtrage(1)
Il est associé à chaque contrainte. Son rôle est de supprimer des valeurs des domaines des variables de la contrainte pour lesquelles il n’est pas possible de satisfaire la contrainte.





Les algorithmes de filtrage(2)
Exemple :
Soit X et Y deux variables.

Les domaines : D(X) = [10,20] et D(Y) = [0,15].
La contrainte est : X<Y.
Un algorithme de filtrage associé à cette contrainte pourra supprimer les valeurs de 15 à 20 de D(x) et les valeurs de 0 à 10 de D(y).

DONC : D(X) = [10,15] et D(Y) = [10,15]

Un mécanisme de propagation
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 à explore donc dès qu’un algorithme de filtrage modifie le domaine d’une variable, cette modification sera étudiée par les autres contraintes impliquant cette variable afin de déduire des autres suppressions.

On dit alors qu’une modification a été propagée
Ce mécanisme de propagation est répété jusqu’à ce que plus aucune modification n’apparaisse.

Un mécanisme de recherche
de solutions (1)
La programmation par contraintes est plus particulièrement des CSP (Constraints Satisfaction Problem) avait pour but de résoudre des problèmes de satisfaction. Donc une solution est considérée comme une instanciation des variables qui satisfait toutes les contraintes.
Un mécanisme de recherche
de solutions (2)
Le but de ce mécanisme est de trouver une solution éventuellement optimale en utilisant des différents moyens comme :

*Les stratégies de choix de variables et de valeurs

*Les méthodes de décomposition

*Les améliorations itératives

Méthodes de résolution
Recherche arborescente
Propagation des contraintes
Recherche arborescente (1)
Dans le cas de la résolution sur domaines finis, il est en théorie possible d'énumérer toutes les possibilités et de vérifier si elles violent ou non les contraintes, cette méthode est appelée générer et tester.

Mais lorsque le problème devient de taille de plus en plus grande cette solution devient inutile donc on trouve le filtrage comme solution à ce problème

Recherche arborescente (2)
Le filtrage consiste à déduire à partir de contraintes les valeurs impossibles et si à la fin une valeur est affectée à une variable, on dit variable instanciée mais le filtrage tout seul ne peut pus instancier toutes les variables on doit relancer le filtrage d’une manière récursive jusqu'à aboutir à une instanciation des toutes les variables.
Recherche arborescente (3)
Cette série de découpages du problème peut être représentée sous forme d'un arbre. Le but de la recherche est de parcourir cet arbre (en le construisant au fur et à mesure) jusqu'à trouver une solution au problème tandis que le filtrage consiste à « élaguer » cet arbre en supprimant toutes les parties n'aboutissant qu'à des contradictions.

Propagation des contraintes (2)
Propagation des contraintes (1)
La propagation de contraintes (ou filtrage) consiste à supprimer d'un problème de PPC des valeurs de variables ne pouvant pas prendre part à une solution.

Étant donné que toutes les contraintes d'un problème de PPC doivent être satisfaites, le fait pour une valeur d'une variable de ne pas pouvoir satisfaire une seule contrainte du problème implique qu'elle ne pourra prendre part à aucune solution du problème.


Il est donc possible de raisonner séparément sur chaque contrainte afin de pouvoir trouver des valeurs pour lesquelles cette contrainte ne peut être satisfaite, et donc les retirer du problème entier.
Propagation des contraintes (3)
On appelle consistance locale le fait de vérifier que certaines variables ne violent pas les contraintes qui lui sont liées. On ignore alors les autres variables et contraintes. Cela permet de filtrer alors certaines valeurs impossibles pour un coût réduit. Il existe plusieurs consistances locales, offrant chacune un équilibre différent entre efficacité du filtrage et rapidité de calcul.
Quelques modèles PPC pratiques
Exemple 1: coloriage d’une carte (1)
Exemple 1: coloriage d’une carte (2)
Exemple 2: SUDOKU (1)
Exemple 2: SUDOKU (2)
Exemple 2: SUDOKU (3)
Exemple 2: SUDOKU (4)
Exemple 2: SUDOKU (5)
Donc les étapes à suivre pour résoudre un problème de SUDOKU sont :
*Raisonnement par élimination, réduction du domaine

*Raisonnement local

*Transmission des déductions aux autres régions

Autres exemples
D’autres exemples de résolution de problèmes par PPC :

* cryptanalyse
* Les n reines
* Les circuits
* Enigmes
*Raisonnement temporel qualitatif
Solveurs PPC 
Solveurs basés sur la programmation logique 
*SICStus Prolog

*ECLiPSE Prolog

*GNU Prolog

*CHIP

Solveurs basés sur des librairies 
* ILOG soveur (C++)

* JSolver (Java)

*Choco (Java)

*Facile (Ocaml)

*CHIP Library (C++)

*JLC (Java)

Conclusion
La PPC est très souple puisqu’aucune hypothèse n’est faite ni sur le type des contraintes utilisées ni sur les domaines des variables. Par ailleurs, aucune solution ne peut être perdue puisque toutes les éventualités seront envisagées, c’est pourquoi on parle également d’algorithme énumératif.
Exemple 1: coloriage d’une carte (2)
Full transcript