Exploitation de l'hypertree decomposition pour la resolution des problemes de satisfaction de contraintes

Abstract

Les problèmes de satisfaction de contraintes (CSP) sont un cadre générique permettant la représentation et la résolution d’une large palette de problèmes. Plusieurs approches existent pour la résolution des CSP, l’une d’elles est l’approche de résolution par décomposition qui regroupe un ensemble de méthodes dites de décomposition structurelle. Dans ce mémoire, nous nous intéressons particulièrement à une méthode récente de décomposition structurelle appelée hypertree ecomposition et plus particulièrement au calcul de cette décomposition. Nous proposons alors une nouvelle méthode heuristique appelée Construct&Reduce, pour le calcul de l’hypertree decomposition puis nous décrivons la manière dont cette nouvelle méthode peut être utilisée dans le cadre de la résolution des CSP.