Recherchez sur tout Techno-Science.net
       
Techno-Science.net : Suivez l'actualité des sciences et des technologies, découvrez, commentez
Posté par Redbran le Mardi 15/12/2015 à 12:00
Calculer le diamètre du réseau routier mondial
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.



Le diamètre d’un graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) 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 changement dans le monde.) 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 (En mathématiques, une conjecture est une assertion qui a été proposée comme vraie, mais que personne n'a encore pu démontrer...) SETH (Strong Exponential Time Hypothesis) sur la résolution du problème de satisfiabilité (SAT) qui est central en théorie de la complexité.


Diamètre du réseau routier mondial par pays

Cependant, l’équipe a développé une algorithmique (L'algorithmique est l’ensemble des règles et des techniques qui sont impliquées dans la définition et la conception d'algorithmes, c'est à dire de...) 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 d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un tout », comme...) de données 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 l'univers.) 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

Commentez et débattez de cette actualité sur notre forum Techno-Science.net. Vous pouvez également partager cette actualité sur Facebook, Twitter et les autres réseaux sociaux.
Icone partage sur Facebook Icone partage sur Twitter Partager sur Messenger Icone partage sur Delicious Icone partage sur Myspace Flux RSS
Source: CNRS/INS2I
Illustration: INRIA