Kasdien naudojate „Google Maps“, bet tikriausiai nežinote, kaip ji iš tiesų veikia

Vairuotojui pakanka kelių sekundžių, kad „Google Maps“ ar kita navigacijos programėlė pasiūlytų optimalų maršrutą per visą žemyną. Tačiau už šio, atrodytų, paprasto veiksmo slypi viena sudėtingiausių kompiuterių mokslo problemų – trumpiausio kelio paieška milžiniškuose kelių tinkluose.

Norint teoriškai išbandyti visas galimas keliones nuo Niujorko iki San Fransisko Šiaurės Amerikos kelių tinkle, tektų nagrinėti maždaug 10 laipsniu 220 maršrutų. Net tikrindami milijardą kelių per sekundę, tai truktų daugiau nei 10 laipsniu 200 metų. Tad akivaizdu, kad „brutalios jėgos“ metodas čia neįmanomas.

Trumpiausio kelio paieškos pradžia

Šiuolaikinių maršrutų skaičiavimo šerdyje – Edsgerio Dijkstros darbas. 1956 metais, dirbdamas su ankstyvuoju kompiuteriu ARMAC Nyderlanduose, jis ieškojo aiškaus, paprasto pavyzdžio, galinčio parodyti, ką apskritai gali kompiuteriai.

Vaikščiodamas po Amsterdamą ir gerdamas kavą, jis sugalvojo uždavinį: „Koks trumpiausias kelias iš Roterdamo į Groningeną?“. Miestai ir keliai buvo pavaizduoti kaip grafas – taškai ir juos jungiančios briaunos su atstumų svoriais.

Dijkstra pastebėjo, kad paprastas paieškos būdas, kai iš pradžių tikrinami visi vieno žingsnio, po to dviejų, trijų žingsnių atstumai, tinka tik tada, kai visi keliai vienodo ilgio. Realiose kelių sistemose taip nėra, todėl reikėjo algoritmo, kuris atsižvelgtų į skirtingus svorius.

Jo sukurtas metodas šiandien žinomas kaip Dijkstros algoritmas. Jis kiekvienam taškui priskiria dabartinę trumpiausio kelio kainą nuo pradžios. Visų pirma pasirenkamas mazgas su mažiausia kaina, atnaujinami jo kaimynų atstumai, tada procesas kartojamas. Taip garantuojama, kad kai tikslas pirmą kartą pažymimas kaip „galutinai apskaičiuotas“, gautas kelias iš tiesų yra trumpiausias.

Nuo teorijos iki miestų žemėlapių

Nors Dijkstros algoritmas laikomas elegantišku ir patikimu, vien jo nepakanka pasauliniams žemėlapiams. Šiaurės Amerikos kelių tinkle yra daugiau kaip 64 milijonai sankryžų, ir gerai optimizuotas algoritmas vidutiniškai gali veikti apie 7 sekundes vienai užklausai.

Iš pirmo žvilgsnio tai atrodo priimtina, bet paslaugoms, kurios vienu metu aptarnauja milijonus vartotojų, septynios sekundės yra per daug. Be to, daugeliui kelionių reikia optimizuoti ne atstumą, o laiką, atsižvelgiant į greičio ribojimus ir transporto srautus.

Siekiant paspartinti paiešką, buvo sukurta vadinamoji A* (A-star) paieška – tai praplėstas Dijkstros algoritmas, naudojantis euristiką. Ji kiekvienam taškui prideda apytikslį tiesų atstumą iki tikslo, taip tarsi „baudžiant“ žingsnius netinkama kryptimi ir verčiant paiešką judėti labiau „žmogiškai“ – maždaug tikrojo tikslo link.

Tokie metodai ypač populiarūs vaizdo žaidimuose ir robotikoje, kur svarbu greitai rasti padorų kelią dvimatėje erdvėje. Tačiau kai optimizuojamas kelionės laikas, o ne kilometrai, į euristiką reikia įtraukti greičio apribojimus ir tai tampa sudėtinga. A* tokiais atvejais dažnai net pralaimi gerai sureguliuotam Dijkstros algoritmui.

Hierarchijos ir „sutrumpinti“ keliai

Norint pasiekti sekundės dalių užklausų laikus, reikia pasinaudoti tuo, kaip iš tikrųjų atrodo kelių tinklai. Mes kasdien žinome, kad pirma važiuosime mažomis gatvėmis, po to išvažiuosime į magistralę, o prie tikslo vėl nusileisime į vietinių gatvių lygį. Taigi keliams būdinga hierarchija.

Ankstyvosios automobilių navigacijos sistemos hierarchijas kūrė rankiniu būdu: magistralės, pagrindiniai keliai, siauri vietiniai keliai. Algoritmas pirmiausia ieškodavo trumpiausių maršrutų žemiausiu lygiu, tada kildavo aukštyn, bet tokį klasifikavimą buvo sunku padaryti tiksliai ir garantuoti, kad nebus praleistas geresnis maršrutas.

Šiuolaikiniai metodai hierarchiją išgauna automatiškai, analizuodami patį grafą. Vienas svarbiausių požiūrių – vadinamosios sutrauktos hierarchijos. Idėja tokia: kiekvienam mazgui priskiriamas svarbos rangas pagal tai, kiek trumpiausių kelių per jį praeina. Sankryža, jungianti dvi magistrales, yra itin svarbi, o akligatvis – menkai reikšmingas.

Vėliau, pradedant nuo mažiausiai svarbių mazgų, jie tarsi „sulankstomi“, tarp aukštesnio rango taškų pridedant trumpinančias jungtis. Jei trumpiausias kelias tarp dviejų magistralių eina per smulkias gatveles, algoritmas iš anksto įterpia vieną „sutrumpintą“ briauną su tokia pačia kaina, kad paieška vėliau nebeturėtų naršyti po visas detales.

Taip sudaroma daug sluoksnių hierarchija, kurioje ilgi maršrutai skaičiuojami daugiausia aukštame lygyje, aplenkiant didžiąją dalį vietinių gatvių. Paieška vyksta abiem kryptimis – nuo pradžios ir nuo tikslo – ir susitinka aukštesniame tinkle, naudodama tik svarbiausias sankryžas.

Nuo sekundžių iki mikrosekundžių

Praktiškuose bandymuose sutrauktos hierarchijos leido kelių paiešką Šiaurės Amerikos tinkle paspartinti dešimtis tūkstančių kartų, palyginti su klasikiniu Dijkstros algoritmu. Vietoje maždaug 7 sekundžių, užklausos trukmė sudaro vos kelis šimtus mikrosekundžių, o aplankytų mazgų skaičius sumažėja nuo dešimčių milijonų iki kelių tūkstančių.

Tokį greitį leidžia pasiekti brangesnis paruošiamasis etapas. Iš pradžių sudaroma hierarchija ir apskaičiuojamos visos „sutrumpintos“ jungtys. Šis žingsnis gali trukti daugiau nei valandą, tačiau jį reikia kartoti tik pasikeitus kelių tinklui. Vėliau, atnaujinant svorius dėl eismo ar apribojimų, pakanka kelių sekundžių.

Nors didžiosios kompanijos, tokios kaip „Google“ ar „Apple“, neskelbia tikslių naudojamų algoritmų, mokslinėje literatūroje sutrauktos hierarchijos laikomos vienu realistiškiausių ir efektyviausių sprendimų pasaulinio masto navigacijai.

Įdomu tai, kad visų šių sudėtingų metodų šerdyje vis dar veikia Dijkstros idėja, sugalvota per dvidešimt minučių Amsterdamo kavinėje. Pats Dijkstra mėgo kartoti, kad „paprastumas yra būtina patikimumo sąlyga“ – ši nuostata iki šiol lemia, kaip kuriamos mūsų kasdienybės technologijos.