Aj vaša dovolenka na Slovensku môže byť data-driven

Pandémia COVID-19 zasiahla do života hádam každého z nás. Aktuálna korona kríza zmenila náš pracovný stereotyp, spôsob trávenia voľného času, ako aj nákupné zvyklosti, doplnila nám šatník o módne kúsky, ktoré by sme si inokedy za žiadnych okolností na seba nedali a mnohým z nás nabúrala aj cestovateľské plány na leto. Ak teda tiež patríte k tým, ktorí tento rok plánujú dovolenkovať na Slovensku, tento článok je práve pre vás!

50 najkrajších miest na Slovensku

Prvým problémom, ktorému budete čeliť pri plánovaní roadtripu po Slovensku, je vybrať si z priam nekonečných možností krásnych miest, ktoré na Slovensku máme. Aj keď vo voľnom čase píšem vlastný cestovateľský blog, priznám sa, že obsahu o Slovensku tam mám pomenej. Oslovil som preto väčších odborníkov, youtuberov Martina a Mimu z projektu Hike the World a tí pre vás, našich čitateľov, zostavili tento exkluzívny zoznam:

Devín, Haluzická tiesňava a Banská Štiavnica

Zoznam by sme mali, teraz nastáva druhý problém. Ako pospájať všetky tieto krásne miesta tak, aby sme strávili čo najmenej času v aute a čo najviac obdivovaním kultúrnych pamiatok a prírodných scenérií. Aj keď sa to na prvý pohľad nemusí javiť ako veľký problém, poďme do toho zapojiť trochu matematiky a kombinatoriky:

• V prvom rade potrebujeme zistiť všetky vzájomné vzdialenosti medzi jednotlivými miestami. Pri 50 miestach je počet možných kombinácií 1225 (kombinácie C₂(50) bez opakovania). Pre zjednodušenie nepredpokladajme, že v opačných smeroch môžu byť kvôli jednosmerkám vzdialenosti trochu iné. Zistiť si 1225 vzdialeností cez Google Maps zvládnete hravo za 2 dni. Tak príjemnú zábavu. 😉
• Druhý krok bude zaujímavejší. Tu potrebujeme usporiadať všetkých 50 bodov, spočítať vzdialenosti medzi nimi a vyhodnotiť, ktorá permutácia je pre nás najvýhodnejšia (permutácie P(50) bez opakovania). Problém je, že takýchto permutácií je pri 50 miestach presne 30.414.093.201.713.378.043.612.608.166.064.768.844.377.641.568.960.512.000.000.000.000. Ak by ste na výpočet a porovnanie všetkých týchto trás chceli použiť bežný domáci počítač, k výsledku by ste sa dostali o pár miliárd rokov neskôr, ako vybuchne naše Slnko… Hmm, mám taký pocit, že vtedy by ste už Bojnický zámok asi len ťažko hľadali.

Bojnický zámok, chalúpky v Čičmanoch a chata pri Zelenom Plese vo Vysokých Tatrách

Problém obchodného cestujúceho

Skôr ako sa na celý roadtrip po Slovensku vykašlete, otvoríte si pivo a pustíte Netflix, poďme sa na to pozrieť očami analytika. Tento matematický problém, ktorý sa snažia matematici vyriešiť už od polovice 19. storočia, sa volá Problém obchodného cestujúceho, aj keď v tomto konkrétnom prípade ho môžme nazvať aj Problém zanieteného cestovateľa, ktorý kvôli korone ostal na Slovensku.

Princíp je nasledovný: je daných N miest, pričom z každého mesta sa dá dostať do N-1 ostatných miest. Každá cesta medzi akýmikoľvek dvoma mestami je ohodnotená číslom, ktoré môže vyjadrovať vzdialenosť, čas, cenu za dopravu a pod. Cieľom obchodného cestujúceho je navštíviť každé mesto práve raz a vrátiť sa do počiatočného mesta, pričom musí absolvovať cestu tak, aby precestoval čo najmenšiu vzdialenosť, strávil na cestách čo najmenej času, resp. zaplatil čo najmenej peňazí za dopravu a podobne.

Ak sa práve teraz zamýšľate nad tým, či existuje iné praktické využitie problému obchodného cestujúceho ako pre potreby tohto článku, tak áno. Vo veľkej miere sa tieto výpočty využívajú v logistike, ale napríklad aj v priemysle – pri posune vŕtacích hlavíc, alebo pri osadzovaní dosiek plošných spojov. A ak tento článok číta nejaká pani poštárka, radi jej data-driven metódou pripravíme optimálnu trasu pre roznos zásielok. 🙂

Hrad Šomoška na hraniciach s Maďarskom, Bardejov a Hriňovské lazy s rozkvitnutými čerešňami

Problém obchodného cestujúceho vyriešený. Čiastočne.

Aby sme mohli absolvovať tento data-driven roadtrip ešte za nášho života, počas existencie Slnečnej sústavy a aktuálneho vesmíru, musíme si pomôcť metódami automatizácie postavenými na programovacom jazyku Python:

• Na zistenie vzdialeností medzi jednotlivými miestami použijeme Google Maps Distance Matrix API. Cena za vytiahnutie 1225 údajov je solídnych $6.13.
• Keďže doposiaľ sa nepodarilo nájsť iné riešenie problému obchodného cestujúceho ako pracné porovnanie všetkých permutácií, najčastejšie sa používa algoritmus, ktorý nájde riešenie najviac sa približujúce ideálnemu. V praxi to funguje tak, že algoritmus si náhodne vytvorí niekoľko trás a postupne z nich vyberá tie najlepšie segmenty. Stále znova a znova, až kým nenájde ideálnu kombináciu. Ak si chcete podrobne preštudovať celý algoritmus, odporúčam vám zdrojový kód od Randyho Olsona, ktorý ma inšpiroval.

Ako vyzerá ideálny roadtrip po Slovensku?

Epický roadtrip naprieč Slovenskom má 2250 km a vo forme GPS súradníc vyzerá takto:

{"48.142670,17.098347"; "48.184379,17.014869"; "48.175494,16.979143"; "48.508137,17.302696"; "48.511678,17.432121"; "48.716956,17.770871"; "48.822100,17.867666"; "49.109642,18.213788"; "49.065015,18.153785"; "48.954627,18.516042"; "49.152036,18.677703"; "49.164826,18.588380"; "49.258038,19.065683"; "49.276688,19.155517"; "49.141956,19.294100"; "49.037849,19.276512"; "48.907948,19.164333"; "49.261213,19.358083"; "49.251630,19.703940"; "49.178585,19.542021"; "48.971791,19.581750"; "48.998349,20.770613"; "48.965905,20.385866"; "49.187835,20.292426"; "49.334647,20.231038"; "49.396960,20.418112"; "49.316753,20.693576"; "49.292359,21.279290"; "49.413725,21.698920"; "49.028549,22.481314"; "48.906996,22.202375"; "48.468620,21.678546"; "48.717289,21.262357"; "48.617608,20.832288"; "48.766110,20.338098"; "48.663693,20.305315"; "48.851971,20.188811"; "48.740106,20.045957"; "48.178794,19.854421"; "48.354324,19.574136"; "48.592918,19.498337"; "48.807737,19.133529"; "48.458827,18.897762"; "48.703508,18.915686"; "48.777655,18.576059"; "48.418966,18.412093"; "48.319087,18.363692"; "48.354884,18.056785"; "47.799005,18.721007"; "47.917495,17.996583"; "48.142670,17.098347"}

Vo forme interaktívnej mapy napríklad takto:

A vo forme videa od Hike the World napríklad takto:

Spolu 2249,9 kilometrov plných dychberúcich scenérií. Cestou navštívite nádherné hrady a zámky a uvidíte kopec výnimočných prírodných unikátov. Aj taký môže byť váš tohtoročný data-driven roadtrip po Slovensku. Tak čo, tešíte sa?