Skip to Main content Skip to Navigation
Conference papers

Complexité de Forward Checking et Hiérarchie des Décompositions de CSP Revisitées

Résumé : Dans cette contribution, nous proposons une nouvelle évaluation de la complexité de la procédure Forward Checking appliquée à la résolution de CSP n-aires à domaines finis. Généralement, cette évaluation prend en compte la taille des domaines associés aux variables. Ici, nous l'exprimons relativement à la taille des relations de compatibilité associées aux contraintes. Cette nouvelle approche permet ainsi, parfois, de fournir une meilleure borne de complexité théorique. Nous montrons l'intérêt essentiel de cette démarche en revenant sur les résultats proposés dans [10] et qui concernent la hiérarchie des décompositions de CSP (comparaisons des méthodes de décompositions structurelles), et qui constituent un résultat fondamental du domaine. Nous invalidons une partie de ces résultats en démontrant notamment que le concept de décomposition en hyperarbres, situé au sommet de cette hiérarchie, n'est finalement pas meilleur que celui de décomposition arborescente. Ce résultat, essentiellement théorique, s'avère toutefois en adéquation avec les observations expérimentales obtenues ces dernières années au sein de la communauté.
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.inria.fr/inria-00291557
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Friday, June 27, 2008 - 2:16:22 PM
Last modification on : Monday, March 30, 2020 - 8:42:25 AM
Document(s) archivé(s) le : Friday, May 28, 2010 - 10:55:25 PM

File

pages-153-163-article20.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00291557, version 1

Citation

Philippe Jégou, Samba Ndojh Ndiaye, Cyril Terrioux. Complexité de Forward Checking et Hiérarchie des Décompositions de CSP Revisitées. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.153-163. ⟨inria-00291557⟩

Share

Metrics

Record views

176

Files downloads

234