Date : 2005
Editeur / Publisher : [S.l.] : [s.n.] , 2005
Type : Livre / Book
Type : Thèse / ThesisLangue / Language : français / French
Résumé / Abstract : Cette thèse propose une approche hybride générique pour résoudre les problèmes de satisfaction de contraintes (CSP). Après avoir présenté les CSP et les méthodes couramment utilisées pour les résoudre, nous présentons notre approche, combinant des stratégies inspirées de la recherche arborescente et de la recherche locale. Le cadre unificateur est celui d'une population d'individus, lesquels correspondent, non pas à des solutions, mais à des sous-ensembles de l'espace de recherche. La propagation de contraintes et la découpe de domaines contribuent à réduire les individus à des sous-ensembles plus restreints; la recherche locale examine des solutions (appelées "points") dans un individu. Notre approche est évaluée expérimentalement sur un ensemble de problèmes. Enfin, nous proposons de nouvelles perspectives et adaptations possibles de notre approche sur d'autres types de problèmes.
Résumé / Abstract : In this thesis, we propose a generic hybrid approach to solve Constraints Satisfaction Problems (CSP). After having presented the CSP and the methods usually used to solve them, we present our approach, combining strategies inspired of arborescent search and local search. The unifying framework is that of an individuals population, which correspond, with not solutions, but with subsets of the search space. The constraint propagation and the domain splitting contribute to reduce individuals to subsets more restricted. Local search examnines solutions in an individual. Our approach is experiments evaluated on a problems set. Lastly, we propose new prospects and possible adaptation of our approach on other problems types.