Informatycy odkryli najdłuższą prostą linię, po której można płynąć bez uderzania w ląd

W 2012 roku na stronie dyskusyjnej Reddit pojawiła się ciekawa debata, a konkretnie na subreddicie o nazwie /r/MapPorn. Tutaj użytkownik Kepleronlyknows zamieścił mapę świata, która rzekomo pokazuje najdłuższą żeglowną ścieżkę w linii prostej nad wodą bez uderzania w ląd. Trasa zaczynała się w Pakistanie i biegła po wielkim kręgu pod Afryką i Ameryką Południową, aż dotarła do wschodniej Rosji.

Post wywołał ogromną debatę, z dużą ilością drapania się w głowę i grzebania w wykresach i globusach. Wielkie pytanie brzmiało, czy twierdzenie było słuszne – czy może istnieć inna prosta trasa nad wodą, która byłaby dłuższa, ale niezakłócona przez jakikolwiek ląd? W tym samym czasie pojawiło się to samo pytanie dla lądu – jaka była najdłuższa trasa w linii prostej, nieprzerwana przez jeziora lub morza?

Dla kartografów jasne jest, że odpowiedzi musiałyby przebiegać po wielkim okręgu: łuku wzdłuż jednego z wielu największych wyimaginowanych okręgów, które można narysować wokół kuli. Wielkie koła zawsze podążają najkrótszą ścieżką między dwoma punktami na sferze. Ale jak znaleźć wielkie kręgi zawierające rozwiązania?

Najdłuższa podróż lądowa w linii prostej na Ziemi.

Teraz mamy odpowiedź dzięki pracy Rohana Chabukswara z United Technologies Research Center w Irlandii i Kushala Mukherjee z IBM Research w Indiach. Ci faceci opracowali algorytm obliczania najdłuższej linii prostej na lądzie lub morzu.

Jednym ze sposobów rozwiązania tego problemu jest brutalna siła — pomiar długości każdej możliwej prostej ścieżki nad lądem i wodą. Byłoby to co najmniej czasochłonne. Globalna mapa o rozdzielczości 1,85 kilometra zawiera ponad 230 miliardów wielkich kręgów. Każdy z nich składa się z 21 600 pojedynczych punktów, co daje łącznie ponad pięć bilionów punktów do rozważenia.

Najdłuższa morska podróż w linii prostej bez uderzania w ląd.

Jednak Chabukswar i Mukherjee opracowali szybszą metodę, korzystając z algorytmu, który wykorzystuje technikę znaną jako branch and bound.

Działa to poprzez rozważenie potencjalnych rozwiązań jako gałęzi na drzewie. Zamiast oceniać wszystkie rozwiązania, algorytm sprawdza jedną gałąź po drugiej. Nazywa się to rozgałęzianiem i jest zasadniczo tym samym, co wyszukiwanie siłowe. Ale inna technika, zwana ograniczaniem, znacznie zmniejsza zadanie. Każda gałąź zawiera podzbiór potencjalnych rozwiązań, z których jedno jest rozwiązaniem optymalnym. Sztuczka polega na znalezieniu właściwości podzbiorów, która zależy od tego, jak blisko rozwiązania zbliżają się do optymalnego.

Ograniczająca część algorytmu mierzy tę właściwość, aby określić, czy podzbiór rozwiązań jest bliższy wartości optymalnej. Jeśli tak nie jest, algorytm całkowicie ignoruje tę gałąź. Jeśli jest bliżej, staje się to najlepszym podzbiorem rozwiązań i porównywana jest z nim następna gałąź.

Proces ten trwa, dopóki wszystkie gałęzie nie zostaną przetestowane, ujawniając tę, która zawiera optymalne rozwiązanie. Algorytm rozgałęziania dzieli następnie tę gałąź na mniejsze gałęzie, a proces powtarza się, aż dojdzie do jednego optymalnego rozwiązania.

Sztuczka, którą Chabukswar i Mukherjee udoskonalili, polega na znalezieniu matematycznej właściwości ścieżek po dużym okręgu, która ogranicza optymalne rozwiązanie dla ścieżek w linii prostej. Następnie tworzą algorytm, który wykorzystuje to do znalezienia najdłuższej ścieżki.

Algorytm zwrócił najdłuższą ścieżkę w ciągu około 10 minut obliczeń dla ścieżki wodnej i 45 minut obliczeń dla ścieżki lądowej na standardowym laptopie - twierdzą naukowcy.

Okazuje się, że Kepleronlyknows miał całkowitą rację. Najdłuższa droga w linii prostej nad wodą zaczyna się w Sonmiani, Beludżystanie, Pakistanie, przechodzi między Afryką a Madagaskarem, a następnie między Antarktydą a Ziemią Ognistą w Ameryce Południowej, a kończy się w Okręgu Karagińskim, Kraju Kamczackim w Rosji. Ma 32 089,7 km długości.

Ta ścieżka jest wizualnie taka sama, jak znaleziona przez kepler tylko wie , potwierdzając w ten sposób jego [sic!] twierdzenie, mówią Chabukswar i Mukherjee.

Najdłuższa droga nad lądem biegnie z okolic Jinjiang, Fujian w Chinach, przecina Mongolię, Kazachstan i Rosję, by wreszcie dotrzeć do Europy, by zakończyć w pobliżu Sagres w Portugalii. Łącznie trasa przebiega przez 15 krajów na odcinku 11 241,1 km.

Teraz pytanie brzmi: kto, kiedy i jak, jako pierwszy wykona te podróże?

Nr ref.: arxiv.org/abs/1804.07389 : Najdłuższe ścieżki w linii prostej na wodzie lub lądzie na ziemi

ukryć