Dataforskere har funnet den lengste rette linjen du kan seile uten å treffe land

Tilbake i 2012 dukket det opp en nysgjerrig debatt på diskusjonsnettstedet Reddit, nærmere bestemt på en subreddit kalt /r/MapPorn. Her la brukeren Kepleronlyknows ut et kart over verden som påstår å vise den lengste navigerbare rettlinjede banen over vann uten å treffe land. Ruten begynte i Pakistan og fulgte en stor sirkel under Afrika og Sør-Amerika til den traff det østlige Russland.

Innlegget skapte stor debatt, med mye hodeskraping og poting over diagrammer og jordkloder. Det store spørsmålet var om påstanden var riktig – kunne det være en annen rettlinjet rute over vann som var lengre, men uavbrutt av land av noe slag? Samtidig dukket det samme spørsmålet opp for land - hva var den lengste rettlinjede ruten uten avbrudd av innsjøer eller hav?

For kartografer er det klart at svarene må følge en storsirkel: en bue langs en av de mange største imaginære sirklene som kan tegnes rundt en kule. Store sirkler følger alltid den korteste veien mellom to punkter på en kule. Men hvordan finne de store sirklene som inneholder løsningene?

Den lengste rettlinjede landreisen på jorden.

Vi har nå et svar takket være arbeidet til Rohan Chabukswar ved United Technologies Research Center i Irland og Kushal Mukherjee ved IBM Research i India. Disse karene har utviklet en algoritme for å beregne den lengste rettlinjede banen på land eller sjø.

En måte å løse dette problemet på er med råkraft – å måle lengden på alle mulige rettlinjede sti over land og vann. Dette vil mildt sagt være tidkrevende. Et globalt kart med en oppløsning på 1,85 kilometer har over 230 milliarder storsirkler. Hver av disse består av 21 600 individuelle poeng, noe som utgjør totalt over fem billioner poeng å vurdere.

Den lengste rettlinjede sjøreisen uten å treffe land.

Men Chabukswar og Mukherjee har utviklet en raskere metode ved å bruke en algoritme som utnytter en teknikk kjent som branch and bound.

Dette fungerer ved å vurdere potensielle løsninger som grener på et tre. I stedet for å evaluere alle løsninger, sjekker algoritmen den ene grenen etter den andre. Det kalles forgrening, og det er egentlig det samme som et brute-force-søk. Men en annen teknikk, kalt bounding, reduserer oppgaven betydelig. Hver gren inneholder en undergruppe av potensielle løsninger, hvorav en er den optimale løsningen. Trikset er å finne en egenskap til delmengdene som avhenger av hvor nær løsningene kommer til den optimale.

Den avgrensende delen av algoritmen måler denne egenskapen for å bestemme om delmengden av løsninger er nærmere den optimale verdien. Hvis den ikke er det, ignorerer algoritmen denne grenen fullstendig. Hvis den er nærmere, blir dette den beste delmengden av løsninger, og neste gren sammenlignes med den.

Denne prosessen fortsetter til alle grener er testet, og avslører den som inneholder den optimale løsningen. Forgreningsalgoritmen deler deretter denne grenen opp i mindre grener og prosessen gjentas til den kommer til den optimale løsningen.

Trikset som Chabukswar og Mukherjee har perfeksjonert er å finne en matematisk egenskap til storsirkelbaner som avgrenser den optimale løsningen for rettlinjede baner. De lager så en algoritme som bruker denne til å finne den lengste veien.

Algoritmen returnerte den lengste banen på omtrent 10 minutter med beregning for vannbane, og 45 minutter med beregning for landbane på en standard bærbar datamaskin, sier forskerne.

Det viser seg at Kepleronlyknows var helt korrekt. Den lengste rettlinjede banen over vann begynner i Sonmiani, Balochistan, Pakistan, passerer mellom Afrika og Madagaskar og deretter mellom Antarktis og Tierra del Fuego i Sør-Amerika, og ender i Karaginsky-distriktet, Kamchatka Krai, i Russland. Den er 32 089,7 kilometer lang.

Denne banen er visuelt den samme som ble funnet av kepleronlyknows , og beviser dermed hans [sic] påstand, sier Chabukswar og Mukherjee.

Den lengste veien over land går fra nær Jinjiang, Fujian, i Kina, vever seg gjennom Mongolia Kasakhstan og Russland, og når til slutt Europa for å avslutte nær Sagres i Portugal. Totalt går ruten gjennom 15 land over 11 241,1 kilometer.

Spørsmålet nå er: hvem vil være den første til å gjøre disse reisene, når og hvordan?

Ref: arxiv.org/abs/1804.07389 : Lengste rette linjestier på vann eller land på jorden

gjemme seg