Skip to Main content Skip to Navigation
Conference papers

Heuristiques pour la recherche énumérative bornée : Vers une libération de l'ordre

Résumé : Lors des JFPC'2005, les auteurs de la présente contribution, ont montré l'intérêt que recèle l'exploitation des heuristiques pour s'assurer de l'efficacité pratique des méthodes de résolution de CSP par décomposition arborescente. Nous étendons ce travail en le géné- ralisant. Nous montrons qu'au-delà d'heuristiques sur le parcours de l'arborescence associé à la décomposition, une gestion dynamique de l'heuristique de choix des variables s'avère cruciale. Tout en conservant les bornes de complexité (O(exp(w+1)) où w est la tree-width du CSP), nous proposons une voie pour s'aranchir en partie du carcan imposé par la structure arborescente. Cette démarche nous conduit à dénir de nouvelles bornes de complexité qui orent un compromis entre bornes théoriques et libération de l'ordre. En particulier, nous introduisons un nouveau paramètre k indiquant le degré de liberté laissé à l'heuristique de choix de variables qui permet de borner la complexité par O(exp(2(w + k))). Les résultats expérimentaux présentés montrent l'intérêt d'une telle démarche.
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/inria-00085810
Contributor : Laurent Henocque <>
Submitted on : Friday, July 14, 2006 - 3:38:06 PM
Last modification on : Monday, March 30, 2020 - 8:41:42 AM
Document(s) archivé(s) le : Tuesday, April 6, 2010 - 12:10:01 AM

File

Identifiers

  • HAL Id : inria-00085810, version 1

Citation

Philippe Jegou, Cyril Terrioux, Samba Ndiaye. Heuristiques pour la recherche énumérative bornée : Vers une libération de l'ordre. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France. ⟨inria-00085810⟩

Share

Metrics

Record views

225

Files downloads

118