Matematika v každodennom živote: satelitný navigátor

Satelitný navigátor je určite veľmi častým nástrojom a často sa predpokladá, že jeho prevádzkou je iba príjem informácií zo satelitov, ktoré „ukazujú cestu“. V skutočnosti je jeho schopnosť určiť cestu na dosiahnutie ľubovoľného cieľa výsledkom kombinácie rôznych techník, ktoré sa týkajú schopnosti presne identifikovať, kde sa v ktorejkoľvek chvíli nachádzame, dostupnosti presných a aktualizovaných cestných máp predovšetkým schopnosť vypočítať najlepšiu cestu k cieľu. V tomto článku zameriame našu pozornosť na tento posledný bod a vysvetlíme, že na základe tohto výpočtu je veľmi presná matematická teória, „teória grafovČo nám umožňuje pochopiť, ako je možné určiť najkratšiu cestu medzi dvoma bodmi. V praxi vidíme, ako sa abstraktná vedecká predstava stáva základom praktického, skutočného a predovšetkým veľmi užitočného objektu.

Najprv začneme zdola: čo je to graf?

V skutočnosti to nie je nič iné ako množina navzájom prepojených prvkov: každý z prvkov sa nazýva „uzol“ a spojenia sa nazývajú „oblúky“. Príkladom grafu je ten, ktorý obsahuje ako prvky sériu miest navzájom prepojených diaľničnou sieťou: v tomto prípade sú uzlami mestá a oblúky diaľničné úseky medzi samotnými mestami. Graf si môžeme predstaviť ako sériu farebných gulí alebo kruhov (uzlov) spojených navzájom úsečkami (oblúkmi). Oblúk môže byť orientovaný alebo neusmernený: orientovaný oblúk je ten, ktorý umožňuje prechod iba od východiskového uzla k príchodovému uzlu (a nie naopak); neusmernený oblúk je ten, ktorý umožňuje priechod v oboch smeroch. V našom príklade navigátora môže byť ulica považovaná za orientovaný oblúk, ak je jednosmerná, zatiaľ čo ulicu možno považovať za neusmernený oblúk, ak je obojsmerná.

Graf sa považuje za vážený, ak je s každým oblúkom spojená hodnota, ktorá sa nazýva váha. Táto hodnota môže byť všeobecne pozitívna alebo negatívna. S odvolaním sa na predchádzajúci príklad miest a diaľnic môžeme získať vážený graf tak, že každý úsek diaľnice spojíme s jeho dĺžkou v kilometroch. V grafe je teoreticky možné prejsť z uzla A do uzla B niekoľkými rôznymi spôsobmi pomocou rôznych oblúkov, rovnako ako v skutočnosti je možné prejsť z jedného mesta do druhého po rôznych cestách. Potom budeme nazývať „najkratšiu cestu“ „najkratšou cestou“ na pripojenie uzla A k uzlu B.

Pre náš satelitný navigátor je nájdenie cesty medzi počiatočným a koncovým bodom rovnaké ako nájdenie najkratšej cesty v grafe. V matematickej teórii grafov bol problém výpočtu najkratšej dráhy študovaný a analyzovaný zo všetkých hľadísk a je vytvorených veľa algoritmov. Jedným z najpoužívanejších je napríklad Dijkstraov algoritmus, ale existuje veľa ďalších. Preto je na voľbe výrobcu prehliadača, aby si vybral algoritmus, ktorý považuje za najvhodnejší. Pri tejto voľbe treba určite vziať do úvahy, že teória, ktorá je základom hľadania najkratšej cesty medzi dvoma uzlami, môže byť veľmi zložitá, najmä pokiaľ ide o výpočet na veľmi zložitých cestných mapách. Napríklad bol vyvinutý algoritmus A *, ktorý hľadá najkratšiu cestu pomocou „štatistického odhadu“ pre každý uzol; povedané „zložitými slovami“, tento odhad predstavuje apriórne hodnotenie výhody prechodu cez jeden uzol cez druhý na ceste do konečného cieľa. V každom prípade je však podrobnosť algoritmov trochu komplikovaná a vyžaduje špecifické znalosti; Dúfame, že v každom prípade poskytneme základnú víziu problému a možno podnietime záujem o matematickú teóriu s mnohými praktickými dôsledkami pre každodenný život.

Giovanni Calcerano