Génération rapide et filtrage de configurations canoniques

Résumé : La configuration sous contraintes présente une nouvelle difficulté à prendre en compte par les méthodes d'élimination de symétries connues par la communauté CSP car elle y introduit un aspect dynamique. Nous présentons ici une amélioration significative d'un algorithme de génération de configurations canoniques. Cette nouvelle version exploite l'incrémentalité que l'on peut faire ressortir de la génération de solutions canoniques et de l'ordre total sur les arbres sur laquelle elle repose. La complexité du test de canonicité passe ainsi de O(Nlog(N)) à O(N). De plus, une technique de filtrage nous permet d'éliminer à l'avance des configurations non canoniques. Des résultats expérimentaux montrent l'intérêt de cette approche sur des problèmes classiques.
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, Rocquencourt / 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-00151237
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 19:03:10
Dernière modification le : jeudi 15 mars 2018 - 16:56:06
Document(s) archivé(s) le : vendredi 21 septembre 2012 - 16:06:16

Fichier

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

Identifiants

  • HAL Id : inria-00151237, version 1

Collections

Citation

Laurent Henocque, Nicolas Prcovic. Génération rapide et filtrage de configurations canoniques. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, Rocquencourt / France, 2007, JFPC07. 〈inria-00151237〉

Partager

Métriques

Consultations de la notice

84

Téléchargements de fichiers

57