Calculer le diamètre du réseau routier mondial

Publié par Redbran le 15/12/2015 à 12:00
Source: CNRS/INS2I
Illustration: INRIA
6
Restez toujours informé: suivez-nous sur Google Actualités (icone ☆)

L'équipe-projet commune Inria Gang du Laboratoire d'Informatique Algorithmique: Fondements et Applications (LIAFA - CNRS/Université Paris-Diderot) a calculé récemment le diamètre du réseau routier mondial. Plus qu'un défi calculatoire, il s'agit d'un pas dans la résolution effective des problèmes de distances dans les grands graphes.


Diamètre du
réseau (Un réseau informatique est un ensemble d'équipements reliés entre eux pour échanger des...) routier mondial le plus long


Le diamètre d'un graphe est la distance entre les deux points les plus éloignés du graphe. Dans le réseau routier, la notion de distance qui nous intéresse le plus souvent est le temps (Le temps est un concept développé par l'être humain pour appréhender le...) de trajet. Trouver le diamètre du réseau routier mondial revient donc à trouver deux points tels que le temps de trajet pour aller de l'un à l'autre est maximal. Une fois ces deux points identifiés, on peut alors calculer le plus court trajet qui va de l'un à l'autre pour obtenir, en quelque sorte, le plus long "road trip" possible au monde (Le mot monde peut désigner :). Calculer le diamètre d'un graphe requiert en général de calculer toutes les distances pour toutes paires de nœuds, ce qui est infaisable pour un graphe aussi grand.


Diamètre du réseau routier mondial par continent

C'est un sujet d'actualité qui a donné lieu à de nombreux résultats théoriques montrant la quasi-impossibilité d'un algorithme vraiment efficace sur tous les graphes (temps de calcul proportionnel à la taille de la donnée). Cette impossibilité dépend d'une conjecture SETH (Strong Exponential Time Hypothesis) sur la résolution du problème de satisfiabilité (SAT) qui est central en théorie de la complexité (La théorie de la complexité s'intéresse à l'étude formelle de la difficulté des problèmes en...).


Diamètre du réseau routier mondial par pays

Cependant, l'équipe a développé une algorithmique basée sur des parcours de graphes qui s'avère très efficace sur de nombreux graphes rencontrés en pratique. Les réseaux routiers avec leurs structures très diversifiées fournissent un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection...) de données (Dans les technologies de l'information (TI), une donnée est une description élémentaire, souvent...) de grande taille qui ont permis de tester les algorithmes. Grâce à OpenStreetMap, l'équipe a pu ainsi calculer le diamètre routier du monde (et d'autres parties plus restreintes du réseau routier) et les visualiser. Les algorithmes peuvent être adaptés pour calculer aussi les centres des réseaux, c'est-à-dire les points depuis lesquels on peut atteindre tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou...) autre point (Graphie) en un temps qui soit le plus petit possible. Cependant le calcul des centres s'avère moins efficace que pour le calcul du diamètre de certaines parties du réseau et la prochaine étape consistera donc à l'améliorer. À plus long terme, l'équipe cherche à obtenir des représentations succinctes et algorithmiquement efficaces de toutes les distances dans de tels graphes.

Pour plus d'information voir:
Road network project at Gang
Page générée en 0.481 seconde(s) - site hébergé chez Contabo
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
A propos - Informations légales | Partenaire: HD-Numérique
Version anglaise | Version allemande | Version espagnole | Version portugaise