Résolution des problèmes de satisfaction de contraintes en exploitant les propriétés structurelles

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.