Des informaticiens ont trouvé la plus longue ligne droite que vous puissiez naviguer sans toucher terre

En 2012, un curieux débat a émergé sur le site de discussion Reddit, en particulier sur un sous-reddit appelé /r/MapPorn. Ici, l'utilisateur Kepleronlyknows a publié une carte du monde prétendant montrer le plus long chemin navigable en ligne droite sur l'eau sans toucher la terre. La route a commencé au Pakistan et a suivi un grand cercle sous l'Afrique et l'Amérique du Sud jusqu'à ce qu'elle touche l'est de la Russie.

Le message a généré un énorme débat, avec beaucoup de grattements de tête et de piaffer sur les cartes et les globes. La grande question était de savoir si l'affirmation était correcte - pourrait-il y avoir une autre route en ligne droite sur l'eau qui soit plus longue mais ininterrompue par la terre de quelque nature que ce soit ? En même temps, la même question se posait pour la terre : quelle était la plus longue route en ligne droite ininterrompue par des lacs ou des mers ?

Pour les cartographes, il est clair que les réponses devraient suivre un grand cercle : un arc le long de l'un des nombreux plus grands cercles imaginaires pouvant être tracés autour d'une sphère. Les grands cercles suivent toujours le chemin le plus court entre deux points sur une sphère. Mais comment trouver les grands cercles qui contiennent les solutions ?

Le plus long voyage terrestre en ligne droite sur Terre.

Nous avons maintenant une réponse grâce aux travaux de Rohan Chabukswar au United Technologies Research Center en Irlande et de Kushal Mukherjee à IBM Research en Inde. Ces gars-là ont développé un algorithme pour calculer le plus long chemin en ligne droite sur terre ou sur mer.

Une façon de résoudre ce problème consiste à utiliser la force brute - en mesurant la longueur de chaque chemin en ligne droite possible sur terre et sur l'eau. Cela prendrait du temps, c'est le moins qu'on puisse dire. Une carte globale avec une résolution de 1,85 kilomètres compte plus de 230 milliards de grands cercles. Chacun d'eux se compose de 21 600 points individuels, soit un total de plus de cinq billions de points à prendre en compte.

Le plus long voyage en mer en ligne droite sans toucher terre.

Mais Chabukswar et Mukherjee ont développé une méthode plus rapide en utilisant un algorithme qui exploite une technique connue sous le nom de branch and bound.

Cela fonctionne en considérant les solutions potentielles comme des branches sur un arbre. Au lieu d'évaluer toutes les solutions, l'algorithme vérifie une branche après l'autre. C'est ce qu'on appelle la création de branches, et c'est essentiellement la même chose qu'une recherche par force brute. Mais une autre technique, appelée bonding, réduit considérablement la tâche. Chaque branche contient un sous-ensemble de solutions potentielles, dont l'une est la solution optimale. L'astuce consiste à trouver une propriété des sous-ensembles qui dépend de la proximité des solutions par rapport à la solution optimale.

La partie englobante de l'algorithme mesure cette propriété pour déterminer si le sous-ensemble de solutions est plus proche de la valeur optimale. Si ce n'est pas le cas, l'algorithme ignore entièrement cette branche. S'il est plus proche, cela devient le meilleur sous-ensemble de solutions et la branche suivante lui est comparée.

Ce processus se poursuit jusqu'à ce que toutes les branches aient été testées, révélant celle qui contient la solution optimale. L'algorithme de branchement divise ensuite cette branche en branches plus petites et le processus se répète jusqu'à ce qu'il arrive à la solution optimale unique.

L'astuce que Chabukswar et Mukherjee ont perfectionnée consiste à trouver une propriété mathématique des trajectoires orthodromiques qui délimite la solution optimale pour les trajectoires en ligne droite. Ils créent ensuite un algorithme qui l'utilise pour trouver le chemin le plus long.

L'algorithme a renvoyé le chemin le plus long en environ 10 minutes de calcul pour le chemin de l'eau et 45 minutes de calcul pour le chemin terrestre sur un ordinateur portable standard, expliquent les chercheurs.

Il s'avère que Kepleronlyknows avait tout à fait raison. Le plus long chemin en ligne droite au-dessus de l'eau commence à Sonmiani, au Balouchistan, au Pakistan, passe entre l'Afrique et Madagascar, puis entre l'Antarctique et la Terre de Feu en Amérique du Sud, et se termine dans le district de Karaginsky, Kamchatka Krai, en Russie. Il mesure 32 089,7 kilomètres de long.

Ce chemin est visuellement le même que celui trouvé par kepleronlyknows , prouvant ainsi son affirmation [sic], disent Chabukswar et Mukherjee.

Le plus long chemin terrestre part de près de Jinjiang, Fujian, en Chine, traverse la Mongolie, le Kazakhstan et la Russie, et atteint enfin l'Europe pour se terminer près de Sagres au Portugal. Au total, l'itinéraire traverse 15 pays sur 11 241,1 kilomètres.

La question est maintenant : qui sera le premier à faire ces voyages, quand et comment ?

Réf : arxiv.org/abs/1804.07389 : Chemins en ligne droite les plus longs sur l'eau ou sur terre sur la Terre

cacher