Skip to Main content Skip to Navigation
Conference papers

Les CSP extrêmaux

Résumé : Nous proposons une nouvelle classe de CSP binaires appelés CSP extrêmaux. Les CSP de cette classe sont inconsistants mais deviendraient consistants si n'importe quel couple de valeurs interdit devenait autorisé. Etant inconsistants, ils ne sont pas traitables avec des méthodes de réparation locale. Comme ils autorisent un nombre très élevé de solutions partielles presque complètes, ils peuvent être très difficiles à résoudre à l'aide de méthodes de recherche arborescente intégrant le filtrage des domaines. Il faudra donc trouver de nouvelles méthodes pour les résoudre. Nous présentons un algorithme simple de génération de CSP extrêmaux. Nous constatons expérimentalement que les CSP extrêmaux équilibrés sont beaucoup plus longs à résoudre que les CSP aléatoires dits difficiles de même taille. Nous présentons aussi un schéma d'algorithme susceptible d'être performant sur des problèmes difficiles, dès lors qu'on sera en mesure de générer suffisamment rapidement des CSP extrêmaux.
Complete list of metadata

https://hal.inria.fr/inria-00000066
Contributor : Christine Solnon <>
Submitted on : Thursday, May 26, 2005 - 10:04:15 AM
Last modification on : Monday, March 30, 2020 - 8:49:27 AM
Long-term archiving on: : Thursday, April 1, 2010 - 9:32:59 PM

Files

Identifiers

  • HAL Id : inria-00000066, version 1

Citation

Nicolas Prcovic. Les CSP extrêmaux. Premières Journées Francophones de Programmation par Contraintes, CRIL - CNRS FRE 2499, Jun 2005, Lens, pp.315-324. ⟨inria-00000066⟩

Share

Metrics

Record views

120

Files downloads

98