Une nouvelle approche pour le test d'inconsistance de CSP

Résumé : Tester la consistance de CSP est en théorie un problème NP-Complet. Il existe deux familles de méthodes pour le test de consistance. La première famille regroupe les méthodes complètes qui font un parcours exhaustif de l'espace de recherche de solutions. Ces méthodes ont l'avantage de prouver l'inconsistance de CSP, cependant leur complexité croît exponentiellement avec la taille du problème. La seconde famille inclut les méthodes incomplètes qui font de la recherche locale sur l'espace de recherche de solutions. Ces méthodes ont été utilisées efficacement pour trouver des solutions pour des problèmes de grande taille que les méthodes complètes ne peuvent résoudre. Le principal inconvénient des méthodes incomplètes reste tout de même leur incapacité de prouver l'inconsistance d'une instance CSP. L'un des challenges mis en avant par la communauté CP (Selman et al. 1997) est de proposer des méthodes incomplètes efficaces pour la preuve d'inconsistance de CSP. Le travail que nous présentons ici est une contribution à ce difficile challenge. Nous introduisons une nouvelle méthode incomplète pour le test d'inconsistance qui se base sur la notion de dominance entre CSPs et la coloration de la micro-structure du CSP. Nous avons expérimenté la méthode sur des instances CSP générées aléatoirement et les résultats obtenus sont très encourageant.
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.201-208, 2008
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00291586
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : vendredi 27 juin 2008 - 15:20:14
Dernière modification le : jeudi 11 janvier 2018 - 06:24:45
Document(s) archivé(s) le : vendredi 28 mai 2010 - 20:25:39

Fichier

pages-201-208-article4.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00291586, version 1

Collections

Citation

Belaïd Benhamou, Mohamed Saïdi. Une nouvelle approche pour le test d'inconsistance de CSP. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.201-208, 2008. 〈inria-00291586〉

Partager

Métriques

Consultations de la notice

79

Téléchargements de fichiers

192