Intégration partielle de la consistance de chemin dans la résolution des CSP

Assef Chmeiss 1 Vincent Krawczyk 1 Lakhdar Saïs 1
1 CRIL - Centre de Recherche en Informatique de Lens
Résumé : De nombreuses propriétés de consistance locale ont été exploitées dans la résolution des problèmes de satisfaction de contraintes (CSP). L'objectif est de réduire l'espace de recherche et par conséquent améliorer les méthodes de résolution. La consistance d'arc a été la forme de consistance locale la plus étudiée. Il a été montré que le maintien de la consistance d'arc durant la recherche est très utile pour la résolution des CSP. L'utilisation de formes plus fortes de consistance locale (comme la consistance de chemin) est encore limitée car elles nécessitent la gestion de structures de données complexes. Dans ce papier, nous proposons une technique permettant l'exploitation, dans la phase de prétraitement, d'une forme partielle de consistance d'arc et de chemin. Cette consistance est basée sur la notion d'intervalles de supports. Nous montrons aussi que, grâce à cette forme de consistance, il est possible de réduire l'espace de recherche pendant la résolution.
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.385-389, 2008
Liste complète des métadonnées
https://hal.inria.fr/inria-00293693
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : lundi 7 juillet 2008 - 13:13:32
Dernière modification le : jeudi 11 janvier 2018 - 06:19:28
Document(s) archivé(s) le : vendredi 28 mai 2010 - 21:31:41

Fichier

pages-385-389-article38.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00293693, version 1

Collections

JFPC08

Citation

Assef Chmeiss, Vincent Krawczyk, Lakhdar Saïs. Intégration partielle de la consistance de chemin dans la résolution des CSP. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.385-389, 2008. 〈inria-00293693〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

226

Téléchargements de fichiers

247

Contact


archive-ouverte@inria.fr