From Implicit to Explicit Pavings

Gilles Chabert 1 Rémi Douence 2
1 TASC - Theory, Algorithms and Systems for Constraints
Inria Rennes – Bretagne Atlantique , Département informatique - EMN, LINA - Laboratoire d'Informatique de Nantes Atlantique
2 ASCOLA - Aspect and composition languages
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
Résumé : Une recherche combinatoire peut être réalisée soit en utilisant un arbre de recherche implicite, où l'état initial est récursivement transformé jusqu'à atteindre un état but, soit en utilisant un arbre de recherche explicite, où la structure d'arbre initiale contenant l'état racine est itérativement étendue jusqu'aux feuilles qui satisfont l'ensemble des états buts. Ce rapport propose une étude exploratoire visant à montrer que les arbres de recherche explicites peuvent jouer un rôle notable dans le cas des contraintes numériques. Le premier avantage de la recherche explicite est son expressivité : on peut écrire de nouveaux algorithmes ou reformuler des algorithmes existants d'une manière simple et unifiée. Le second avantage est l'efficacité car une recherche explicite permet d'éviter, dans certains cas, une explosion de calculs redondants. Ceci est illustré à travers plusieurs exemples
Liste complète des métadonnées


https://hal.inria.fr/hal-00720739
Contributeur : Gilles Chabert <>
Soumis le : mercredi 25 juillet 2012 - 15:32:34
Dernière modification le : samedi 17 septembre 2016 - 01:36:39
Document(s) archivé(s) le : vendredi 16 décembre 2016 - 02:53:04

Fichier

RR-8028.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00720739, version 1

Citation

Gilles Chabert, Rémi Douence. From Implicit to Explicit Pavings. [Research Report] RR-8028, INRIA. 2012. <hal-00720739>

Partager

Métriques

Consultations de
la notice

324

Téléchargements du document

123