Ett par forskare, ett med United Technologies Research Center, den andra med IBM Research, har utvecklat en algoritm som kan användas för att bestämma den längsta raka linjen över vatten på jorden. I deras papper laddat upp till arXiv förtrycksserver, Rohan Chabukswar och Kushal Mukherjee beskriver deras algoritm och vad den avslöjade.

De två forskarna skapade sin algoritm som svar på ett inlägg av en okänd person på Reddit (han har identifierats som Patrick Anderson)-han lade upp vad han hävdade var den längsta raka havsresa som är möjlig på planeten Jorden. Tillsammans med posten var en grafik som visar den föreslagna direktlinjen, men inget bevis på hur det hittades. Intresserad av förslaget, de två forskarna undrade hur de faktiskt skulle kunna beräkna en sådan linje. De visste att det skulle vara möjligt att göra det med ett brute force -tillvägagångssätt, vilket skulle innebära att mäta längden på varje havsträcka. Men det, de noterade, skulle troligen kräva mer datorkraft än de hade. Med en global karta från NOAA, som erbjöd en upplösning på 1,8 kilometer, de såg att ett brute force -tillvägagångssätt skulle innebära slipning genom data som beskriver över 230 miljarder stora cirklar. Och det skulle innebära att analysera biljoner enskilda datapunkter - helt klart för mycket knas för deras tillgängliga dator. För att minska mängden arbete, de vände sig till matematik - specifikt optimeringsalgoritmer som kallas gren och bundna. Sådana algoritmer minskar sökmängden genom att tilldela rutter till grenar som själva har delmängder av liknande rutter. När algoritmen körs, delmängder analyseras och grenar elimineras, få mängden data som kräver analys tills grenen som håller lösningen hittas.

Genom att koda och köra deras algoritm och mata in kartdata, forskarna fann att det tog bara tio minuter för deras bärbara dator att ge ett svar. Intressant, svaret var detsamma som Anderson gav, som enligt uppgift fick sin information från ett okänt Wiki -inlägg. Linjen går mellan en punkt på en strandlinje i Pakistan ända till en rysk strandlinje - ett avstånd på cirka 32, 089,7 kilometer.

© 2018 Phys.org