Complexité de Forward Checking et Hiérarchie des Décompositions de CSP Revisitées - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

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

Dates et versions

inria-00291557 , version 1 (27-06-2008)

Identifiants

  • HAL Id : inria-00291557 , version 1

Citer

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⟩
107 Consultations
173 Téléchargements

Partager

Gmail Facebook X LinkedIn More