Математика у свакодневном животу: сателитски навигатор

Сателитски навигатор је свакако врло уобичајен алат и често се претпоставља да је његов рад једноставно примање информација од сателита који "показују пут". У стварности, његова способност да успостави пут до било ког одредишта резултат је комбинације различитих техника, које се тичу способности прецизне идентификације тачке у којој се налазимо у сваком тренутку, доступности тачних и ажурираних мапа путева и изнад свега , могућност израчунавања најбоље руте до нашег одредишта. У овом чланку фокусираћемо нашу пажњу на ову последњу тачку, објашњавајући да у основи овог прорачуна постоји врло прецизна математичка теорија, "теорија графоваШто нам омогућава да разумемо како је могуће идентификовати најкраћи пут између две тачке. У пракси видимо како апстрактни научни појам постаје темељ практичног, стварног и надасве врло корисног објекта.

Прво, почнимо од дна: шта је графикон?

У стварности, то није ништа друго до скуп елемената који су међусобно повезани: сваки од елемената назива се „чвор“, а везе се називају „лукови“. Пример графикона је онај који као елементе има низ градова међусобно повезаних путем аутопутева: у овом случају чворови су градови, а лукови су сегменти аутопута између самих градова. Графикон можемо замислити као низ обојених куглица или кругова (чворова) повезаних линијама (луковима). Лук може бити оријентисан или неусмерен: оријентисани лук је онај који дозвољава пролаз само од почетног чвора до долазног чвора (а не обрнуто); неусмерен лук је онај који дозвољава пролаз у оба смера. У нашем примеру навигатора, улица се може сматрати оријентисаним луком ако је једносмерна, док се може сматрати неусмереним луком ако је двосмерна.

За графикон се каже да је пондерисан ако је вредност, која се назива тежина, повезана са сваким луком. Ова вредност може генерално бити позитивна или негативна. Позивајући се на претходни пример градова и аутопутева, можемо добити пондерисани графикон повезивањем сваке деонице аутопута са њеном дужином у километрима. На графикону је теоретски могуће ићи од чвора А до чвора Б на неколико различитих начина, користећи различите лукове, баш као што је у стварности могуће ићи из једног града у други различитим путевима. Затим ћемо "најкраћи пут" назвати "најкраћим путем" за повезивање чвора А са чвором Б.

За нашег сателитског навигатора проналажење путање између почетне и крајње тачке је исто као и проналажење најкраће путање унутар графикона. У математичкој теорији графова, проблем израчунавања најкраћег пута је проучаван и анализиран са сваког становишта, а произведено је много алгоритама. Један од најчешће коришћених, на пример, је Дијкстрин алгоритам, али има много других. Стога је произвођач прегледача одабран алгоритам који сматра најприкладнијим. При овом избору свакако се мора узети у обзир да теорија која лежи у потрази за најкраћим путем између два чвора може бити врло сложена, посебно када је у питању прорачун на врло сложеним мапама пута. На пример, развијен је алгоритам А * који тражи најкраћу путању користећи "статистичку процену" за сваки чвор; говорећи „тешким речима“, ова процена представља априорну процену предности проласка кроз један чвор над другим на путу до крајњег одредишта. У сваком случају, улажење у детаље алгоритама постаје донекле компликовано и захтева посебно знање; надамо се да смо у сваком случају дали основну визију проблема и можда подстакли интересовање за математичку теорију са многим практичним импликацијама у свакодневном животу.

Гиованни Цалцерано