211service.com
Computerwetenschappers hebben de langste rechte lijn gevonden die je kunt zeilen zonder land te raken
In 2012 ontstond er een merkwaardig debat op de discussiewebsite Reddit, met name op een subreddit genaamd /r/MapPorn. Hier plaatste de gebruiker Kepleronlyknows een kaart van de wereld die beweerde het langste bevaarbare rechte pad over water te tonen zonder land te raken. De route begon in Pakistan en volgde een grote cirkel onder Afrika en Zuid-Amerika totdat hij Oost-Rusland bereikte.
De post zorgde voor een enorm debat, met veel hoofdbrekens en klauwen over grafieken en wereldbollen. De grote vraag was of de bewering juist was - zou er een andere rechte lijn over water kunnen zijn die langer was maar niet onderbroken door welke aard dan ook? Tegelijkertijd rees dezelfde vraag voor land: wat was de langste rechte lijn die niet werd onderbroken door meren of zeeën?
Voor cartografen is het duidelijk dat de antwoorden een grootcirkel moeten volgen: een boog langs een van de vele grootste denkbeeldige cirkels die om een bol kunnen worden getrokken. Grootcirkels volgen altijd de kortste weg tussen twee punten op een bol. Maar hoe vind je de grote cirkels die de oplossingen bevatten?
De langste landreis in rechte lijn op aarde.
We hebben nu een antwoord dankzij het werk van Rohan Chabukswar bij het United Technologies Research Center in Ierland en Kushal Mukherjee bij IBM Research in India. Deze jongens hebben een algoritme ontwikkeld om het langste rechte pad op land of zee te berekenen.
Een manier om dit probleem op te lossen is met brute kracht: het meten van de lengte van elk mogelijk rechtlijnig pad over land en water. Dit zou op zijn zachtst gezegd tijdrovend zijn. Een wereldkaart met een resolutie van 1,85 kilometer heeft meer dan 230 miljard grootcirkels. Elk van deze bestaat uit 21.600 individuele punten, wat neerkomt op een totaal van meer dan vijf biljoen punten om te overwegen.
De langste zeereis in rechte lijn zonder land te raken.
Maar Chabukswar en Mukherjee hebben een snellere methode ontwikkeld met behulp van een algoritme dat gebruikmaakt van een techniek die bekend staat als branch-and-bound.
Dit werkt door mogelijke oplossingen te beschouwen als takken aan een boom. In plaats van alle oplossingen te evalueren, controleert het algoritme de ene tak na de andere. Dat wordt vertakking genoemd en het is in wezen hetzelfde als zoeken met brute kracht. Maar een andere techniek, begrenzing genaamd, vermindert de taak aanzienlijk. Elke tak bevat een subset van mogelijke oplossingen, waarvan er één de optimale oplossing is. De truc is om een eigenschap van de deelverzamelingen te vinden die afhangt van hoe dicht de oplossingen bij de optimale komen.
Het begrenzende deel van het algoritme meet deze eigenschap om te bepalen of de subset van oplossingen dichter bij de optimale waarde ligt. Als dit niet het geval is, negeert het algoritme deze tak volledig. Als het dichterbij is, wordt dit de beste subset van oplossingen en wordt de volgende tak ermee vergeleken.
Dit proces gaat door totdat alle takken zijn getest, waardoor degene wordt onthuld die de optimale oplossing bevat. Het vertakkingsalgoritme verdeelt deze vertakking vervolgens in kleinere vertakkingen en het proces herhaalt zich totdat het bij de enkele optimale oplossing komt.
De truc die Chabukswar en Mukherjee hebben geperfectioneerd, is om een wiskundige eigenschap van grootcirkelpaden te vinden die de optimale oplossing voor rechte lijnen begrenst. Vervolgens maken ze een algoritme dat dit gebruikt om het langste pad te vinden.
Het algoritme gaf het langste pad terug in ongeveer 10 minuten berekening voor het waterpad en 45 minuten voor het landpad op een standaardlaptop, zeggen de onderzoekers.
Het blijkt dat Kepleronlyknows helemaal gelijk had. Het langste rechte pad over water begint in Sonmiani, Balochistan, Pakistan, loopt tussen Afrika en Madagaskar en vervolgens tussen Antarctica en Tierra del Fuego in Zuid-Amerika, en eindigt in het Karaginsky-district, Kamchatka Krai, in Rusland. Het is 32.089,7 kilometer lang.
Dit pad is visueel hetzelfde als gevonden door kepleronlyweet , waarmee hij zijn [sic] bewering bewijst, zeggen Chabukswar en Mukherjee.
Het langste pad over land loopt van nabij Jinjiang, Fujian, in China, slingert door Mongolië, Kazachstan en Rusland, en bereikt uiteindelijk Europa om te eindigen bij Sagres in Portugal. In totaal gaat de route door 15 landen over 11.241.1 kilometer.
De vraag is nu: wie maakt deze reizen als eerste, wanneer en hoe?
Referentie: arxiv.org/abs/1804.07389 : Langste rechte lijnpaden op water of land op aarde