HD DBT : Hypertree Décomposition pour la résolution des problèmes de satisfaction de contraintes basée sur un Dual Backtracking

Résumé : L'hypertree decomposition généralisée est l'approche la plus générale connue dans la littérature pour identifier des sous classes traitables de problèmes de satisfaction de contraintes (CSPs) n-aires représentés à l'aide d'hypergraphes. Seulement, quoi que sa complexité théorique est bornée par la largeur de la décomposition, la méthode proposée pour la résolution du CSP donné sous forme d'hypertree n'est pas efficace en pratique. Dans ce papier, nous proposons la méthode HD DBT (pour résolution des CSP par un algorithme de type BT sur les tuples guidé par un ordre statique induit par une Hypertree Décomposition) comme une nouvelle approche de résolution des CSPs préalablement décomposés en hypertree généralisée. Nous avons implémenté et expérimenté cette approche. Les résultats de comparaison par rapport à la méthode de résolution des CSPs par hypertree decomposition, connue dans la littérature sont encourageants.