ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique

APPEL À
CONTRIBUTION
Masses de données hétérogènes
En savoir plus >>
Autres revues >>

Revue d'Intelligence Artificielle

0992-499X
Revue des Sciences et Technologies de l'Information
 

 ARTICLE VOL 28/5 - 2014  - pp.521-522
TITRE
INTRODUCTION

RÉSUMÉ

Malgré son nom peu attrayant, la programmation par contraintes représentait à l’origine un idéal d’informaticien : un cadre de programmation purement déclaratif. Le programmeur qui souhaite calculer un résultat n’a alors qu’à le décrire dans un langage adapté, fait de contraintes, et un solveur trouve une solution à son problème. Ce cadre idyllique a malheureusement un prix, qui pour la programmation par contraintes se paie principalement en temps de calcul du solveur. Traditionnellement apparentée à l’intelligence artificielle, la communauté de programmation par contraintes s’est organisée en domaine scientifique dans les années 1990, avec une conférence internationale créée en 1994, et en France, deux conférences nationales, nées en 1992 et 1994 : les Journées Francophones de Programmation Logique avec Contraintes (JFPLC) et les Journées Nationales sur la Résolution Pratique de Problèmes NP - complets (JNPC). On retrouve dans ces titres deux préoccupations fondamentales et complémentaires du domaine : pouvoir résoudre les problèmes efficacement en pratique, et proposer des langages expressifs et génériques, initialement basés sur la programmation logique. Logique, car la programmation par contraintes était alors naturellement implémentée dans la famille des langages logiques Prolog : on peut en effet définir une contrainte comme un prédicat de la logique du premier ordre. En combinant ces contraintes dans un langage logique, on obtient un cadre de programmation déclarative générique, permettant a priori une grande flexibilité de programmation. On retrouve cette idée dans l’article de Dao, Duong et Vrain, où la généricité de la programmation par contraintes permet à l’utilisateur d’exprimer facilement des propriétés dans un cadre applicatif, la classification non supervisée. Les problèmes pratiques qui se posent lors de la résolution de contraintes sont liés à la nature combinatoire des problèmes de contraintes, les CSP (Constraint Satisfaction Problem), qui portent sur des variables indépendantes, les inconnues du problème. Ces variables sont le plus souvent de domaines finis. L’ensemble des affectations possibles de valeurs des domaines aux variables est alors le produit cartésien des domaines : par nature, l’espace des possibles est donc de taille exponentielle en le nombre de variables, d’où un temps de résolution a priori exponentiel. Afin de réduire ce temps de calcul, on exploite l’information des contraintes pour couper le domaine des variables : s’il est possible de prouver qu’une valeur d’un domaine n’appartient à aucune solution du problème, alors on peut enlever cette valeur sans dommages. Ce principe est répété dans les solveurs pour chaque domaine et chaque contrainte du problème. Or, il est difficile, dans le cas général, de trouver une façon efficace de propager les contraintes. Les méthodes modernes de propagation sont devenues très subtiles, et reposent sur une algorithmique belle et complexe. L’article de Vion et Piechowiak est un bel exemple. Les auteurs utilisent une structure de donnée, les diagrammes de décision multivalués, maintenue incrémentalement au cours de la recherche et exploitée pour éviter certains calculs superflus.



AUTEUR(S)
Charlotte TRUCHET

LANGUE DE L'ARTICLE
Français

 PRIX
GRATUIT
   
ACCÉDER A L'ARTICLE COMPLET  (20 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier