Skip to Main content Skip to Navigation
Conference papers

Consistance duale conservative

Résumé : Les consistances sont des propriétés de réseaux de contraintes qui peuvent être exploitées afin de générer des inférences. Lorsqu'un nombre important d'inférences peut être effectué, il devient alors plus facile de résoudre les réseaux à l'aide par exemple d'une recherche systématique. Dans ce papier, nous nous intéressons aux consistances de relation, i.e. aux consistances qui permettent d'identifier des couples de valeurs inconsistantes. Nous proposons une nouvelle consistance, appelée consistance duale (DC pour Dual Consistency), et nous la comparons à la consistance de chemin (PC pour Path Consistency). Nous montrons que la DC conservative (CDC), i.e. DC telle que seules les relations associées aux contraintes du réseau soient filtrées, est plus forte, en terme de filtrage, que la PC conservative (CPC). En suivant l'approche de Mac Gregor, nous introduisons un algorithme pour établir la CDC (forte) avec une complexité spatiale très faible dans le pire des cas. Bien que l'efficacité relative de l'algorithme introduit dépend en partie de la densité du graphe de contraintes, l'expérimentation que nous avons conduite montre que, sur de nombreuses séries d'instances, établir CDC à l'aide de cet algorithme est largement plus rapide qu'établir CPC à l'aide d'algorithmes directement adaptés de PC-8 ou PC-2001. Par ailleurs, nous avons observé qu'établir CDC lors d'une phase de pré-traitement permet une accélération significative de la résolution de certaines instances structurées difficiles.
Document type :
Conference papers
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/inria-00150733
Contributor : Sylvain Soliman <>
Submitted on : Thursday, May 31, 2007 - 2:25:17 PM
Last modification on : Thursday, January 11, 2018 - 6:19:28 AM
Long-term archiving on: : Friday, September 21, 2012 - 4:00:45 PM

File

27.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00150733, version 1

Collections

Citation

Christophe Lecoutre, Stéphane Cardon, Julien Vion. Consistance duale conservative. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France. ⟨inria-00150733⟩

Share

Metrics

Record views

111

Files downloads

89