Zajímá vás, jak navigační přístroje optimalizují jízdní trasu? V článku vysvětlíme, jak taková optimalizace probíhá, a popíšeme nejběžnější optimalizační metody.
Je třeba vzít na vědomí, že konkrétní použité optimalizační programy v navigačních přístrojích jsou předmětem utajení. Správná optimalizace je totiž klíčem k úspěchu. Neočekávejte tedy popis, jak funguje konkrétní navigátor. Podíváme se na úlohu hledání trasy z obecnějšího hlediska.
Jak člověk hledá cestu
Každý, kdo chce cestovat automobilem s větším zájmem než obyčejné zavazadlo, se běžně zamýšlí nad volbou jízdní trasy. Při rozhodování vycházíme z různých zdrojů informací (mapy, vlastní či cizí zkušenosti, ukazatele lemující silnici) a vyzdvihujeme jiné přednosti. Někdo rád sviští na dálnici, jiný si vychutná jízdu s elegantním průjezdem zatáček a další nedá dopustit na neznámé zkratky. Jeden se drží na cestách, po kterých jezdí takříkajíc odmala, druhý rád poznává nepoznané.
Že se někdy jedná o obtížné rozhodnutí lze ukázat na vášnivých hádkách řidičů (řidičky prominou), která trasa z města A do města B je lepší. Přitom složitost situace (silniční sítě) mezi těmito městy nemusí být obzvlášť velká.
Je-li na mapě zadané startovní a cílové město, pak se při hledání cesty soustředíme přirozeně na oblast mezi nimi. Hledáme zpravidla cestu, která se co nejméně odchyluje od „vzdušné čáry“. Tato volba může být výrazně ovlivněna například horstvem či vodními plochami, kde uvažujeme o cestě údolím či podél břehu. Při pohledu do mapových podkladů nás navíc jejich formát motivuje k výběru zvýrazněných silnic vyšších tříd.
Význam měřítka mapy a zvýraznění silnic vyšších tříd
O jaký problém se jedná
Chceme-li se spokojeně dopravit z jednoho místa na druhé, bereme v potaz dvě věci: dostupnou silniční síť a vlastní kritéria nejvýhodnější trasy.
Samotná síť je pro náročnost volby vhodné trasy zpravidla nejvýznamnější. Čím bohatší je síť na různé druhy propojení, tím náročnější a zajímavější se stává úloha vybrat vhodnou trasu. Příkladem může být cesta z Olomouce do Kyjova. Pokud jste vybaveni dálniční známkou, pojedete zřejmě do Vyškova, kde odbočíte na Bučovice. Posléze si můžete vybrat cestu přes Bučovice a Ždánice, nebo zkusíte štěstí po cestě přes Koryčany. Nemáte-li dálniční známku, pak se situace stane komplikovanější. Můžete jet přes Tovačov, Přerov nebo podél dálnice přes Bedihošť a Výškovice.
Pro kterou trasu se nakonec rozhodnete, je určeno druhou věcí: vašimi kritérii. Podle počtu kritérií rozdělujeme problém na jednokriteriální a vícekriteriální. Je-li pro vás podstatné pouze minimalizovat čas strávený na cestě, jedná se o jednokriteriální úlohu. Chcete-li minimalizovat čas a zároveň ujetou vzdálenost, pak se často jedná o protichůdné požadavky a mluvíme o vícekriteriální úloze. Z Olomouce do Kyjova se nejrychleji dostanete po dálnici, ale nejkratší cesta vede přes Bedihošť (v tomto případě je rozdíl délky obou tras pouze pár kilometrů).
U vícekriteriálních úloh s protichůdnými kritérii a bohatou situací zpravidla neexistuje optimální trasa. Výsledkem optimalizace je více tras, kde některé vyhovují spíše jednomu kritériu a jiné spíše druhému kritériu.
Chceme-li se vícekriteriální optimalizaci vyhnout, je možné vytvořit kombinované kritérium, ve kterém se spojí více jednoduchých kritérií. Provádí se to například pomocí součtu s váhovými koeficienty. Pamatovat si více nalezených variant trasy ale může být výhodné i při jednokriteriální optimalizaci. Při cestě můžeme třeba zjistit, že ve vedlejším městě zrovna probíhá akce, kterou nesmíme minout. Tato odbočka nás pak může přivést na zcela jinou trasu, kterou již můžeme mít v paměti.
Kudy do Střeně? Po dálnici, nebo silnicí druhé třídy?
K rozhodování o trase patří nepochybně také informace, které nemusí být všeobecně dostupné. Může se jednat o kvalitu a upravenost silničního povrchu, množství cyklistů či nákladních automobilů, četnost dopravních problémů, šířka silnice atd. Tyto informace získáváme praktickými zkušenostmi, případně také rozhovory se zkušenými řidiči a dalšími způsoby.
Dvě fáze hledání
Podíváme-li se na hledání optimální trasy mezi dvěma městy trochu blíže, zjistíme, že zde existují dvě fáze. V první fázi neznáme žádnou trasu mezi těmito městy. Když to přeženeme, můžeme se dokonce ptát, jestli je cesta mezi těmito městy vůbec možná. Druhá fáze odpovídá situaci, kdy alespoň jednu trasu mezi městy známe, ale nevíme, zda je optimální.
První fáze probíhá většinou tak, že se s výhodou orientujeme podle směru, ve kterém se druhé město nachází. Je-li startovní i cílové město špatně dostupné, vyplatí se hledat trasu z obou směrů. Samozřejmě s ohledem na směr jízdy.
Druhá fáze může být pro člověka i počítač o dost jednoduší, protože poskytuje srovnání. Můžeme totiž vyřadit všechny trasy, které jsou (nebo by po dokončení byly) horší, než je tato známá.
Jak navigátor hledá cestu
Dnešní běžné navigační přístroje jsou jen hloupé stroje, které umějí opravdu velmi rychle počítat nebo prohledávat databáze. Co přístroj dokáže, je téměř úplně závislé na tom, kdo a jak ho programuje a jaká data jsou do něj vložena. Je třeba všechno jasně definovat: data musí mít přesně dané vlastnosti a kritéria musí být vyčíslitelná.
Silniční síť je pro navigační systém soustava uzlů (křižovatek) a spojů (cest), které tyto uzly vzájemně propojují. Každý uzel musí kromě souřadnic obsahovat alespoň vlastnosti, které řeknou odkud kam lze na něm odbočit. Každý spoj musí mimo jiné udávat, které uzly spojuje a za jakých podmínek lze na něm cestovat.
Uspořádání uzlů a spojů v paměti počítače se zcela liší od mapových podkladů, které používáme my. Počítač udržuje databázi: zásuvku s lístky uzlů a zásuvku s lístky spojů. Nalézt spojení mezi dvěma městy tak představuje procházení těchto zásuvek a lístků mnohokrát dokola. Z lidského hlediska je tedy to, co počítač při hledání cesty provádí, otrocká dřina.
Jak vidí mapu člověk a jak počítač
Metody hledání cesty
Postupy pro hledání optimální trasy, které se do navigačních systémů programují, se v zásadě dělí na deterministické a stochastické. Rozdíl mezi nimi je v použití náhody při prohledávání.
Deterministické postupy náhodu neobsahují. Jsou založené na systematickém prohledávání všech možných tras, přičemž pozornost lze věnovat jen těm, které nejlépe splňují zvolené kritérium. Je-li prohledávaná silniční síť dostatečně jednoduchá, může deterministický algoritmus zaručit nalezení optimální trasy (pokud existuje) v rozumném čase.
Se vzrůstající velikostí a složitostí sítě však bude výpočetní doba potřebná k analýze všech možností narůstat. Dobře navržený deterministický algoritmus bude i nadále dávat řešení v rozumném čase, ale vzdá se tak své nejsilnější zbraně, kterou je jistota nalezení optima. Souhrnně vzato: deterministické algoritmy se hodí pro hledání trasy v malých a přehledných silničních sítích.
Stochastické metody: do hry přichází náhoda
Stochastický postup – oproti deterministickému – pracuje s náhodou a v principu nedává jistotu nalezení optimální trasy. Význam náhody tkví ve způsobu, jakým se provádí prohledávání. Lze říci, že stochastický algoritmus obsahuje dvě funkce: první, která je zodpovědná za systematické zlepšování trasy, a druhou, která trasu změní (i náhodně) bez ohledu na její zlepšení. Náhoda určuje, která funkce je v daný okamžik použita.
Pokud se ptáte, k čemu je to dobré, pak vězte, že u složitých a rozsáhlých silničních sítí může optimální varianta různě zatáčet a vracet se, což při blízkém pohledu může vypadat nesmyslně. Mezi obecně použitelné stochastické metody patří například simulované žíhání a genetické algoritmy. Stochastické metody lze doporučit při vícekriteriálních úlohách, v případech, kdy je silniční síť velmi rozsáhlá a složitá, a dále požadujeme-li na vedení trasy mnoho omezení.
Genetické algoritmy: život v navigaci
Při hledání optima pomocí genetických algoritmů se výpočetní proces vzdáleně připodobňuje evoluční teorii vývoje života. Vytvoří se skupina umělých bytostí, kde každá bytost může být pro nás jednou trasou nebo její částí. Tyto bytosti se mohou vzájemně spojovat, rozmnožovat a může docházet k jejich mutaci.
V tomto umělém světě pak musí existovat selekční tlak, který odpovídá kritériím pro optimální trasu. Pomocí selekčního tlaku přežívají zejména zdatní jedinci, kterými jsou v našem případě vhodné trasy. Selekce také způsobí, že vyřazením některé bytosti vzniká prostor pro nového jedince. Ačkoli celý proces probíhá náhodně, vede rozmnožování a selekční tlak k postupnému přibližování k optimu.
Úplně jim nevěřte
Udělali jste si o optimalizaci trasy přesnější představu? Pokud ano, tak již také víte, že výsledku optimalizace navigačním přístrojem nelze vždy věřit. Mimochodem nikdy nevíte jak prospěšná může být nechtěná zajížďka. Kdo ví co tam na vás čeká…
Reference
- Coveney P., Highfield R., Mezi chaosem a řádem, nakladatelství Mladá Fronta, edice Kolumbus, Praha 2003
- Dijkstrův algoritmus (Wikipedia)
