LIP6 1997/029
- Rapports de recherche
Programmation par contraintes en CLIPS - J.-M. Labat, M. Futtersack
- 29 pages - 12/11/1997- document en - http://www.lip6.fr/lip6/reports/1997/lip6.1997.029.ps.gz - 47 Ko
- Contact : Jean-Marc.Labat (at) nulllip6.fr
- Ancien Thème : SYSDEF
- Mots clés : contraintes, CLIPS, CCP, CSP
- Directeur de la publication : Valerie.Mangin (at) nulllip6.fr
CCP (CLIPS Constraint Programming) est une base de connaissance générique qui permet de faire de la programmation par contraintes a l'interieur du système CLIPS.
CCP est composé de trois modules. Le module MAIN contient la boucle de top-level incluant les règles d'interface H/M. Le module SEARCH implante un algorithme classique de backtrack chronologique.
Le module PROPAGATION implante un algorithme de Forward Checking. CCP a été testé sur de nombreux problèmes classiques : N-reines, coloration de graphe, mots croisés, etc.
Pour résoudre un nouveau problème, il suffit à l'utilisateur de déclarer chaque variable et son domaine, ainsi que les règles de propagation de contraintes. Ainsi toutes les connaissances spécifiques à un probleme sont encapsulées dans le module PROPAGATION.
CCP est un outil générique qui peut être intégré dans un système à base de règles pour faire localement de la programmation par contraintes.
CCP est tres compact puisqu'il ne contient en tout qu'une quinzaine de règles générales. De plus, CCP peut être utilisé à des fins pédagogiques car il illustre de nombreuses fonctionnalités avancées de CLIPS (dépendances logiques, quantificateurs existenciel et universel, écriture dynamique de règles, utilisation de la pile des focus pour le contrôle stratégique).
CCP est composé de trois modules. Le module MAIN contient la boucle de top-level incluant les règles d'interface H/M. Le module SEARCH implante un algorithme classique de backtrack chronologique.
Le module PROPAGATION implante un algorithme de Forward Checking. CCP a été testé sur de nombreux problèmes classiques : N-reines, coloration de graphe, mots croisés, etc.
Pour résoudre un nouveau problème, il suffit à l'utilisateur de déclarer chaque variable et son domaine, ainsi que les règles de propagation de contraintes. Ainsi toutes les connaissances spécifiques à un probleme sont encapsulées dans le module PROPAGATION.
CCP est un outil générique qui peut être intégré dans un système à base de règles pour faire localement de la programmation par contraintes.
CCP est tres compact puisqu'il ne contient en tout qu'une quinzaine de règles générales. De plus, CCP peut être utilisé à des fins pédagogiques car il illustre de nombreuses fonctionnalités avancées de CLIPS (dépendances logiques, quantificateurs existenciel et universel, écriture dynamique de règles, utilisation de la pile des focus pour le contrôle stratégique).