Elimination des symétries locales durant la résolution dans les CSPs

Résumé : Plusieurs approches exploitant l'élimination des symétries dans la résolution des CSPs sont apparues récemment. La grande majorité de ces méthodes exploitent les symétries globales du problème étudié et ne tente pas d'exploiter les symétries locales. Il a été montré que l'élimination des symétries globales peut être utile dans la résolution des CSPs. Mais exploiter uniquement ces symétries peut ne pas suffire pour résoudre des problèmes difficiles contenant de nombreuses symétries locales. En effet, un problème peut avoir peu ou pas du tout de symétries initiales (globales) et devenir très symétrique à certains noeuds durant la recherche. Dans ce papier, nous étudions le principe général de la symétrie sémantique et on définit la symétrie syntaxique qui est une condition suffisante de la symétrie sémantique. Nous montrons comment la symétrie syntaxique est détectée et éliminée localement pour améliorer l'efficacité des méthodes de résolution de CSPs. Les expérimentations confirment que l'exploitation des symétries locales est profitable dans la résolution des CSPs.
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 [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00151225
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 18:22:35
Dernière modification le : jeudi 15 mars 2018 - 16:56:06
Document(s) archivé(s) le : jeudi 8 avril 2010 - 18:44:50

Fichier

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

Identifiants

  • HAL Id : inria-00151225, version 1

Collections

Citation

Belaïd Benhamou, Mohamed Saïdi. Elimination des symétries locales durant la résolution dans les CSPs. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07. 〈inria-00151225〉

Partager

Métriques

Consultations de la notice

102

Téléchargements de fichiers

131