Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00291586
Contributor : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Submitted on : Friday, June 27, 2008 - 3:20:14 PM
Last modification on : Monday, March 30, 2020 - 8:41:17 AM
Long-term archiving on: : Friday, May 28, 2010 - 8:25:39 PM

File

pages-201-208-article4.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00291586, version 1

Citation

Belaïd Benhamou, Mohamed 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⟩

Share

Metrics

Record views

169

Files downloads

312