Dataloger har fundet den længste lige linje, du kunne sejle uden at ramme land

Tilbage i 2012 dukkede en nysgerrig debat op på diskussionswebstedet Reddit, specifikt på en subreddit kaldet /r/MapPorn. Her postede brugeren Kepleronlyknows et kort over verden, der foregav at vise den længste sejlbare lige linjesti over vand uden at ramme land. Ruten begyndte i Pakistan og fulgte en stor cirkel under Afrika og Sydamerika, indtil den ramte det østlige Rusland.

Indlægget skabte enorm debat med megen hovedskrabe og poter over søkort og jordkloder. Det store spørgsmål var, om påstanden var korrekt - kunne der være en anden lige linje over vand, der var længere, men uafbrudt af land af nogen art? Samtidig opstod det samme spørgsmål for land - hvad var den længste lige linjerute uafbrudt af søer eller have?

For kartografer er det klart, at svarene skal følge en stor cirkel: en bue langs en af ​​de mange største imaginære cirkler, der kan tegnes rundt om en kugle. Store cirkler følger altid den korteste vej mellem to punkter på en kugle. Men hvordan finder man de store cirkler, der indeholder løsningerne?

Den længste landrejse i lige linje på Jorden.

Vi har nu et svar takket være arbejdet fra Rohan Chabukswar ved United Technologies Research Center i Irland og Kushal Mukherjee hos IBM Research i Indien. Disse fyre har udviklet en algoritme til at beregne den længste retlinjede vej på land eller hav.

En måde at løse dette problem på er ved brute force - måling af længden af ​​enhver mulig retlinet sti over land og vand. Dette ville mildest talt være tidskrævende. Et globalt kort med en opløsning på 1,85 kilometer har over 230 milliarder storcirkler. Hver af disse består af 21.600 individuelle point, hvilket gør i alt over fem billioner point at overveje.

Den længste retlinede sørejse uden at ramme land.

Men Chabukswar og Mukherjee har udviklet en hurtigere metode ved hjælp af en algoritme, der udnytter en teknik kendt som branch and bound.

Dette virker ved at betragte potentielle løsninger som grene på et træ. I stedet for at evaluere alle løsninger, tjekker algoritmen den ene gren efter den anden. Det kaldes forgrening, og det er i bund og grund det samme som en brute-force-søgning. Men en anden teknik, kaldet bounding, reducerer opgaven markant. Hver gren indeholder en delmængde af potentielle løsninger, hvoraf den ene er den optimale løsning. Tricket er at finde en egenskab for delmængderne, der afhænger af, hvor tæt løsningerne kommer på den optimale.

Den afgrænsende del af algoritmen måler denne egenskab for at bestemme, om delmængden af ​​løsninger er tættere på den optimale værdi. Hvis den ikke er det, ignorerer algoritmen denne gren fuldstændigt. Hvis det er tættere på, bliver dette den bedste delmængde af løsninger, og den næste gren sammenlignes med den.

Denne proces fortsætter, indtil alle grene er blevet testet, og afslører den, der indeholder den optimale løsning. Forgreningsalgoritmen deler derefter denne gren op i mindre grene, og processen gentages, indtil den når frem til den enkelte optimale løsning.

Det trick, som Chabukswar og Mukherjee har perfektioneret, er at finde en matematisk egenskab ved storcirkelstier, der afgrænser den optimale løsning for lige linjestier. De laver så en algoritme, der bruger denne til at finde den længste vej.

Algoritmen returnerede den længste vej i omkring 10 minutters beregning for vandvej og 45 minutters beregning for landvej på en standard bærbar computer, siger forskerne.

Det viser sig, at Kepleronlyknows var fuldstændig korrekt. Den længste lige linje over vandet begynder i Sonmiani, Balochistan, Pakistan, passerer mellem Afrika og Madagaskar og derefter mellem Antarktis og Tierra del Fuego i Sydamerika og ender i Karaginsky-distriktet, Kamchatka Krai, i Rusland. Den er 32.089,7 kilometer lang.

Denne sti er visuelt den samme som fundet af kepleronlyknows , hvilket beviser hans [sic] påstand, siger Chabukswar og Mukherjee.

Den længste vej over land løber fra nær Jinjiang, Fujian, i Kina, væver sig gennem Mongoliet, Kasakhstan og Rusland, og når endelig Europa for at afslutte nær Sagres i Portugal. I alt går ruten gennem 15 lande over 11.241,1 kilometer.

Spørgsmålet er nu: hvem vil være den første til at foretage disse rejser, hvornår og hvordan?

Ref: arxiv.org/abs/1804.07389 : Længste lige linjestier på vand eller land på jorden

skjule