Informatiker haben die längste gerade Linie gefunden, die man segeln könnte, ohne auf Land zu treffen

Bereits 2012 entstand auf der Diskussionswebsite Reddit eine merkwürdige Debatte, insbesondere auf einem Subreddit namens /r/MapPorn. Hier hat der Benutzer Kepleronlyknows eine Weltkarte gepostet, die angeblich den längsten befahrbaren geradlinigen Weg über Wasser zeigt, ohne Land zu treffen. Die Route begann in Pakistan und folgte einem großen Kreis unter Afrika und Südamerika, bis sie Ostrussland erreichte.

Der Beitrag löste eine große Debatte aus, mit viel Kopfkratzen und Scharren über Diagramme und Globen. Die große Frage war, ob die Behauptung richtig war – könnte es eine andere geradlinige Route über Wasser geben, die länger, aber nicht von Land unterbrochen war? Gleichzeitig stellte sich die gleiche Frage für Land – was war die längste geradlinige Route, die nicht von Seen oder Meeren unterbrochen wurde?

Für Kartografen ist klar, dass die Antworten einem Großkreis folgen müssten: einem Bogen entlang eines der vielen größten imaginären Kreise, die man um eine Kugel ziehen kann. Großkreise folgen immer dem kürzesten Weg zwischen zwei Punkten auf einer Kugel. Aber wie findet man die großen Kreise, die die Lösungen enthalten?

Die längste geradlinige Landreise auf der Erde.

Dank der Arbeit von Rohan Chabukswar vom United Technologies Research Centre in Irland und Kushal Mukherjee von IBM Research in Indien haben wir jetzt eine Antwort. Diese Jungs haben einen Algorithmus entwickelt, um den längsten geradlinigen Weg an Land oder auf See zu berechnen.

Eine Möglichkeit, dieses Problem zu lösen, ist rohe Gewalt – das Messen der Länge aller möglichen geradlinigen Pfade über Land und Wasser. Dies wäre gelinde gesagt zeitaufwändig. Eine Weltkarte mit einer Auflösung von 1,85 Kilometern hat über 230 Milliarden Großkreise. Jeder davon besteht aus 21.600 einzelnen Punkten, sodass insgesamt über fünf Billionen Punkte zu berücksichtigen sind.

Die längste geradlinige Seereise, ohne Land zu treffen.

Aber Chabukswar und Mukherjee haben eine schnellere Methode entwickelt, die einen Algorithmus verwendet, der eine Technik nutzt, die als Branch and Bound bekannt ist.

Dies funktioniert, indem mögliche Lösungen wie Äste an einem Baum betrachtet werden. Statt alle Lösungen auszuwerten, prüft der Algorithmus einen Ast nach dem anderen. Das nennt sich Verzweigung und ist im Wesentlichen dasselbe wie eine Brute-Force-Suche. Aber eine andere Technik, die Bounding genannt wird, reduziert die Aufgabe erheblich. Jeder Zweig enthält eine Teilmenge möglicher Lösungen, von denen eine die optimale Lösung ist. Der Trick besteht darin, eine Eigenschaft der Teilmengen zu finden, die davon abhängt, wie nahe die Lösungen der optimalen kommen.

Der Begrenzungsteil des Algorithmus misst diese Eigenschaft, um zu bestimmen, ob die Teilmenge der Lösungen näher am optimalen Wert liegt. Ist dies nicht der Fall, ignoriert der Algorithmus diesen Zweig vollständig. Wenn es näher ist, wird dies zur besten Teilmenge von Lösungen, und der nächste Zweig wird damit verglichen.

Dieser Prozess wird fortgesetzt, bis alle Zweige getestet wurden und derjenige mit der optimalen Lösung gefunden wurde. Der Verzweigungsalgorithmus teilt diesen Zweig dann in kleinere Zweige auf und der Prozess wiederholt sich, bis er zu der einzigen optimalen Lösung gelangt.

Der Trick, den Chabukswar und Mukherjee perfektioniert haben, besteht darin, eine mathematische Eigenschaft von Großkreispfaden zu finden, die die optimale Lösung für geradlinige Pfade begrenzt. Sie erstellen dann einen Algorithmus, der dies verwendet, um den längsten Pfad zu finden.

Der Algorithmus lieferte den längsten Pfad in etwa 10 Minuten Berechnung für den Wasserpfad und 45 Minuten Berechnung für den Landpfad auf einem Standard-Laptop, sagen die Forscher.

Es stellt sich heraus, dass Kepleronlyknows völlig richtig war. Der längste geradlinige Weg über Wasser beginnt in Sonmiani, Belutschistan, Pakistan, verläuft zwischen Afrika und Madagaskar und dann zwischen der Antarktis und Feuerland in Südamerika und endet im Bezirk Karaginsky in der Region Kamtschatka in Russland. Sie ist 32.089,7 Kilometer lang.

Dieser Pfad ist optisch derselbe wie gefunden von Kepler weiß es , was seine [sic] Behauptung beweist, sagen Chabukswar und Mukherjee.

Der längste Weg über Land verläuft von der Nähe von Jinjiang, Fujian, in China, schlängelt sich durch die Mongolei, Kasachstan und Russland und erreicht schließlich Europa, um in der Nähe von Sagres in Portugal zu enden. Insgesamt führt die Route auf 11.241,1 Kilometern durch 15 Länder.

Die Frage ist nun: Wer wird diese Reisen wann und wie als erster unternehmen?

Ref: arxiv.org/abs/1804.07389 : Längste gerade Linienpfade auf dem Wasser oder Land auf der Erde

verbergen