Skip to Main content Skip to Navigation
Conference papers

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

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/inria-00151225
Contributor : Sylvain Soliman <>
Submitted on : Friday, June 1, 2007 - 6:22:35 PM
Last modification on : Monday, March 30, 2020 - 8:52:48 AM
Long-term archiving on: : Thursday, April 8, 2010 - 6:44:50 PM

File

51.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00151225, version 1

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

Share

Metrics

Record views

155

Files downloads

248