Etude comparative entre les méthodes de décomposition structurelles et les méthodes de décomposition sémantiques pour la résolution des CSPs

Abstract

Ce mémoire ce concentre sur la comparaison entre quelques méthodes structurelles et sémantiques o`u on a choisi la complexité comme métrique de comparaison, après avoir fait une études sur les généralités des CSPs puis les principales méthodes structurelles et sémantiques o`u on a choisi les problèmes de satisfaction de contrainte conservatrices dans lesquels les valeurs autorisées peuvent être restreintes de manière arbitraire, et une technique de décomposition de domaines guidée par la sémantique des contraintes de distance. D'après l'´etude qu'on a fait, nous avons conclu´e que les méthodes de décomposition sémantique sont plus efficace que les méthodes structurelles.