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.
