Skip to Main content Skip to Navigation
Conference papers

Sur la génération et l'exploitation de décompositions pour la résolution de réseaux de contraintes

Résumé : Les méthodes exploitant les décompositions arborescentes pour résoudre des réseaux de contraintes semblent constituer les meilleures approches en termes de complexité théorique en temps. Néanmoins, on peut estimer qu'elles n'ont pas démontré, à ce jour, un véritable intérêt pratique. Aussi, dans cette contribution, nous étudions tout d'abord différentes stratégies d'approximations de décompositions arborescentes optimales, et nous analysons ensuite leur pertinence dans le cadre de la résolution de CSP. Dans une seconde partie, nous étudions le problème du choix de la meilleure stratégie pour le parcours de l'arbre de clusters associé dans le cadre de la résolution du CSP. Les stratégies sont relatives notamment au choix du cluster racine, c'est-à-dire, celui à partir duquel débutera la recherche. Un deuxième aspect concerne l'ordre dans lequel les fils d'un cluster seront visités.
Complete list of metadatas

https://hal.inria.fr/inria-00000072
Contributor : Christine Solnon <>
Submitted on : Thursday, May 26, 2005 - 11:26:08 AM
Last modification on : Monday, March 30, 2020 - 8:41:06 AM
Document(s) archivé(s) le : Thursday, April 1, 2010 - 9:33:24 PM

Files

Identifiers

  • HAL Id : inria-00000072, version 1

Citation

Philippe Jégou, Samba Ndiaye, Cyril Terrioux. Sur la génération et l'exploitation de décompositions pour la résolution de réseaux de contraintes. Premières Journées Francophones de Programmation par Contraintes, CRIL - CNRS FRE 2499, Jun 2005, Lens, pp.149-158. ⟨inria-00000072⟩

Share

Metrics

Record views

152

Files downloads

93