Skip to Main content Skip to Navigation
Conference papers

Tables de transposition pour la satisfaction de contraintes

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00151218
Contributor : Sylvain Soliman <>
Submitted on : Friday, June 1, 2007 - 6:08:15 PM
Last modification on : Thursday, January 11, 2018 - 6:19:28 AM
Long-term archiving on: : Thursday, April 8, 2010 - 6:44:25 PM

File

22.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00151218, version 1

Collections

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. ⟨inria-00151218⟩

Share

Metrics

Record views

128

Files downloads

63