211service.com
Datavetare har hittat den längsta raka linjen du kan segla utan att träffa land
Redan 2012 dök en nyfiken debatt upp på diskussionswebbplatsen Reddit, specifikt på en subreddit som heter /r/MapPorn. Här publicerade användaren Kepleronlyknows en karta över världen som påstod sig visa den längsta navigerbara raka vägen över vatten utan att träffa land. Rutten började i Pakistan och följde en stor cirkel under Afrika och Sydamerika tills den träffade östra Ryssland.
Inlägget skapade stor debatt, med mycket huvuden och tafsande över sjökort och jordklot. Den stora frågan var om påståendet var korrekt – kunde det finnas en annan rätlinjeväg över vatten som var längre men oavbruten av land av något slag? Samtidigt uppstod samma fråga för land – vilken var den längsta rätlinjevägen utan avbrott av sjöar eller hav?
För kartografer är det klart att svaren måste följa en stor cirkel: en båge längs en av de många största imaginära cirklarna som kan ritas runt en sfär. Stora cirklar följer alltid den kortaste vägen mellan två punkter på en sfär. Men hur hittar man de stora cirklarna som innehåller lösningarna?
Den längsta raka landresan på jorden.
Vi har nu ett svar tack vare Rohan Chabukswars arbete vid United Technologies Research Center i Irland och Kushal Mukherjee vid IBM Research i Indien. De här killarna har utvecklat en algoritm för att beräkna den längsta raka vägen på land eller till sjöss.
Ett sätt att lösa detta problem är med brute force—mätning av längden på alla möjliga räta linjer över land och vatten. Detta skulle vara minst sagt tidskrävande. En global karta med en upplösning på 1,85 kilometer har över 230 miljarder storcirklar. Var och en av dessa består av 21 600 individuella poäng, vilket gör totalt över fem biljoner poäng att ta hänsyn till.
Den längsta raka sjöresan utan att träffa land.
Men Chabukswar och Mukherjee har utvecklat en snabbare metod med hjälp av en algoritm som utnyttjar en teknik som kallas branch and bound.
Detta fungerar genom att överväga potentiella lösningar som grenar på ett träd. Istället för att utvärdera alla lösningar kontrollerar algoritmen den ena grenen efter den andra. Det kallas förgrening, och det är i huvudsak detsamma som en brute-force-sökning. Men en annan teknik, kallad bounding, minskar uppgiften avsevärt. Varje gren innehåller en delmängd av potentiella lösningar, varav en är den optimala lösningen. Tricket är att hitta en egenskap hos delmängderna som beror på hur nära lösningarna kommer den optimala.
Den gränsande delen av algoritmen mäter denna egenskap för att avgöra om delmängden av lösningar är närmare det optimala värdet. Om det inte är det, ignorerar algoritmen denna gren helt. Om det är närmare blir detta den bästa delmängden av lösningar, och nästa gren jämförs mot den.
Denna process fortsätter tills alla grenar har testats och avslöjar den som innehåller den optimala lösningen. Förgreningsalgoritmen delar sedan upp denna gren i mindre grenar och processen upprepas tills den kommer fram till den enda optimala lösningen.
Knepet som Chabukswar och Mukherjee har fulländat är att hitta en matematisk egenskap hos storcirkelvägar som avgränsar den optimala lösningen för räta banor. De skapar sedan en algoritm som använder denna för att hitta den längsta vägen.
Algoritmen gav den längsta vägen på cirka 10 minuters beräkning för vattenväg och 45 minuters beräkning för landväg på en vanlig bärbar dator, säger forskarna.
Det visar sig att Kepleronlyknows var helt korrekt. Den längsta raka vägen över vatten börjar i Sonmiani, Balochistan, Pakistan, passerar mellan Afrika och Madagaskar och sedan mellan Antarktis och Tierra del Fuego i Sydamerika, och slutar i Karaginsky-distriktet, Kamchatka Krai, i Ryssland. Den är 32 089,7 kilometer lång.
Denna väg är visuellt densamma som den hittas av kepleronlyknows , vilket bevisar hans [sic] påstående, säger Chabukswar och Mukherjee.
Den längsta vägen över land går från nära Jinjiang, Fujian, i Kina, väver genom Mongoliet Kazakstan och Ryssland och når slutligen Europa för att avsluta nära Sagres i Portugal. Totalt passerar rutten genom 15 länder över 11 241,1 kilometer.
Frågan är nu: vem blir den första att göra dessa resor, när och hur?
Ref: arxiv.org/abs/1804.07389 : De längsta raka banorna på vatten eller land på jorden