Fast Global Filtering for Eternity II

Eric Bourreau 1 Thierry Benoist 2
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : In this paper we consider the enumeration of all solutions of a 2D edge-matching puzzle. We show that a judicious modeling of the problem, combined with the use of appropriate data structures allows obtaining an effective filtering algorithm with complexity O(1) at each node of tree search. Our experiments show the relevancy of the proposed power/complexity trade-off, compared to the results of some of the best available brute force tree search algorithms and to classical Constraint Programming models.
Type de document :
Article dans une revue
Constraint Programming Letters (CPL), CLS, 2008, 3, pp.036-049. 〈http://www.cs.brown.edu/people/pvh/CPL/Papers/v3/BenoistBourreau.pdf〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00364330
Contributeur : Eric Bourreau <>
Soumis le : mercredi 25 février 2009 - 17:01:30
Dernière modification le : jeudi 11 janvier 2018 - 06:26:23
Document(s) archivé(s) le : samedi 26 novembre 2016 - 06:04:10

Fichier

Bourreau_CPL08_eternity.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : lirmm-00364330, version 1

Collections

Citation

Eric Bourreau, Thierry Benoist. Fast Global Filtering for Eternity II. Constraint Programming Letters (CPL), CLS, 2008, 3, pp.036-049. 〈http://www.cs.brown.edu/people/pvh/CPL/Papers/v3/BenoistBourreau.pdf〉. 〈lirmm-00364330〉

Partager

Métriques

Consultations de la notice

207

Téléchargements de fichiers

204