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.
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 [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00150733
Contributeur : Sylvain Soliman <>
Soumis le : jeudi 31 mai 2007 - 14:25:17
Dernière modification le : jeudi 11 janvier 2018 - 06:19:28
Document(s) archivé(s) le : vendredi 21 septembre 2012 - 16:00:45

Fichier

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

Identifiants

  • 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, 2007, JFPC07. 〈inria-00150733〉

Partager

Métriques

Consultations de la notice

90

Téléchargements de fichiers

59