Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 3 Janvier 2006

Recherches hybrides dans les reseaux de contraintes ponderees

par 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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr