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.