Compilation de CSP en Set-labeled Diagram - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

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.
Fichier principal
Vignette du fichier
NiveauFargierPralet_JFPC2012.pdf (539.79 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00811474 , version 1 (10-04-2013)

Identifiants

  • HAL Id : hal-00811474 , version 1

Citer

Alexandre Niveau, Hélène Fargier, Cédric Pralet. Compilation de CSP en Set-labeled Diagram. 8èmes Journées Francophones sur la Programmation par Contraintes (JFPC 2012), LAAS, Toulouse; Association francaise de programmation par contraintes, May 2012, Toulouse, France. pp.244-253. ⟨hal-00811474⟩
155 Consultations
80 Téléchargements

Partager

Gmail Facebook X LinkedIn More