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.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00085810
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 15:38:06
Dernière modification le : jeudi 15 mars 2018 - 16:56:06
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:10:01

Fichier

Identifiants

  • HAL Id : inria-00085810, version 1

Collections

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, 2006. 〈inria-00085810〉

Partager

Métriques

Consultations de la notice

168

Téléchargements de fichiers

73