Elimination des symétries locales durant la résolution dans les CSPs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2007

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.
Fichier principal
Vignette du fichier
51.pdf (129.51 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00151225 , version 1 (01-06-2007)

Identifiants

  • HAL Id : inria-00151225 , version 1

Citer

Belaïd Benhamou, Mohamed Reda 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. ⟨inria-00151225⟩
80 Consultations
134 Téléchargements

Partager

Gmail Facebook X LinkedIn More