211service.com
Datorzinātnieki ir atraduši garāko taisno līniju, ar kuru varētu braukt, neietriecoties zemē
Jau 2012. gadā diskusiju vietnē Reddit izcēlās ziņkārīgas debates, īpaši par subreddit ar nosaukumu /r/MapPorn. Šeit lietotājs Kepleronlyknows ievietoja pasaules karti, kurā ir redzams garākais kuģojamais taisnais ceļš virs ūdens, nesaskaroties ar zemi. Maršruts sākās Pakistānā un sekoja lielam lokam zem Āfrikas un Dienvidamerikas, līdz sasniedza Krievijas austrumu daļu.
Šis ieraksts izraisīja milzīgas diskusijas, kas skrāpēja galvu un pārsteidza diagrammas un globusus. Lielais jautājums bija par to, vai apgalvojums ir pareizs — vai varētu būt cita taisna līnija pa ūdeni, kas būtu garāks, bet bez jebkāda veida sauszemes? Tajā pašā laikā tas pats jautājums radās par sauszemi — kurš bija garākais taisnais maršruts, kuru nepārtrauca ezeri vai jūras?
Kartogrāfiem ir skaidrs, ka atbildēm vajadzētu sekot lielajam lokam: lokam pa vienu no daudzajiem lielākajiem iedomātajiem apļiem, ko var apvilkt ap sfēru. Lielie apļi vienmēr iet pa īsāko ceļu starp diviem sfēras punktiem. Bet kā atrast lielos lokus, kas satur risinājumus?
Garākais taisnās līnijas sauszemes ceļojums uz Zemes.
Tagad mums ir atbilde, pateicoties Rohana Čabuksvara (Rohan Chabukswar) darbam United Technologies Research Center Īrijā un Kushal Mukherjee darbam IBM Research Indijā. Šie puiši ir izstrādājuši algoritmu garākā taisnās līnijas ceļa aprēķināšanai uz sauszemes vai jūrā.
Viens no veidiem, kā atrisināt šo problēmu, ir brutāls spēks — katra iespējamā taisnā ceļa garuma mērīšana virs zemes un ūdens. Tas būtu maigi izsakoties laikietilpīgi. Globālajā kartē ar 1,85 kilometru izšķirtspēju ir vairāk nekā 230 miljardi lielo apļu. Katrs no tiem sastāv no 21 600 atsevišķiem punktiem, kas kopā veido vairāk nekā piecus triljonus punktu, kas jāņem vērā.
Garākais taisnās līnijas jūras ceļojums, neiebraucot zemē.
Bet Chabukswar un Mukherjee ir izstrādājuši ātrāku metodi, izmantojot algoritmu, kas izmanto paņēmienu, kas pazīstams kā filiāle un saistība.
Tas darbojas, ņemot vērā iespējamos risinājumus kā zarus uz koka. Tā vietā, lai novērtētu visus risinājumus, algoritms pārbauda vienu zaru pēc otra. To sauc par atzarošanu, un tas būtībā ir tāds pats kā brutāla spēka meklēšana. Bet cits paņēmiens, ko sauc par ierobežošanu, ievērojami samazina uzdevumu. Katra filiāle satur potenciālo risinājumu apakškopu, no kurām viens ir optimālais risinājums. Viltība ir atrast apakškopu īpašību, kas ir atkarīga no tā, cik tuvu risinājumi ir optimālajam.
Algoritma ierobežojošā daļa mēra šo īpašību, lai noteiktu, vai risinājumu apakškopa ir tuvāk optimālajai vērtībai. Ja tā nav, algoritms pilnībā ignorē šo atzaru. Ja tas ir tuvāk, tas kļūst par labāko risinājumu apakškopu, un nākamā filiāle tiek salīdzināta ar to.
Šis process turpinās, līdz ir pārbaudītas visas filiāles, atklājot to, kurā ir optimālais risinājums. Pēc tam sazarošanas algoritms sadala šo zaru mazākos zaros un process atkārtojas, līdz tiek sasniegts vienīgais optimālais risinājums.
Čabuksvara un Mukherjee pilnveidotais triks ir atrast lielu apļa ceļu matemātisko īpašību, kas ierobežo optimālo risinājumu taisnām takām. Pēc tam viņi izveido algoritmu, kas to izmanto, lai atrastu garāko ceļu.
Pētnieki saka, ka algoritms standarta klēpjdatorā atdeva garāko ceļu aptuveni 10 minūšu laikā, veicot aprēķinus ūdens ceļam un 45 minūšu laikā, veicot aprēķinu zemes ceļam.
Izrādās, ka Kepleronlyknows bija pilnīga taisnība. Garākais taisnās līnijas ceļš virs ūdens sākas Sonmiani, Beludžistānā, Pakistānā, iet starp Āfriku un Madagaskaru un tad starp Antarktīdu un Ugunszemi Dienvidamerikā un beidzas Karaginskas rajonā, Kamčatkas apgabalā Krievijā. Tā garums ir 32 089,7 kilometri.
Šis ceļš vizuāli ir tāds pats kā atrastais keplerons zina , tādējādi pierādot viņa [sic] apgalvojumu, saka Čabuksvars un Mukherjee.
Garākais ceļš pa sauszemi ved no netālu no Jinjiang, Fujian, Ķīnā, vijas caur Mongoliju Kazahstānu un Krieviju un beidzot sasniedz Eiropu, lai finišētu netālu no Sagres Portugālē. Kopumā maršruts šķērso 15 valstis 11 241,1 kilometra garumā.
Tagad jautājums ir: kurš pirmais veiks šos braucienus, kad un kā?
Atsauce: arxiv.org/abs/1804.07389 : garākie taisnās līnijas ceļi uz ūdens vai zemes uz Zemes