Intégration partielle de la consistance de chemin dans la résolution des CSP - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2008

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

Assef Chmeiss
Lakhdar Saïs

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

Dates et versions

inria-00293693 , version 1 (07-07-2008)

Identifiants

  • HAL Id : inria-00293693 , version 1

Citer

Assef Chmeiss, Vincent Krawczyk, Lakhdar Saïs. Intégration partielle de la consistance de chemin dans la résolution des CSP. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, LINA - Université de Nantes - Ecole des Mines de Nantes, Jun 2008, Nantes, France. pp.385-389. ⟨inria-00293693⟩
115 Consultations
265 Téléchargements

Partager

Gmail Facebook X LinkedIn More