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é.
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.153-163, 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00291557
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 27 juin 2008 - 14:16:22
Dernière modification le : jeudi 18 janvier 2018 - 01:55:40
Document(s) archivé(s) le : vendredi 28 mai 2010 - 22:55:25

Fichier

pages-153-163-article20.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00291557, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

117

Téléchargements de fichiers

156