Abstract:
Plusieurs techniques de la résolutions des problèmes de satisfaction de contraintes ont
_été développé durant les quarante dernières années. Ces techniques peuvent être divisées
grossièrement en deux catégories, ceux basés sur la recherche avec backtrack et ceux basés sur la propagation de contraintes. Pour les deux approches, la complexité des algorithmes est exponentielle en la taille du problème. Afin de réduire cette complexité, on a essayé d'extraire des classes de CSP dites tractable dont celle des CSP acyclique fait partie.
Ainsi, La recherche est dirigée vers un autre axe qui consiste à décomposer la stuc-
ture d'un CSP qui est un graphe ou plus généralement un hypergraphe en une structure
arborescente de largeur bornée.
De nombreuses méthodes de décomposition structurelle ont été développées, nous nous
sommes intéressés à la méthode de décomposition hypetree qui généralise toutes les autres méthodes.
Il a été prouvé qu'un CSP dont la structure est acyclique peut être résolu en un temps
polynomial ce qui met en accent l'importance de l'étape de décomposition. Cependant ce
résultat théorique est confronté à de nombreux problèmes lors de sa mise en œuvre parmi
lesquelles le coût du travail réalisé au niveau de chaque nœud de l'arbre qui est parfois prohibitif en terme de temps et d'espace.
