HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Un schéma générique d'algorithmes énumératifs avec (no)good recording pour la résolution bornée de CSP

Résumé : Ce papier présente un schéma générique d'algorithmes énumératifs pour la résolution de CSP. Ce schéma exploite des propriétés sémantiques et topologiques du réseau de contraintes afin de produire des goods et des nogoods. Il repose sur un ensemble de séparateurs du graphe de contraintes et plusieurs fonctions et procédures paramétrables de sorte à exploiter des heuristiques, des méthodes de filtrage, des techniques de retour en arrière intelligent, d'enregistrement de nogoods classiques ou de (no)goods structurels et des bornes de complexité théorique héritées des méthodes basées sur les décompositions de graphes. Selon les choix effectués, nous obtenons une famille d'algorithmes dont la complexité en temps est comprise entre $O(exp(w+1))$ et $O(exp(n))$ avec $w$ la largeur d'arbre du graphe de contraintes et $n$ le nombre de variables.
Document type :
Conference papers
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/inria-00151213
Contributor : Sylvain Soliman Connect in order to contact the contributor
Submitted on : Friday, June 1, 2007 - 6:04:21 PM
Last modification on : Friday, October 22, 2021 - 3:33:09 AM
Long-term archiving on: : Thursday, April 8, 2010 - 6:44:15 PM

File

16.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00151213, version 1

Citation

Samba Ndiaye, Cyril Terrioux. Un schéma générique d'algorithmes énumératifs avec (no)good recording pour la résolution bornée de CSP. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France. ⟨inria-00151213⟩

Share

Metrics

Record views

91

Files downloads

49