Compilation de CSP en Set-labeled Diagram

Résumé : La plupart des requêtes associées aux CSPs sont NP-difficiles, et doivent pourtant parfois être exécutées en ligne et en temps limité. Dans ce cas, la résolution du CSP n'est pas assez efficace, voire impossible. Des structures ont été proposées, tels les MDDs, pour compiler les CSPs et rendre leur exploitation en ligne efficace. Les MDDs sont des DAGs orientés dont chaque nœud représente l'assignation d'une variable ; l'ensemble des solutions d'un CSP correspond à l'ensemble des chemins du MDD correspondant. Dans cet article, nous étudions la relaxation de deux restrictions usuellement imposées aux MDDs, l'ordonnancement et la non-répétition des variables, introduisant une structure de compilation nommée " set-labeled diagrams " (SDs). Un CSP peut être compilé en SD en suivant la trace de l'arbre de recherche exploré par un solveur de CSP. L'impact des restrictions susnommées peut être étudié en faisant varier les heuristiques utilisées par le solveur lors de la résolution.
Type de document :
Communication dans un congrès
JFPC - Journées Francophones sur la Programmation par Contraintes - 2012, May 2012, Toulouse, France. 2012
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00811474
Contributeur : Alexandre Niveau <>
Soumis le : mercredi 10 avril 2013 - 13:53:03
Dernière modification le : mercredi 28 mars 2018 - 14:16:10
Document(s) archivé(s) le : lundi 3 avril 2017 - 03:34:42

Fichier

NiveauFargierPralet_JFPC2012.p...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00811474, version 1

Collections

Citation

Alexandre Niveau, Hélène Fargier, Cédric Pralet. Compilation de CSP en Set-labeled Diagram. JFPC - Journées Francophones sur la Programmation par Contraintes - 2012, May 2012, Toulouse, France. 2012. 〈hal-00811474〉

Partager

Métriques

Consultations de la notice

149

Téléchargements de fichiers

61