Problème du plus court chemin avec poids évidentiels
Tuan-Anh Vu  1@  , Sohaib Afifi  1@  , Eric Lefèvre  1@  , Frédéric Pichon  1@  
1 : Laboratoire de Génie Informatique et dÁutomatique de lÁrtois
Université d'Artois : UR3929

Nous étudions le problème du plus court chemin d'une source unique à une destination unique dans un graphe où l'information sur les poids des arcs est evidentielle. c'est-à-dire modélisée par une fonction de croyance. 

Dans ce contexte, nous considérons trois critères classiques pour comparer les chemins en fonction de leurs poids : le critère d'Hurwicz généralisé, le critère de dominance forte et le critère de dominance faible.

Nous montrons que, selon ces critères, dans le cas particulier où les éléments focaux de la fonction de croyance sont des produits cartésiens d'intervalles, trouver les meilleurs chemins, c'est-à-dire les chemins non dominés, revient à résoudre des variantes connues du problème déterministe du plus court chemin, pour lequel il existe des algorithmes de résolution exacte.

 


Personnes connectées : 3 Vie privée
Chargement...