Une stratégie de recherche basée sur la substituabilité

Overview & Synopsis

Nous introduisons une nouvelle stratégie de recherche pour énumérer toutes les solutions d'un problème de satisfaction de contraintes. L'idée principale de cette stratégie consiste à énumérer des solutions génériques à partir desquelles toutes les solutions peuvent être efficacement calculées. Les solutions génériques contiennent des valeurs qui sont substituables à toutes les autres. Notre stratégie provoque l'apparition des valeurs substituables. Ainsi, à la différence d'une stratégie de recherche classique, notre méthode économise du temps en générant seulement quelques solutions génériques. Nous montrons expérimentalement que notre approche donne des résultats intéressants sur des problèmes ayant un grand nombre de solutions.