Tables de transposition pour la satisfaction de contraintes

Christophe Lecoutre 1 Lakhdar Saïs 1 Sébastien Tabary 1 Vincent Vidal 1
1 CRIL - Centre de Recherche en Informatique de Lens
Résumé : Dans ce papier, nous proposons une approche basée sur la reconnaissance d'états dans le cadre de la résolution du problème de satisfaction de contraintes (CSP). L'idée principale consiste en la mémorisation d'états pendant la recherche de manière à prévenir la résolution de sous-réseaux similaires. Les techniques classiques évitent la réapparition de conflits précédemment rencontrés en enregistrant des ensembles conflits (conflict sets). Ceci contraste avec notre approche basée sur les états qui mémorise des sous-réseaux déjà explorés, c'est à dire une photographie de certains domaines sélectionnés. Ces informations sont ensuite exploitées pour éviter soit le parcours d'états in consistants, soit de recalculer l'ensemble des solutions de ces sous-réseaux. Les deux approches présentent une certaine complémentarité : en effet différents états peuvent être évités à partir d'une même instantiation partielle ou ensemble conflits tandis que différentes instantiations partielles peuvent mener à un même état qui n'a besoin d'être exploré qu'une seule fois. De plus notre méthode permet de détecter et casser dynamiquement certaines formes de symétries (notamment l'interchangeabilité au voisinage). Les résultats expérimentaux obtenus laissent entrevoir des perspectives promette uses pour la recherche basée sur les états.
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00151218
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 18:08:15
Dernière modification le : jeudi 11 janvier 2018 - 06:19:28
Document(s) archivé(s) le : jeudi 8 avril 2010 - 18:44:25

Fichier

22.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00151218, version 1

Collections

JFPC07

Citation

Christophe Lecoutre, Lakhdar Saïs, Sébastien Tabary, Vincent Vidal. Tables de transposition pour la satisfaction de contraintes. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07. 〈inria-00151218〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

98

Téléchargements de fichiers

54

Contact


archive-ouverte@inria.fr