Une paire de chercheurs, un avec United Technologies Research Center, l'autre avec IBM Research, a développé un algorithme qui peut être utilisé pour déterminer le plus long chemin en ligne droite au-dessus de l'eau sur Terre. Dans leur article téléchargé sur le arXiv serveur de préimpression, Rohan Chabukswar et Kushal Mukherjee décrivent leur algorithme et ce qu'il a révélé.

Les deux chercheurs ont créé leur algorithme en réponse à un message d'un inconnu sur Reddit (il a été identifié comme étant Patrick Anderson) – il a posté ce qu'il prétendait être le plus long voyage océanique en ligne droite possible sur la planète Terre. Le message était accompagné d'un graphique montrant l'itinéraire proposé en ligne directe, mais aucune preuve de la façon dont il a été trouvé. Intrigué par la proposition, les deux chercheurs se sont demandé comment ils pouvaient réellement calculer une telle ligne. Ils savaient qu'il serait possible de le faire en utilisant une approche de force brute, ce qui impliquerait de mesurer la longueur de chaque étendue d'océan. Mais ça, ils ont noté, auraient probablement besoin de plus de puissance informatique qu'ils n'en avaient. Avec une carte globale obtenue de la NOAA, qui offrait une résolution de 1,8 kilomètre, ils ont vu qu'une approche par force brute impliquerait de broyer des données décrivant plus de 230 milliards de grands cercles. Et cela signifierait analyser des billions de points de données individuels, ce qui est clairement trop compliqué pour leur ordinateur disponible. Pour réduire la quantité de travail, ils se sont tournés vers les mathématiques, en particulier, algorithmes d'optimisation appelés branch and bound. De tels algorithmes réduisent la quantité de recherche en attribuant des routes à des branches qui détiennent elles-mêmes des sous-ensembles de routes similaires. Au fur et à mesure de l'exécution de l'algorithme, les sous-ensembles sont analysés et les branches éliminées, vanter la quantité de données à analyser jusqu'à ce que la branche qui détient la solution soit trouvée.

En codant et en exécutant leur algorithme et en entrant les données cartographiques, les chercheurs ont découvert qu'il ne fallait que dix minutes à leur ordinateur portable pour fournir une réponse. De façon intéressante, la réponse était la même que celle donnée par Anderson, qui aurait obtenu ses informations à partir d'un article Wiki inconnu. La ligne va d'un point sur un rivage au Pakistan jusqu'à un rivage russe - une distance d'environ 32, 089,7 kilomètres.

© 2018 Phys.org