Résolution des CSPs par décomposition

Abstract

La résolution des CSPs fait généralement appel à des recherches arborescentes exploitant des améliorations du backtracking , De telles méthodes obtiennent souvent des résultats satisfaisants en pratique. Cependant, leur complexité en temps est bornée par la taille de l'espace de recherche, qui est exponentielle. A cette e et, plusieurs algorithme on été proposées pour la résolution e cace de ces problème parmi les quelles les algorithmes énumératifs. L'algorithme Maintaining Arc Consistency (MAC) est l'un des algorithmes qui donne toujours de meilleurs résultats en pratique. Notre approche consiste à tirer pro t à la fois des avantages des algorithmes énumératifs et de ceux de la décomposition GHD.