| HAL-Inria | Publications, software ... of Inria's scientists |
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.
Cited literature [17 references]
https://hal.inria.fr/inria-00151218
Contributor : Sylvain Soliman Connect in order to contact the contributor
Submitted on : Friday, June 1, 2007 - 6:08:15 PM
Last modification on : Wednesday, October 20, 2021 - 9:58:16 AM
Long-term archiving on: : Thursday, April 8, 2010 - 6:44:25 PM
Contributor : Sylvain Soliman Connect in order to contact the contributor
Submitted on : Friday, June 1, 2007 - 6:08:15 PM
Last modification on : Wednesday, October 20, 2021 - 9:58:16 AM
Long-term archiving on: : Thursday, April 8, 2010 - 6:44:25 PM
File
22.pdf
Files produced by the author(s)