Une nouvelle approche pour le test d'inconsistance de 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

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.
Fichier principal
Vignette du fichier
pages-201-208-article4.pdf (351.52 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00291586 , version 1 (27-06-2008)

Identifiants

  • HAL Id : inria-00291586 , version 1

Citer

Belaïd Benhamou, Mohamed Reda Saïdi. Une nouvelle approche pour le test d'inconsistance de 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.201-208. ⟨inria-00291586⟩
113 Consultations
233 Téléchargements

Partager

Gmail Facebook X LinkedIn More