Simon de Givry (INRA Toulouse)

La recherche en profondeur d’abord de type separation et evaluation qui est habituellement utilisee pour traiter les reseaux de contraintes ponderees a une complexite temporelle asymptotique exponentielle en le nombre de variables du reseau. Une exploitation de la structure d’un reseau, au travers d’un ordre d’elimination des variables ou d’une decomposition arborescente, permet d’obtenir une meilleure complexite temporelle au prix d’une complexite spatiale plus forte. Les recherches hybrides presentees combinent une recherche en profondeur d’abord avec une exploitation de la structure du reseau, conduisant a des algorithmes dont le compromis temps/memoire est parametrable.

Nous montrerons egalement l’impact des nouvelles coherences locales souples pour ces recherches hybrides. Une comparaison experimentale des differentes methodes presentees sera donnee sur des reseaux de contraintes ponderees ainsi que sur des reseaux bayesiens.