Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [24 references]  Display  Hide  Download

https://hal.inria.fr/hal-00811474
Contributor : Alexandre Niveau <>
Submitted on : Wednesday, April 10, 2013 - 1:53:03 PM
Last modification on : Wednesday, June 9, 2021 - 10:00:24 AM
Long-term archiving on: : Monday, April 3, 2017 - 3:34:42 AM

File

NiveauFargierPralet_JFPC2012.p...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00811474, version 1

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. ⟨hal-00811474⟩

Share

Metrics

Record views

285

Files downloads

119