Vyhledávání trasy v GPS mapách

Univerzita Karlova v Praze Matematicko-fyzikální fakulta

BAKALÁŘSKÁ PRÁCE

Martin Hykl Vyhledávání trasy v GPS mapách Katedra aplikované matematiky

Vedoucí bakalářské práce: RNDr. Ondřej Pangrác Ph.D. Studijní program: INFORMATIKA Studijní obor: Programování

Praha 2011

Poděkování: V první řadě bych rád poděkoval vedoucímu své práce, doktoru Pangrácovi, za jeho nekonečnou trpělivost a množství dobrých rad a nápadů. Dále pak své rodině a přátelům za psychickou podporu, připomínky a korektury.

Prohlašuji, že jsem tuto bakalářskou práci vypracoval samostatně a výhradně s použitím citovaných pramenů, literatury a dalších odborných zdrojů. Beru na vědomí, že se na moji práci vztahují práva a povinnosti vyplývající ze zákona č. 121/2000 Sb., autorského zákona v platném znění, zejména skutečnost, že Univerzita Karlova v Praze má právo na uzavření licenční smlouvy o užití této práce jako školního díla podle §60 odst. 1 autorského zákona. V Praze dne 4.12.2011

Název práce: Vyhledávání trasy v GPS mapách Autor: Martin Hykl Katedra: Katedra aplikované matematiky Vedoucí bakalářské práce: RNDr. Ondřej Pangrác Ph.D., Katedra aplikované matematiky Abstrakt: Práce pojednává o vyhledávání trasy ve vektorové mapě a o přípravě této mapy k samotnému vyhledávání – tvorbě grafu, připojování waypointů apod. Dále pak o tom, co vlastně chtějí uživatelé vyhledávat, jak jim vyhovět a jestli je to vůbec možné. V závěru práce jsou popisy experimentů, kterými jsem ověřoval některé nápady na zrychlení vyhledávání trasy. Práce také obsahuje uživatelskou dokumentaci k projektu SnailMap verze 2.3b. Klíčová slova: hledání trasy, GPS, vektorové mapy, SnailMap, waypoint

Title: Searching in GPS maps Author: Martin Hykl Department: Department of Applied Mathematics Supervisor: RNDr. Ondřej Pangrác Ph.D., Department of Applied Mathematics Abstract: This work is about routing in maps. There are few topics here: How to prepare a graph from a map, what algorithms can we use, can we really find a useful route for user, and many more. At the end of this work there are descriptions of a few experiments which I used to prove correctness of some ideas how to make routing algorithms faster and better. You can also find a manual to SnailMap 2.3b there. Keywords: routing, GPS, vector maps, SnailMap, waypoint

Obsah Úvod

3

1 Příprava mapy 1.1 Mapa . . . . . . . . . . . . . . . . . . . . . . 1.1.1 Načtení mapy . . . . . . . . . . . . . 1.1.2 Uchování mapy . . . . . . . . . . . . 1.2 Získání grafu . . . . . . . . . . . . . . . . . 1.2.1 Filtry . . . . . . . . . . . . . . . . . 1.2.2 Problémy . . . . . . . . . . . . . . . 1.2.3 Grafy . . . . . . . . . . . . . . . . . 1.2.4 Srovnání z hlediska časové náročnosti 1.2.5 Kontrakce . . . . . . . . . . . . . . . 1.3 Waypointy . . . . . . . . . . . . . . . . . . . 1.3.1 Připojování waypointů ke grafu . . .

. . . . . . . . . . .

4 4 4 4 5 5 5 6 7 7 8 8

. . . . . . . .

12 12 12 12 13 14 14 14 15

3 Uživatelské nároky a praktická stránka problematiky 3.1 Motivace pro hledání cesty . . . . . . . . . . . . . . . . . . . . . . 3.2 Nejkratší vs. nejlepší cesta . . . . . . . . . . . . . . . . . . . . . .

16 16 16

4 Experimenty 4.1 Vliv posílení heuristiky na algoritmus A* . . . . . 4.1.1 Závěr pokusu . . . . . . . . . . . . . . . . 4.2 Nastavení typových penalizací pro hledání nejlepší 4.2.1 Výsledky a pozorování . . . . . . . . . . .

. . . .

18 18 18 21 21

. . . . . . . . . .

24 24 24 25 25 25 26 26 26 26 27

2 Vyhledávání 2.1 Dijkstrův algoritmus . . . . . . . 2.1.1 Popis algoritmu . . . . . . 2.2 Dvousměrný Dijkstrův algoritmus 2.3 A* . . . . . . . . . . . . . . . . . 2.3.1 Popis algoritmu . . . . . . 2.3.2 Heuristiky . . . . . . . . . 2.4 Bi-directional A Star . . . . . . . 2.5 ALT algoritmy . . . . . . . . . .

5 Projekt SnailMap 5.1 O programu . . . . . . . . . . . . 5.2 Systémové požadavky a instalace 5.3 Obecné . . . . . . . . . . . . . . . 5.3.1 První spuštění . . . . . . . 5.3.2 Nastavení . . . . . . . . . 5.4 Seznámení s GUI . . . . . . . . . 5.4.1 Nástroje . . . . . . . . . . 5.4.2 Hlavní menu . . . . . . . . 5.5 Práce s mapou . . . . . . . . . . 5.5.1 Načítání mapy / IMG . . 1

. . . . . . . .

. . . . . . . . . .

. . . . . . . .

. . . . . . . . . .

. . . . . . . .

. . . . . . . . . .

. . . . . . . .

. . . . . . . . . .

. . . . . . . .

. . . . . . . . . .

. . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . cesty . . . . . . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . .

5.5.2 Výběr mapy / IMG . . . . . . . . . . . . 5.5.3 Zavření IMG . . . . . . . . . . . . . . . 5.5.4 Úprava IMG . . . . . . . . . . . . . . . . 5.5.5 Uložení IMG . . . . . . . . . . . . . . . 5.5.6 Úprava mapy . . . . . . . . . . . . . . . 5.5.7 Úpravy mapových objektů . . . . . . . . 5.5.8 Mazání mapových objektů . . . . . . . . 5.6 Práce s POI . . . . . . . . . . . . . . . . . . . . 5.6.1 Otevření souboru . . . . . . . . . . . . . 5.6.2 Zavření souboru . . . . . . . . . . . . . . 5.6.3 Uložení souboru . . . . . . . . . . . . . . 5.6.4 Vytvoření nového bodu / stopy / trasy . 5.6.5 Úprava bodu / stopy / trasy . . . . . . . 5.6.6 Smazání bodu / stopy / trasy . . . . . . 5.6.7 Zaměření bodu / stopy / trasy na mapě 5.7 Vyhledávání . . . . . . . . . . . . . . . . . . . . 5.8 Plánování trasy . . . . . . . . . . . . . . . . . . 5.8.1 Nastavení parametrů plánování . . . . . 5.8.2 Přidání waypointu . . . . . . . . . . . . 5.8.3 Demonstrační mód plánování trasy . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . .

27 27 27 28 28 28 28 28 29 29 29 29 30 30 30 30 31 31 31 31

Závěr

33

Seznam použité literatury

34

Pojmy

35

Seznam použitých zkratek

36

Příloha A

37

Obsah přiloženého CD

40

2

Úvod Vyhledávání cesty je velice starý problém, který řeší každý člověk mnohokrát denně. Pravda, pro naplánování cesty do práce nebo na oběd se většinou obejdeme bez mapy, ale jsou situace, kdy to bez ní opravdu nejde. V takovém případě k hledání cesty obvykle používame metodu „kouknu a vidímÿ, která má ale jednu obrovskou nevýhodu – počítače ji neumějí používat. Proto při automatickém plánování trasy přicházejí ke slovu algoritmy, kterými mapu zpracujeme do čitelné podoby a pak v ní jinými algoritmy vyhledáme cestu. Svou práci jsem zaměřil na plánování trasy na mapě se všemi problémy, které to přináší. První část je věnovaná zpracování mapy – jejímu načtení, uložení a hlavně tomu nejdůležitějšímu: tvorbě grafu, ve kterém pak budeme vyhledávat. To je celkem opomíjený aspekt, zejména proto, že většina map využívá připravený graf, který je v nich uložený. Druhá kapitola je zaměřená na některé běžně používané algoritmy. Jelikož je lze najít v mnoha zdrojích, tato kapitola se specializuje spíš na některé jejich speciální vlastnosti. Další část se věnuje požadavkům uživatele a důležité otázce – lze jim vyhovět? To je nelehký úkol, kterým se zabývá mnoho firem. Bohužel jde vesměs o komerční projekty, jejichž tajemství si firmy pečlivě střeží. Několik dobrých nápadů lze nalézt v [2, 7]. V experimentální části mj. zkouším, jestli se vyplatí vyhledávat suboptimální cestu, pokud to přinese výrazné zrychlení algoritmu. K tomu používám algoritmus A* (kap. 2.3) s posílenou heuristikou. A na úplném konci je uživatelská dokumentace k programu SnailMap. SnailMap je program, určený ke zpracování map a souborů s uživatelskými objekty. Tento program si neklade za cíl nahradit existující software, slouží hlavně k ověření a praktickému vyzkoušení některých postupů, které jsou popsané v této práci. Přílohou této práce jsou zdrojové kódy verze 2.3b.

3

1. Příprava mapy 1.1

Mapa

Vektorové mapy pro GPS lze rozdělit do dvou hlavních kategorií: na topografické a silniční. Topografické mapy (topo-mapy) se hodí do terénu, protože obsahují krajinné prvky, např. lesy a vodní plochy. Silniční mapy obsahují pouze elementy důležité pro navigaci v autě, tj. silnice, města, čerpací stanice apod. Jelikož jde o velké objemy dat, projevuje se, hlavně na topo-mapách, snaha ušetřit paměť snížením přesnosti. Přesnost se snižuje hlavně mimo silnice a občas to vede ke vzniku významných chyb (obr. 1.1) – turistické značky, jež ve skutečnosti vedou po stejné cestě, jsou na mapě mnoho metrů od sebe, křižovatky lesních cest jsou nedotažené apod. Z tohoto důvodu nelze na běžných topo-mapách vyhledávat trasu po turistických značkách, neboť z jejich záznamů není možné sestavit graf odpovídající skutečnosti.

1.1.1

Načtení mapy

První úkol při zpracovávání map je jejich načtení. Mapy pro GPSr Garmin jsou ve formátu IMG, ale pro potřeby projektu SnailMap jsem zvolil formát MP (Polski Formát Map), navržený Stanislawem Kozickim v rámci projektu cGPSmapper [4], protože narozdíl od formátu IMG je MP textový a dobře zdokumentovaný. Pro představu s jak velkými soubory se pracuje, pokusný soubor, okres Benešov z mapy TOPO Czech v 1.20, má v textové podobě více než 8 MB, Praha z téže mapy má přes 10 MB, ale jsou i mapy, které nejsou strukturované na okresy a zdrojový kód pak může mít i přes 200 MB. Při práci na projektu SnailMap se nejvíc osvědčil parser, který čte soubor po řádcích a soustavou if-větví zpracovává informace – jde v podstatě o implementaci automatu. Naopak jakékoliv rozsáhlejší použití regulárních výrazů se ukázalo jako neúnosně pomalé; na zmiňovaném testovacím souboru šlo o rozdíl mezi přibližně 10 s a 20 min.

1.1.2

Uchování mapy

Po úspěšném zvládnutí načítání mapy se objeví další problém, a tím je uskladnění načtených objektů. Těch je několik desítek tisíc v každém okrese (alespoň u topografických map), takže při sebeúspornější implementaci to je nezanedbatelný objem dat. Hlavní část toho objemu obvykle tvoří samotná grafika objektů, alespoň pokud používáme nějaký hotový framework, například QGraphics (případ programu SnailMap). Jediné rozumné řešení, které mě napadlo, spočívalo v rozdělení mapy na menší rámce a načítání grafiky pouze pro objekty uvnitř viditelných rámců. Po opuštění daného rámce program ještě chvíli nechá grafiku načtenou (v bufferu) pro případ, že by se do tohoto rámce vracel, a pak ji smaže. Výhoda tohoto postupu je velká úspora paměti (odhadem přes 60 %), nevýhoda je, že při špatně nastaveném bufferu se příliš často alokuje a uvolňuje paměť. 4

(a) Mapa Garmin TOPO Czech v 1.20.

(b) Mapa z http://mapy.cz.

Obrázek 1.1: Les na souřadnicích N49 52.302 E014 32.448, okres Benešov, srovnání. Další možností úspory paměti je mazání i ořezaných objektů a jejich odkládání na pevný disk (neimplementováno v projektu SnailMap).

1.2

Získání grafu

Samotná vektorová mapa je k nalezení cesty nepoužitelná. Cestu umíme hledat pouze v grafu, takže potřebujeme z mapy udělat co nejdokonalejší graf. Kvůli rychlosti hledání by tento graf měl být co nejjednodušší.

1.2.1

Filtry

První důležitý krok je odstranění prvků, které nás nezajímají. To jsou například všechny polygonální a bodové objekty, dále lineáry, po kterých nemůžeme chodit, např. potoky, železnice, letištní runway, vrstevnice apod., pak také lineáry, po kterých se z nějakého důvodu (např. nízký podvozek, zákaz vjezdu) pohybovat nechceme, třeba lesní cesty. K tomu je nejlepší použít typový filtr, který při vhodné implementaci mapy může být velice rychlý (např. když si kromě jmenných indexačních tabulek pro vyhledávání vedeme i typové). Do budoucího grafu se tak dostanou jenom použitelné objekty.

1.2.2

Problémy

Největší problémy při vytváření grafu z mapy představují mimoúrovňová křížení (např. most přes dálnici) a nedokonalosti mapy (např. obr. 1.1). Nedokonalostem mapy se lze vyhnout tím, že si najdeme lepší mapu, s identifikací mimoúrovňového křížení je to o mnoho těžší. V obecné mapě vůbec není možné jej poznat. Výrazně pomůže zavedení (a respektování) „Pravidla bodu na křižovatceÿ (viz. Pojmy). V dalším textu je popsáno několik metod řešení zmíněných problémů.

5

1.2.3

Grafy

Způsobů, jak z přefiltrované vektorové mapy získat graf, je několik. Program SnailMap používá metodu, kterou považuji za nejchytřejší. Zde jsou navíc zmíněné ještě další dvě, z toho jednu pravděpodobně využívají zařízení Garmin a pravděpodobně i mnohá další. Metoda připraveného grafu Garmin používá k vytváření grafu metodu, která sice vrací nejdokonalejší možné výsledky, ovšem za cenu minimální flexibility a velké pracnosti. Podrobnosti neznám, protože nejsou volně přístupné. Z pouhého pohledu na zdrojový kód mapy a přečtení manuálu k formátu MP [4] je ale vidět, že Garmin využívá předem nadefinovaný graf (má k tomu účelu v kódu zvláštní sekce). Tento postup určitě zajistí, že se do grafu nedostanou žádné vrcholy, které tam nepatří (např. sjezdy z dálnice na most, který vede nad ní apod.), a to i bez dodržení „Pravidla bodu na křižovatceÿ. Vytvoření grafu pro výpočet trasy je otázkou chvilky – graf už je hotový, stačí jej jen načíst. Na druhou stranu se zvýší spotřeba paměti a všechny vrcholy musí přidávat nebo alespoň kontrolovat člověk. K dalším nevýhodám pak patří třeba to, že při úpravě mapy (smazání / přidání / úprava silnice) je nutné opět manuálně opravit graf a konečně, že pro velkou všestrannou náročnost výroby grafu se nevyplatí přidávat méně významné vrcholy, například křížení lesních cest, turistických značek atd. – odtud tvrzení o značně omezené flexibilitě. Segmentová metoda Tento postup využívá program SnailMap. Výsledky nejsou tak dokonalé, jako u metody s připraveným grafem, ale nic se nemusí dělat ručně, algoritmus není závislý na předpřipraveném grafu a do grafu se zahrnou všechny vrcholy, které odpovídají filtru. Na druhou stranu je tento postup velmi závislý na kvalitě mapy a doslova odkázaný na „Pravidlo bodu na křižovatceÿ. Algoritmus vychází z předpokladu, že v místě křížení cest (budoucí vrchol grafu) mají oba lineáry bod, takže bere jeden lineár po druhém, každý rozebere na segmenty podle bodů, jež jej tvoří, a vytvoří tak graf. Ten následně projde a smaže zbytečné vrcholy – ty, skrz které lineár pouze prochází a nevětví / nekříží se. Z předchozího popisu je vidět, že algoritmus mimoúrovňové křížení nemá šanci sám odhalit – jedinou možností je striktní dodržování „Pravidla bodu na křižovatceÿ. Průsečíková metoda Tento algoritmus hledá vrcholy grafu tak, že vybírá průsečíky jednotlivých lineárů. To sice není jednoduché, ale některé frameworky, např. QGraphics, pro to mají zabudované funkce. Původně měl být v programu SnailMap implementován, ale po zvážení všech pro i proti jsem se rozhodl jej nepoužít. Podívejme se teď na jeho výhody a nevýhody oproti ostatním zmiňovaným postupům. Jedna z hlavních výhod je, že po lehké modifikaci dokáže zahladit i některé nedokonalosti mapy, konkrétně špatné křižovatky (obr. 1.2). Další výhodou je, 6

(a) Lineáry stačí lehce modifikovat – rozšířit a případně přidat kruhové oblasti kolem bodů. . .

(b) . . . a může to vyřešit problémy se špatně sestavenými křižovatkami.

Obrázek 1.2: Teoreticky možné řešení špatných křižovatek. že nepotřebuje „Pravidlo bodu na křižovatceÿ – křižovatky hledá pomocí průsečíků, takže body jej nezajímají. Hlavní nevýhodou pak je naprostá neschopnost odhalit mimoúrovňové křížení. Mosty přes dálnici by se daly odhalit zavedením pravidel, určujících, které množiny typů lineárů se mohou křížit (např. „dálniceÿ se smí křížit jenom s „dálničním sjezdemÿ atp.), ale většina případů není takto jednoznačná. A v neposlední řadě může velké problémy způsobit i ona zmiňovaná lehká úprava na vyrovnání chyb v mapě – ta totiž může přidat i hrany, které fyzicky neexistují a v grafu nemají co dělat (např. křižovatka dvou cest, kde jedna vede na skále a druhá pod ní).

1.2.4

Srovnání z hlediska časové náročnosti

Na závěr ještě srovnání, kolik času jednotlivé postupy potřebují na vytvoření grafu. Metoda připraveného grafu je určitě zdaleka nejrychlejší, jelikož graf je už od začátku hotový. Segmentovou metodu bych zařadil na druhé místo. Algoritmus pouze dvakrát projde graf – při prvním průchodu ho buduje, při druhém prořezává. Navíc nikde nic složitého nepočítá, jde o pouhé porovnávání záznamů setříděných podle souřadnic. A za nejpomalejší považuji průsečíkovou metodu. V principu by mohla být rychlejší než segmentová, jelikož jde o jediný průchod seznamem lineárů, při kterém se zjistí průsečíky, jenže je tu podstatný problém s implementací. Nalezení průsečíků lomené čáry s množinou dalších lomených čar není jednoduché a už vůbec ne rychlé. QGraphics framework, využívaný programem SnailMap, na to má zabudovaný algoritmus, ale ten nebyl navržen pro práci s tolika objekty, kolik jich obsahuje mapa. Hledá průsečíky se všemi objekty na mapě, což je při tomto množství neúnosně pomalé.

1.2.5

Kontrakce

Zajímavý způsob jak zmenšit graf, ve kterém vyhledáváme, je kontrakce, případně zjednodušení některých jeho částí.

7

Obrázek 1.3: Trasa navržená programem MapSource. Ve velkém měřítku lze graf podstatně zjednodušit při vyhledávání dlouhé trasy. Pak můžeme vytipovat části grafu, které mají málo společných vrcholů s okolím, tzv. „mostůÿ [6], a předem si připravit optimální trasy pro kažou dvojici těchto mostů. Například když hledáme na celém kontinentě, pak těmito mosty, oddělujícími partity s vyšším stupněm souvislosti, budou hraniční přechody. Těch typicky připadá jen několik desítek na stát, takže spotřeba paměti příliš nevzroste, a pokud start ani cíl vyhledávání neleží uvnitř státu, můžeme tímto celkem jednoduchým podgrafem nahradit složitý a velký původní graf [2].

1.3

Waypointy

Důležitou součástí návrhu trasy jsou takzvané waypointy, nebo česky trasové body. Jde o místa, kterými chce zadavatel projet nebo projít.

1.3.1

Připojování waypointů ke grafu

Motivace - běžné řešení a jeho nevýhody Běžně používané navigační programy volí obvykle poměrně přímočarý přístup – najdou nejbližší silnici nebo jiný lineár, po kterém vyhledávají a spustí na něj z waypointu kolmici. Tento postup má ale vážný nedostatek – nebere v potaz přítomnost nepřekonatelných překážek (např. řeka) mezi waypointem a nejbližším lineárem. Pro demonstraci tohoto nedostatku jsem provedl následující test. Nechal jsem si programem Garmin MapSource vyhledat trasu z bodu nedaleko vysílače Cukrák, odkud byla nejbližší silnice na opačném břehu Berounky (v obci ČernošiceMokropsy), do náhodně zvoleného bodu. Nalezená trasa skutečně vedla přímo přes Berounku k nejbližší silnici (obr. 1.3). Ten samý test jsem zkoušel i na Google-mapy, kde byl výsledek sice korektní, ale jenom proto, že problém neřešil - Google našel trasu až od nejbližší silnice a k výsledku přidal informaci o přímé vzdálenosti k ní.

8

Řešení, navržené pro SnailMap Po zkušenostech, popsaných v předchozí podkapitole, jsem se problémem začal zabývat podrobněji a našel jsem řešení, které tímto nedostatkem netrpí. První věc, která působí problémy, je připojení waypointu pouze přes jednu hranu. Může to vést k nepříjemným efektům v případě, že waypoint je v prostoru mimo komunikace. Nejkratší přípojná hrana pak může vést opačným směrem, než leží následující waypoint, což zbytečně prodlouží trasu (obr. 1.4(a)). Tento problém lze vyřešit přidáním waypointů do grafu ještě před jeho redukcí. Waypoint připojíme tak, že jej hranami spojíme se všemi vrcholy grafu vzdálenými nejvýš r. Pokud do vzdálenosti r žádný vrchol nenajdeme, okruh postupně zvětšujeme o step, ovšem nejvýš na poloměr R, abychom v případě prázdného grafu nespustili nekonečný cyklus (obr. 1.4(b)). Tímto způsobem se v běžných případech vyřeší problém s oklikami, ale pořád ještě zbývá problém s navigací přes nepřekonatelné překážky. Problém s nepřekonatelnými překážkami je možné vyřešit tak, že pro každou přidávanou hranu vyzkoušíme, jestli s nějakým takovým objektem nekoliduje. Pokud ano, nepoužijeme ji. Podobným způsobem by bylo možné i zohlednit prostupnost terénu – například penalizovat hranu podle toho, kolik přetíná vrstevnic atp. Zbývá ještě jeden problém, který dobře ilustruje obrázek 1.4(c). Jak je vidět, program by zde pravděpodobně vybral co nejdelší připojovací hranu v přibližně správném směru, což není dobře. Tento problém se ale dá do značné míry vyřešit přenásobením váhy připojovací hrany nějakým koeficientem, který ji dostatečně znevýhodní oproti normálním hranám v grafu (implementováno ve SnailMapu), případně odstraněním všech připojovacích hran, které kříží nějaký lineár (neimplementováno, ale podle pokusů bych řekl, že je to lepší řešení). Penalizace přípojných hran Při penalizování přípojných hran způsobem, popsaným na konci předchozí podkapitoly, však vyvstává další problém – pokud penalizaci připojovacích hran přeženeme, algoritmus hledá daleko za cílem, dokud se skutečná vzdálenost nevyrovná penalizované. To je do jisté míry v pořádku, ale jen pokud ještě existují nějaké neprozkoumané přístupové cesty k cíli. Tím se nabízí poměrně jednoduché řešení: upravíme vyhledávací algoritmus tak, aby skončil až najde nejkratší cestu do cíle (cíl bude mít status DONE) nebo až najde nejkratší cestu do všech sousedů cíle. V případě, že výpočet skončí na prozkoumaných sousedech, projdeme všechny možnosti a vybereme tu nejkratší. U startovního bodu problémy nejsou, protože není jiná možnost, než použít právě nejvýhodnější přípojnou hranu. Z toho plyne další možné řešení – použití obousměrných algoritmů. A nakonec ještě triviální řešení, a sice nepřehánět penalizaci – stačí koeficient s hodnotou 2 až 3. Implementace a problémy s rychlostí Opět je tu využita funkce pro detekování kolizí, která je velmi pomalá (kap. 1.2.4). Proto je potřeba počet volání této funkce omezit na minimum. Detekce kolizí se 9

A : 12km

A : 10km A : 12km

X

A : 10km

X

X

X

(a) Při použití běžného postupu připojování waypointů hrozí, vznik velké okliky,

X

(b) při použití postupu popsaného v podkapitole 1.3.1 můžeme předpokládat, že k těmto problémům nedojde,

A

B

(c) zato ale může dojít k jiné nepříjemnosti, a sice nadbytečnému zkracování trasy přes zástavbu (trasa A → B).

Obrázek 1.4: Srovnání metod pro připojení waypointu ke grafu. Nalezená cesta vybarvená modře.

10

používá při získání bodů do vzdálenosti r od zpracovávaného waypointu a pak při zjišťování, jestli přidávaná hrana nekoliduje s nějakou nepřekonatelnou překážkou. V první části lze ušetřit výpočetní čas jen omezením počtu iterací. Při původní konfiguraci r = 0, R = 100000 a step = 100 celý výpočet trval několik minut. Proto jsem přešel k rychlejší konfiguraci r = 500, R = 1000 a step = 500. Ve druhé části — při zjišťování kolizí s nepřekonatelnými překážkami — lze ušetřit čas tím, že algoritmus nebude zjišťovat kolize se zakázanými elementy pro všechny nalezené body, ale jen pro ty, které ještě netestoval. To je v programu SnailMap implementováno pomocí množiny bodů, do které se přidá každý zkontrolovaný bod a při příští iteraci jej program rovnou přeskočí. Dalším možným řešením by bylo hledání kolizí ne s kruhem o poloměru r, ale s prstencem o vnějším poloměru r a vnitřním poloměru (r − step), ale to by zbytečně zkomplikovalo kód a oproti předchozímu řešení by to žádné zrychlení nepřineslo (stejný počet volání detekční funkce). A nakonec ještě pomalejší řešení, ač z hlediska estetického vypadá nejlépe – vzít množinu bodů, kolidující s kruhem o poloměru r a odečíst od ní množinu kolidující s kruhem o poloměru (r − step). Tento postup by hledal kolize v první fázi dvakrát místo jednou a to je neúnosné zdržování; kromě toho první postup dělá to samé, jen s pamětí mezi iteracemi.

11

2. Vyhledávání Tato část je zaměřená na některé algoritmy na vyhledávání trasy v grafu. V následujícím textu je použito označení grafů G(V, E), kde V je množina všech vrcholů grafu a E je množina všech hran, a funkce l : V → R, která každému vrcholu v ∈ V přiřadí reálnou hodnotu, vyjadřující vzdálenost vrcholu od startu. Většina algoritmů si pomáhá nastavováním stavů vrcholů. Jelikož se označení stavů zdroj od zdroje liší, je zde uvedeno označení použité v této práci a programu SnailMap: N – NOT VISITED (vrchol, který algoritmus ještě nezkoumal), V – VISITED (vrchol, který již algoritmus navštívil, ale ještě není vyloučeno, že do něj najde lepší cestu), D – DONE (uzavřený vrchol – do něj už žádná kratší cesta neexistuje). Některé zdroje stavy N a V slučují do jednoho (∀v ∈ V , kde stav v je N platí l(v) = ∞) jiné používají odlišné označení, třeba FINISHED místo DONE.

2.1

Dijkstrův algoritmus

Dijkstrův algoritmus je bezesporu nejznámější algoritmus na vyhledávání nejkratší cesty grafem. Je pojmenovaný po svém autorovi, slavném nizozemském informatikovi E. W. Dijkstrovi. Oproti jiným algoritmům, např. Bellman-Fordovu, nedokáže počítat se záporným ohodnocením hran, ale to naštěstí v případě hledání cesty ve skutečné mapě nevadí. Podrobný popis a důkaz konečnosti a korektnosti Dijkstrova algoritmu naleznete například v [1, 5, 8].

2.1.1

Popis algoritmu

Algoritmus vlastně nehledá nejkratší cestu ze startu do cíle, ale pouze počítá délku nejkratší cesty, navíc do všech vrcholů grafu, které jsou startu blíž než cíl. Pokud chceme zjistit, kudy tato nejkratší cesta vede, obvykle se použije jednoduché rozšíření, kdy si do každého vrcholu průběžně ukládáme odkaz na předchozí vrchol na této nejkratší cestě. Cestu pak rekonstruujeme tak, že postupujeme od cíle po odkazech na předka. Dijkstrův algoritmus je velice pomalý, jelikož nepočítá cestu do konkrétního bodu, ale rovnoměrně všemi směry. Naštěstí existuje celá řada jeho rozšíření, z nichž některá jsou popsána v dalším textu.

2.2

Dvousměrný Dijkstrův algoritmus

Základní myšlenka tohoto algoritmu je snížení počtu iterací. Jak je napsáno v předchozí kapitole, Dijkstrův algoritmus hledá nejkratší cestu do všech vrcholů grafu, nezáleží mu tedy na cíli. Toho využívá jeho dvousměrná varianta - paralelně běží dva výpočty, jeden od startu, druhý od cíle, a výpočet skončí ve chvíli,

12

B

3

B

C

1

D

B

1 D

A

3

3

3

3

E

E

(a)

(b)

3

B

C

1

D

C 1 D

A

3

3

3

1

1

A

C

1

1

A

3

3

3

E

E

(c)

(d)

Obrázek 2.1: Typický protipříklad k BD-Dijkstrovu algoritmu – ačkoliv je nejkratší cesta A → D zcela zřejmě {A, B, C, D}, algoritmus vrátí {A, E, D}. Červeně jsou označené vrcholy se stavem DONE vůči A, žlutě vůči D. kdy se tyto dvě „vlnyÿ setkají, tzn. že stav nějakého vrcholu je v obou směrech DONE. Rekonstrukce cesty pak probíhá z tohoto vrcholu oběma směry. Se skončením běhu algoritmu to ale není tak jednoduché – dokazují to obrázky 2.1. Funkční řešení vyžaduje vyhledávat ještě o krok déle (nebo se „dívat dopředuÿ), protože optimální cesta může vést také po hraně mezi vrcholem, který je uzavřený v jednom směru a vrcholem, který je uzavřený v opačném směru [5]. Dále je při implementaci důležité si uvědomit, že reverzní vyhledávání musí postupovat proti směru hran a musí počítat s příslušnými hodnotami váhové funkce. To je důležité zejména v takovém orientovaném grafu, kde obousměrné hrany mají v každém směru jinou hodnotu váhové funkce.

2.3

A*

Podobný algoritmus s názvem A1 v roce 1964 navrhl Nils Nilsson. A1 byl roku 1967 značně vylepšen Bertramem Raphaelem, který svou verzi nazval A2, ale neuměl dokázat optimalitu tohoto algoritmu. Až v roce 1968 dokázal Peter E. Hart, že při použití konzistentní heuristiky A2 vrací vždy optimální cestu. Tuto finální verzi nazval A* [A star], kde * je Kleeneho hvězdička symbolizující jakýkoliv znak [9].

13

2.3.1

Popis algoritmu

Jde o běžný Dijkstrův algoritmus doplněný heuristikou – funkcí h : V → R. Tato funkce určuje výhodnost daného vrcholu. Obecně není dané, jak získat hodnoty funkce h, ale v případě počítání trasy na reálné mapě se doporučuje použít vzdálenost daného vrcholu od cíle v nějaké rozumné metrice (většinou Manhattanské nebo Euklidovské; projekt SnailMap používá Euklidovskou). Po zavedení heuristiky je jediná odlišnost od Dijkstrova algoritmu to, že prioritní fronta neobsahuje vrcholy setříděné podle l(v), ale podle l(v) + h(v). Tato změna výběru zajišťuje, že se z fronty přednostně vybírají vrcholy blíž cíli (pokud máme dobře zvolenou heuristiku) a výrazně se tak zkrátí výpočet.

2.3.2

Heuristiky

Aby algoritmus fungoval tak, jak je popsaný, je nutné, aby heuristika byla konzistentní. O heuristice řekneme, že je konzistentní, pokud pro každou hranu (v, w) z E platí: l(w) − l(v) ≥ h(v) − h(w) Neboli, že heuristika nebude mít na rozhodování větší vliv, než exaktní vzdálenost. Důkaz spadá do teorie potenciálu a můžete jej najít např. v [5]. Z trojúhelníkové nerovnosti vyplývá, že pro případ hledání v mapě heuristika počítající vzdálenost vzdušnou čarou do cíle uvedenou nerovnost splňuje, takže její použití je korektní. Jak to ale vypadá, když vezmeme zmiňovanou vzdálenost do cíle (heuristiku h(v)) a vynásobíme ji nějakým koeficientem k? Pokud bude k menší než 1, vliv heuristiky se sníží, při hodnotě 0 pak výpočet proběhne stejně jako u Dijkstrova algoritmu. Pokud ovšem k zvětšíme tak, že nerovnost přestane platit, algoritmus formálně přestane fungovat. To ale znamená pouze to, že přestane za každých okolností vracet optimální cestu, ne, že úplně přestane pracovat. Případným úplným potlačením funkce l by pak algoritmus hledal pomocí prohledávání do hloubky ve směru k cílovému vrcholu a jelikož by vůbec nebral v úvahu dosavadní délku cesty, vznikaly by kolem překážek zbytečné okliky (pěkně to ukazuje obrázek u [9]), což se v menší míře děje i při zachování l a zvětšení koeficientu k, jak je vidět na experimentu 4.1.

2.4

Bi-directional A Star

Samotný obousměrný A* nefunguje, stejně jako obousměrný Dijkstra. Aby vracel správné výsledky, je potřeba buď upravit podmínky na ukončení běhu algoritmu (jako u BD Dijkstry), nebo použít mnohem přísněji vybranou heuristiku [3]. Při zvětšení k pak obvykle dochází k naprostému selhání algoritmu, kdy se nezřídka vypočítávané trasy minou a program pak beží stejně dlouho jako normální A* a ještě ke všemu najde 2 paralelní trasy.

14

2.5

ALT algoritmy

ALT je označení pro třídu algoritmů, vyhledávajících s využitím tzv. landmarků. Jsou to velice rychlé a efektivní algoritmy, které ale vyžadují celkem náročnou přípravu, související s vytyčením landmarků. Tato přípravná fáze by měla mít nejhůře polynomiální časovou složitost vůči počtu vrcholů – jde zejména o předpočítání vzdáleností každého bodu od každého landmarku. Takže algoritmus běží velice rychle za cenu poměrně dlouhé přípravy, tudíž je použitelný zejména ve chvíli, kdy na jednu úpravu mapy statisticky připadá mnoho vyhledaných tras. Navíc v případě, že mapa není určena k upravování, je možné do ní předpočítané údaje rovnou uložit (je dost možné, že tento postup využívají např. mapy firmy Garmin). O ALT algoritmech se více dozvíte např. v [3] a v referovaných publikacích.

15

3. Uživatelské nároky a praktická stránka problematiky 3.1

Motivace pro hledání cesty

Jelikož mi jde v mé práci zejména o praktické nasazení, zamyslel jsem se i nad situacemi, kdy lidé používají software na hledání cesty, a co od něj přitom očekávají. Zjistil jsem, že v zásadě jsou pouze dvě situace, kdy potenciální uživatel sáhne po plánovacím software a že jeho požadavky jsou v různých situacích diametrálně odlišné: 1. uživatel se ztratil 2. uživatel plánuje cestu Add 1 Uživatel netuší, kde je, jenom ví, že chce být jinde a že se jinam chce dostat rychle a snadno; přitom mu příliš nezáleží na tom, kudy ho navigační zařízení (obvykle GPSr) povede. Add2 V tomto případě uživatel plánuje trasu, o které má již nějakou rámcovou představu. Trasa, navržená programem, by měla co nejvíce odpovídat této představě, přičemž se může od optimální trasy značně lišit. Uživatel totiž přikládá velký význam subjektivním kritériím, jako například „tam je motorest, kde mají dobrou polévkuÿ a „vždycky jsme jezdili tudyÿ, které není možné zahrnout do váhové funkce. Bohužel, do váhové funkce se špatně zahrnují i objektivní kritéria, například kvalita povrchu vozovky nebo dopravní situace.

3.2

Nejkratší vs. nejlepší cesta

Z předchozí podkapitoly vyplývá, že nejkratší cesta často není pro uživatele tou nejvhodnější variantou. Jako příklad lze uvést situaci, kdy se uživatel chce dostat z bodu A do bodu B a na cestě je nějaká nepříliš výhodná zkratka, navíc těžko průjezdná, např. lesní cesta. Uživatel v tomto případě tedy nechce nejkratší cestu, ale nějakou jinou, pořád rozumně krátkou. Pro nedostatek výstižnějších výrazů této cestě budeme říkat nejlepší cesta. Celý problém tedy spočívá v tom, že nejsme schopni algoritmicky nalézt nejlepší cestu (mj. i proto, že jde o subjektivní hodnocení). Takové lokální problémy, jako v předchozím příkladu, lze vyřešit velice snadno pečlivějším použitím filtrů (kap. 1.2.1) – s lesními cestami prostě nebudeme počítat.

16

Problém Ale co když problém, popsaný v předchozím odstavci, nastane ve větším měřítku? Vezměme případ cesty z Prahy do Chorvatska. Drtivá většina lidí jezdí přes Brno, Vídeň, Graz, Maribor a Záhřeb, ačkoliv existuje mnohem kratší cesta přes České Budějovice a Linec. Důvodem, proč tato kratší cesta není tolik využívaná, je to, že její značná část vede po silnicích druhé a třetí třídy a navíc překonává několik pohoří. Bohužel, v tomto případě se při řešení nemůžeme uchýlit k filtrům a odfiltrovat všechno kromě dálnic a rychlostních silnic. Důvody jsou hned dva. Za prvé se dá předpokládat, že uživatel nehledá trasu mezi dvěma body na dálnici, takže by pravděpodobně ocenil, kdyby ho navigační software nejdříve bezpečně na zmiňovanou dálnici navedl – k tomu ovšem potřebuje nějaké vedlejší silnice. A za druhé evropská dálniční síť není zcela spojitá, takže první problémy by nastaly už na úseku Brno ↔ Vídeň, kde dálnice chybí a jezdí se tam po silnicích nižších tříd.

Řešení Jednou možností řešení tohoto problému je vyhledávání podle času. Tuto metodu nabízí mj. zařízení firmy Garmin. Pravděpodobně k tomu využívají maximální povolené rychlosti pro daný typ silnice a na základě toho přepočítávají váhovou funkci. Při psaní projektu SnailMap jsem se tímto postupem inspiroval a navrhl jsem podobný – program umožňuje penalizovat lineáry podle typů tím, že jejich délku vynásobí zadaným koeficientem. Tímto řešením a vyhledáváním podle „časovéÿ váhové funkce se zabývám ve druhém experimentu (kap. 4.2).

Následky Nyní se budeme zabývat tím, jaké následky má řešení, uvedené v minulé podkapitole, na vyhledávací algoritmy. Dijkstrův ani obousměrný Dijkstrův algoritmus to neovlivní, A* ale ano. A* využívá heuristiku — obecně se doporučuje nejkratší možná vzdálenost do cíle — a musí být splněna nerovnost l(w) − l(v) ≥ h(v) − h(w) A právě tato nerovnost může být porušena, pokud použijeme nějaký koeficient menší než jedna (kap. 2.3.2). Takže koeficienty musí být větší nebo rovny jedné. Ale tím potíže také nekončí, protože při volbě dostatečně velkých koeficientů (např. všechny typy budeme násobit 1 000-krát – to je určitě korektní konfigurace) ztrácí heuristika význam a algoritmus se efektivitou i během blíží Dijkstrovi.

17

4. Experimenty 4.1

Vliv posílení heuristiky na algoritmus A*

Tato podkapitola je věnována pokusům s posílením vlivu heuristiky na rozhodování algoritmu A*. Toto posílení s sebou přináší porušení konzistence heuristiky a ztrátu optimality algoritmu na jedné straně a zkrácení výpočtu na straně druhé. Při následujících pokusech bylo k setřídění prioritní fronty použito k ∗ h(v) + l(v). Pokusy jsou rozdělené do dvou kategorií podle toho, jestli šlo o navigaci skrz město (Praha) nebo mezi vesnicemi (okres Benešov). Zvolené body byly vybrány náhodně.

4.1.1

Závěr pokusu

Jak je vidět z tabulek v příloze A a grafů (obr. 4.1, 4.2), počet iterací s rostoucím k klesá, výjimkou jsou pouze situace, kdy algoritmus při výběru cesty narazí na slepou uličku – pak má zvýšení k za následek „zabřednutíÿ hlouběji a tedy zvýšení počtu iterací (obr. 4.1(b)). Délka nalezené cesty s rostoucím k naopak roste; co je ale horší — a co není vidět z tabulek — nalezené cesty se mohou stávat nesmyslnějšími, a to zejména při vyhledávání po venkově. Při k ≫ 1 vznikají totiž zbytečné „okružní jízdyÿ po vesnicích ve směru vyhledávání, čímž klesá užitečnost takovýchto tras. Dle grafů a pokusů optimální hodnota k leží na intervalu I = (1.2; 1.5) – pokud k ∈ I, je běh algoritmu výrazně zkrácený a zároveň nedochází k přílišnému prodloužení oproti optimální cestě. Na grafech je vidět, že ve městě není zvyšování k tak výhodné jako na venkově – pravděpodobně za to může větší hustota grafu, která způsobuje, že při „hladovémÿ výběru algoritmus častěji sáhne po suboptimální variantě. Dále z výsledků experimentu plyne, že čím je vzdálenost startu a cíle menší, tím větší k je výhodné (srovnání obr. 4.1(a) a 4.1(b)).

18

1400

33 iterace délka

1200

32.5 32

1000

800

31

600

30.5

délka cesty (km)

počet iterací

31.5

30 400 29.5 200

29

0

28.5 1

2

3

4

5

6

7

8

9

10

k

(a) Graf k tabulce 5.1 220

17 iterace délka

200

16

180

počet iterací

160 14 140 13 120

délka cesty (km)

15

12 100 11

80 60

10 1

2

3

4

5

6

7

8

9

10

k

(b) Graf k tabulce 5.2 3000

60 iterace délka

2500

59 58 57 56

1500 55 1000

délka cesty (km)

počet iterací

2000

54 53

500 52 0

51 1

2

3

4

5

6

7

8

9

10

k

(c) Graf k tabulce 5.3

Obrázek 4.1: Grafy závislosti počtu iterací a délky trasy na koeficientu k. Okres Benešov (venkov). 19

2500

28 iterace délka

27.5

2000

1500

26.5

26

1000

délka cesty (km)

počet iterací

27

25.5 500 25

0

24.5 1

2

3

4

5

6

7

8

9

10

k

(a) Graf k tabulce 5.4 4000

17.5 iterace délka

3500

17.4 17.3

3000

počet iterací

17.1 2000 17 1500

délka cesty (km)

17.2 2500

16.9 1000

16.8

500

16.7

0

16.6 1

2

3

4

5

6

7

8

9

10

k

(b) Graf k tabulce 5.5 1100

9.5 iterace délka

1000

9

900 8.5

700 8 600 500

délka cesty (km)

počet iterací

800

7.5

400 7 300 200

6.5 1

2

3

4

5

6

7

8

9

10

k

(c) Graf k tabulce 5.6

Obrázek 4.2: Grafy závislosti počtu iterací a délky trasy na koeficientu k. Praha (město). 20

4.2

Nastavení typových penalizací pro hledání nejlepší cesty

Tento experiment je zaměřený na úpravu grafu, konkrétně na násobení váhy hran koeficienty podle typu lineáru, který hrana zastupuje. Cílem je najít takovou sadu koeficientů, aby program našel cestu co nejpodobnější té, kterou by „ručněÿ naplánoval uživatel (kap. 3.2). Bohužel, nejlepší cesta je poměrně subjektivní, takže výsledek nepůjde vyjádřit tabulkou a grafem jako v předchozím experimentu. Dílčí cíle • ověřit, jestli je dostačující penalizace podle maximální povolené rychlosti (= vyhledávání podle času, které pravděpodobně používají některé běžně používané systémy), • ověřit, zda lze tímto způsobem přesvědčit program, aby navigoval hlavně po dálnicích, • zjistit, jestli s touto metodou obecně nejsou nějaké problémy, které jsem při teoretickém zpracování přehlédl nebo podcenil. Na všechny experimenty byl použit algoritmus A* (bez posílené heuristiky).

4.2.1

Výsledky a pozorování

Soubory s trasami, vyhledanými v rámci dílčích experimentů, naleznete na přiloženém CD ve složce EXP2, vč. popisu (soubor README.txt). Penalizace podle maximální povolené / dosažitelné rychlosti Toto nastavení odpovídá vyhledávání trasy podle času, který v ideálním případě potřebujeme k jejímu absolvování. Jako jednotková hodnota koeficientu byla použita rychlost na dálnici – 130 km/h. Ostatní penalizační koeficienty byly přepočítané podle poměru příslušné rychlosti ke 130 km/h (tab. 4.1). Pro zjednodušení experiment nebere v úvahu omezenou rychlost v obcích – tabulka se vztahuje na typy lineárů a ne na konkrétní úseky silnic. Přesné nastavení filtru a penalizací je vidět v tabulce 4.2. Typ komunikace Dálnice Rychlostní silnice Silnice mimo obec Silnice v obci Nezpevněná cesta

Rychlost [km/h] Koeficient 130 1.00 110 1.18 90 1.44 50 2.60 30 4.33

Tabulka 4.1: Tabulka rychlostí a koeficientů Vyhledávání s těmito koeficienty vrátilo velmi dobré výsledky – trasa se držela hlavních silnic kdekoliv to bylo možné a neobsahovala zkratky polními cestami. 21

Typ 1 11 12 2 3 4 5 7 8 9 6 10

Název Major Highway-thick Major Highway Connector-thick Roundabout Principal Highway-thick Principal Highway-medium Arterial Road-medium Arterial Road-thick Alley-thick Ramp Ramp Road-thin Unpaved Road-thin

k 1.00 1.18 1.18 1.44 1.44 1.44 1.44 1.44 1.44 1.44 2.60 4.33

Tabulka 4.2: Nastavení typových penalizací pro mapy TOPO Czech v 1.20 (vyhledávání podle času). Typy jsou převzaté z programu SnailMap. O něco horší byly výsledky ve městě. Při hledání přes Prahu nebylo zlepšení moc výrazné, jak je vidět ve výsledcích pokusu. Vyhledávání hlavně po dálnicích Síť dálnic je hodně řídká, takže pokud má program najít trasu po dálnici, a to pouze metodou znevýhodňování hran podle typu, je třeba ostatní typy znevýhodnit velmi významně. Experimentoval jsem s hledáním trasy Modřany (Praha) → Bubovice (okres Beroun) a „správnouÿ trasu po dálnici program vyhledal až když byly koeficienty z tabulky 4.1 zpětinásobeny (kromě koeficientu dálnice). Trasa pak sice přesně odpovídala té, kterou při absolvování této cesty používáme, ale výpočet byl téměř neúnosně náročný na prostředky – zatímco normální nalezení nejkratší cesty trvalo kolem 2 500 iterací, toto dálniční hledání si vyžádalo více než desetkrát tolik: přes 28 000 iterací. Kromě toho je zřejmé, že čím dále od dálnice se výchozí a cílový bod nacházejí, tím větší koeficienty jsou potřeba. Z předchozího vyplývá, že mnohem lepším řešením je použít rychlostní koeficienty jako v předchozí podkapitole a na nájezd a sjezd z dálnice umístit další waypointy. Problémy při používaní penalizace Prvním problémem, který se objevil, byl koeficient pro připojovací hrany waypointů (kap. 1.3.1). Přípojná hrana penalizovaná doporučenou hodnotou 2.5 byla náhle výhodnější, než hrana zastupující silnici, takže docházelo k efektům podobným tomu na obrázku 1.4(c). Řešením bylo přenásobení připojovacího koeficientu největším typovým koeficientem (nebo druhým největším, pokud je lineárů s největším koeficientem na mapě málo). Pro experimenty jsem zvolil koeficient běžné obecní ulice (2.6); s výsledným připojovacím koeficientem 6.5 opět vše fungovalo správně. Dalším problémem je zpomalení výpočtu. Pravděpodobně je to alespoň částečně způsobené oslabením vlivu heuristiky (kap. 3.2), která je počítána podle 22

vzdálenosti a ne podle času (to by bylo dost obtížné, ne-li nemožné). Při experimentech, kde jsem počet iterací sledoval, šlo při použití „časovéÿ úpravy grafu o zhruba dvojnásobek iterací oproti grafu bez penalizací, při dalším zvětšování penalizačních koeficientů, pak zpomalení výpočtu velmi rychle rostlo. Jediné řešení, které mě napadlo, je využít posílenou heuristiku jako v prvním experimentu. Tím ale při vyhledávání po málo penalizovaných typech silnic (třeba dálnice) riskujeme ztrátu optimality.

23

5. Projekt SnailMap 5.1

O programu

Projekt SnailMap vznikl kvůli nedostatku software pro práci s GPS daty a mapami (Garmin) na UNIXových systémech, nicméně funguje i na systémech Windows. Cílem není nahradit existující programy, například Garmin MapSource, ale spíše doplnit funkce, které stávající programy postrádají a zastoupit je tam, kde nefungují. Verze 2.3b, která je součástí této práce, má oproti verzi 2.3 zablokované nebo přímo odstraněné funkce, které nesouvisí s bakalářským projektem, místo nich má modul pro simulaci algoritmů pro hledání nejkratší cesty v grafu. Co všechno program umí • načítat, zobrazovat a upravovat mapy ve formátu MP (Polski Formát Map) • načítat, zobrazovat a upravovat body, stopy a trasy ve formátech GPX a LOC • vyhledávat v mapách i datových souborech • plánovat trasy Co program neumí • odesílat data do GPSr a přijímat je • načítat a ukládat přímo IMG soubory

5.2

Systémové požadavky a instalace

Verze: 2.3b Jazyk aplikace: EN Programovací jazyk: C++ / Qt 4.6 Operační systém: GNU/Linux Další požadavky: Qt 4.6, WebKit (devel), qmake, g++ Spuštení programu 1. vytvořte si adresář, kam okopírujte soubory se zdrojovými kódy z přiloženého média 2. v tomto adresáři spusťte konzoli 3. zadejte sekvenci příkazů: qmake -makefile; make 4. spusťte pomocí: ./SnailMap2_3b [filename]*, kde filename je adresa souboru POI ve formátu GPX nebo LOC

24

Obrázek 5.1: Pohled na hlavní okno programu SnailMap s načtenou mapou Benešovska a vypnutými panely.

5.3 5.3.1

Obecné První spuštění

Při prvním spuštění program obvykle vypíše varování, že nemůže najít databázové soubory. Je to kvůli konfiguračnímu souboru, který se vytvořil až po pokusu o jeho načtení. Program se pak spustí téměř nefunkční – bez ikon a databází. Stačí jej vypnout a znovu zapnout a všechno je v pořádku. Program se nerestartuje sám proto, že stejně reaguje při ztrátě souborů s databázemi a tam nepomůže restart, ale dodání chybějících / poškozených souborů.

5.3.2

Nastavení

Veškerá nastavení, která si program zapamatuje pro příští spuštění, se nastavují v dialogu Settings; všechna ostatní platí jen pro aktuální sezení. Dialog Settings je poměrně složitý, přesto jsem se pokusil ho udělat co nejsrozumitelněji – jednotlivá nastavení jsou roztříděná do karet podle tématu a na každé kartě je ve spodní části okénko „Advicesÿ, kde jsou zobrazeny tipy a vysvětlivky k prvkům, jejichž funkce není na první pohled zřejmá. Také je většina prvků vybavena „tool-tipyÿ – krátkou informací o účinku prvku, která se zobrazí, když na prvek najedete myší. Dialog Settings otevřete v hlavním menu: Settings → SnailMap settings.

25

5.4 5.4.1

Seznámení s GUI Nástroje

Nástroje lze vybrat ve zvláštní nástrojové liště. Dostupné nástroje a jejich funkce: • Drag – symbol ruky – umožňuje pohybovat mapou • Mark – symbol vlaječky – jedna z možností, jak vytvořit nový POI • Measure – symbol pravítka – slouží k zadávání bodů při využívání nástroje měření vzdálenosti • Select – symbol šipky – slouží k vybrání POI V této liště dále najdete spínač editačního módu (symbol mapy s tužkou).

5.4.2

Hlavní menu

V hlavním menu můžete nalézt položky: • File – slouží k práci se soubory POI • Find – jedna z možností, jak se dostat k panelu pro hledání objektů a plánování trasy • Map – slouží k práci s mapami a IMG • POI / Path / Route – obsahuje nástroje pro práci s uživatelsky zadanými objekty • View – v tomto menu si můžete nastavit, které panely a nástrojové lišty se zobrazí • Tools – obsahuje některé užitečné nástroje, např. měření vzdálenosti • Settings – nastavení • Help – informace o programu a odkaz na webový manuál

5.5

Práce s mapou

Mapy jsou hierarchicky dělené: Mapa obsahuje jednotlivé IMG, které se dělí na různě podrobné vrstvy. Mapa představuje soubor příbuzných IMG souborů a je v programu SnailMap reprezentována soubory formátu SMM. Tento formát není kompatibilní s jinými programy a jde o pouhý seznam adres MP-souborů k načtení. IMG představuje jeden IMG soubor (mapový soubor Garmin). V něm jsou uložené informace o vrstvách a všech objektech. Obvykle jde o mapu nějakého nevelkého územního celku, například v Garmin TOPO Czech v 1.20 má každý okres svůj IMG soubor. Program SnailMap neumožňuje načítat nebo ukládat přímo IMG soubory, je nutné používat „meziformátÿ MP (Polski Formát Map). 26

Každý IMG má až 10 (u Garmin TOPO Czech v 1.20 obvykle 3 – 4) různě podrobných vrstev (číslovaných od 0; nejvyšší musí být vždy prázdná). Při změně přiblížení se pak zvolí příslušná vrstva (pokud vlastníte GPSr s podporou map, víte, o čem mluvím). Platí, že čím nižší číslo má vrstva, tím je podrobnější. Vrstvy jako takové sice můžete nastavovat ručně (pomocí výběru hned vedle výběru IMG), ale nedoporučuje se to (při neopatrné manipulaci by mohlo dojít k selhání programu pro přílišnou spotřebu paměti nebo přílišné nároky na grafiku). Také můžete přenastavit mapováni vrstev na úrovně přiblížení (viz. 5.5.4). Informace o otevřených IMG a mapách můžete na panelu Objects na kartě Maps.

5.5.1

Načítání mapy / IMG

1. v hlavním menu zvolte Map → Load map (Ctrl+M), resp. → Load IMG (Ctrl+I) 2. vyberte soubory, které chcete načíst 3. počkejte, dokud se neobjeví zpráva o načtení požadovaných souborů POZOR! Tato operace může trvat i několik desítek sekund. Před načtením map nebo IMG se ujistěte, že máte dost paměti na RAM – program to nekontroluje a tudíž všechny problémy vzniklé zabráním příliš mnooho paměti řeší systém (obvykle násilným ukončením běhu programu). Je dobré počítat zhruba 10 MB / 1 MB souboru MP. Pokud se během načítání objeví syntaktické chyby v MP souboru, program Vás na ně upozorní. V takovém případě zkontrolujte, zda není soubor poškozený (soubory jsou velké, může snadno dojít ke ztrátě dat, např. při předčasném odpojení přenosového média, ze kterého soubor kopírujtete).

5.5.2

Výběr mapy / IMG

Použijte výběr v nástrojové liště Maps toolbar. Hned vedle najdete ovládání ručního výběru vrstvy.

5.5.3

Zavření IMG

1. zobrazte IMG, který chcete zavřít 2. v hlavním menu zvolte Map → Close current IMG Zavírání IMG má význam zejména z hlediska úspory paměti.

5.5.4

Úprava IMG

1. přejděte na poslední kartu panelu Objects 2. zvolte IMG, který chcete upravit (POZOR – defaultní prázdný IMG „empty imgÿ upravovat nemůžete) 27

3. na zvolený IMG dvojklikněte 4. zobrazí se Vám dialog úpravy IMG – proveďte požadované úpravy a uložte / zrušte změny

5.5.5

Uložení IMG

1. zobrazte IMG, který chcete uložit 2. v hlavním menu zvolte Map → IMG actions → Save current IMG, resp. Save current IMG as... 3. v případě „save as. . .ÿ vyberte kam chcete IMG uložit 4. počkejte na zprávu potvrzující úspěšné uložení POZOR! Tato operace může trvat i několik desítek sekund.

5.5.6

Úprava mapy

Mapě můžete nastavit jenom jméno. 1. dvojklikněte na zvolenou mapu v panelu Objects na kartě Maps 2. zadejte nové jméno

5.5.7

Úpravy mapových objektů

1. ujistěte se, že je v nástrojové liště sepnutý přepínač úpravy IMG 2. klikněte pravým tlačítkem myši na objekt, který chcete upravit 3. v menu vyberte svůj objekt 4. v submenu zvolte Edit 5. v dialogu, který se Vám následně otevře, upravte co potřebujete a uložte / zrušte; přitom dejte pozor na (ne-)zaškrnutí políčka Save as copy

5.5.8

Mazání mapových objektů

1. ujistěte se, že je v nástrojové liště sepnutý přepínač úpravy IMG 2. klikněte pravým tlačítkem myši na objekt, který chcete smazat 3. v menu vyberte svůj objekt 4. zvolte Delete

5.6

Práce s POI

Narozdíl od např. MapSource, který může zároveň pracovat pouze s jedním souborem, SnailMap umožňuje otvírat neomezené množství souborů, umožňuje je spojovat, měnit jejich formát atd. 28

5.6.1

Otevření souboru

V hlavním menu zvolte File → Open POIs file (zkratka Ctrl+O), zvolte soubory GPX nebo LOC, které chcete otevřít, a počkejte než se načtou (doba závisí na velikosti, obvykle do 1 sec.). Parser je navržený tak, aby při selhání načítání jednoho objektu tento objekt vynechal, nahlásil chybu a snažil se o načtení zbytku souboru. Syntaktických chyb se tak může při načítání objevit víc.

5.6.2

Zavření souboru

V hlavním menu zvolte File → Close a vyberte ze submenu nejvhodnější příkaz.

5.6.3

Uložení souboru

SnailMap umožňuje uložit soubory mnoha způsoby – jen zobrazené, všechny do jednoho apod. Ovšem pozor – ukládání souboru funguje stejně jako například v konzolových textových editorech (vim apod.): stávající podoba se uloží do zvoleného souboru, ale dál pokračujete v úpravě původního souboru. Postup 1. v hlavním menu zvolte File → Save POIs file a v následujícím submenu si zvolte požadovaný způsob uložení 2. při volbě jedné z prvních dvou možností (Save a Save as) budete dotázáni na soubor, kterého se činnost týká a bude Vám nabídnut seznam otevřených souborů Tipy • zobrazené soubory si můžete zvolit na panelu Object na kartě POI files SnailMap sám rozpozná typ souboru, který chcete uložit, podle zadané přípony. Pokud při tomto uložení dojde u některých objektů ke konverzi GPX ↔ LOC, SnailMap vypíše varování. Program varuje proto, že při změně formátu zahazuje všechny tagy, které nezná, případně ty, pro které druhý formát nemá ekvivalent, takže může dojít ke ztrátě uživatelských dat (jde o obsah rámečku Others v editačním dialogu).

5.6.4

Vytvoření nového bodu / stopy / trasy

• v hlavním menu zvolte POI / Path / Route → New → POI (resp. Path, Route): bod, stopa, trasa • na panelu Objects, na kartě POIs (resp. Paths, Routes) klikněte na Add new POI (resp. Path, Route): bod, stopa, trasa • v nástrojové liště Tools zvolte nástroj Mark (znak vlaječky), zvolte místo na mapě a klikněte (bod, který zvolíte, leží pod spodním koncem žerdi vlaječky): bod 29

• v hlavním menu zvolte Find → Plan route (zkratka Ctrl+R): trasa

5.6.5

Úprava bodu / stopy / trasy

• zvolte nástroj Select a dvakrát klikněte na zvolený bod: bod • na panelu Objects, na kartě POIs (resp. Paths, Routes) dvojklikněte na zvolený objekt: bod, stopa, trasa • klikněte na mapě pravým tlačítkem na zvolený bod, vyberte jej v menu a zvolte Edit: bod, stopa, trasa

5.6.6

Smazání bodu / stopy / trasy

• na panelu Objects, na kartě POIs (resp. Paths, Routes) označte na zvolené objekty a stiskněte Del: bod, stopa, trasa • klikněte na mapě pravým tlačítkem na zvolený bod, vyberte jej v menu a zvolte Delete: bod, stopa, trasa

5.6.7

Zaměření bodu / stopy / trasy na mapě

• na panelu Objects, na kartě POIs (resp. Paths, Routes) označte na zvolený objekt a v hlavním menu zvolte POI / Path / Route → Center selected (zkratka Space): bod, stopa, trasa

5.7

Vyhledávání

SnailMap umožňuje vyhledávat mapové objekty pouze podle názvu, zato ovšem s mnoha filtry, které Vám pomohou nalézt to, co zrovna hledáte. Některé filtry ovšem mohou vyhledávání výrazně zpomalit. Všechna nastavení vyhledávání se po vypnutí programu zruší. Nastavit lze vyhledávání pomocí regulárního výrazu (default) nebo přesné shody, zda vyhledávat v mapových objektech a/nebo v souborech POI (u POI je možné hledat i v sekci description; defaultně hledá všude a jen podle názvů), ve kterých IMG souborech hledat (defaultně ve všech otevřených), ve kterých vrstvách hledat (defaultně ve všech) a které typy mapových objektů hledat (defaultně jenom body). Při hledání mapových objektů lze zapnout typový filtr, který ale hledání značně zpomaluje. Důležité • porovnávání je vždy case-insensitive (nezáleží na velikosti písma) • pokud zadáte moc obecný regexp (např. „.*ÿ), může vyhledávání trvat velice dlouho

30

Tipy • při dvojkliku na nalezený objekt se mapa zaměří na jeho souřadnice a nastaví se příslušný IMG soubor a vrstva Hledání otevřete mj. zkratkou Ctrl+F nebo přes hlavní menu: Find → Object.

5.8

Plánování trasy

Panel Plan route pro plánování trasy zobrazíte tak, že v hlavním menu zvolíte Find → Plan route (zkratka Ctrl+R), případně přepenete panel Find objects na správnou kartu.

5.8.1

Nastavení parametrů plánování

Panel Plan route má 2 části, v jedné se nastavují parametry plánování, ve druhé je správa waypointů. Některá nastavení lze navíc nastavit uložit v dialogu Settings (kap. 5.3.2), jde konkrétně o algoritmus, k pro A* (kap. 2.3.2 a 4.1) a filtr. Nastavit můžete IMG soubory, ze kterých se vybuduje vyhledávací graf (defaultně všechny otevřené), vrstvu, na které se bude vyhledávat (defaultně 0), algoritmus, kterým se bude vyhledávat (defaultně A*) a filtry, které se použijí při budování grafu. Kromě několika hotových filtrů si můžete snadno vytvořit své vlastní, případně upravit stávající. Číslo ve sloupci Penalization je koeficient podle 3.2.

5.8.2

Přidání waypointu

• pravým tlačítkem myši klikněte na místo, kde chcete vytvořit waypoint, zvolte General → Add to route – automaticky se na vybraném místě vytvoří POI a souřadnice se přidají na konec seznamu waypointu na panelu Plan route • přidejte bod ručně do seznamu na panelu Plan route • pokud chcete přidat do seznamu existující bod / POI, klikněte na něj pravým tlačítkem myši, zvolte správné submenu a Add to route; v případě bodu musí být zapnutý režim editace mapy

5.8.3

Demonstrační mód plánování trasy

Panel demonstračního plánování trasy je společný s vyhledáváním a normálním plánovním trasy – je na kartě Debug visualization. Při používání demonstračního módu se k výrobě grafu použije aktualně zvolené nastavení pro normální plánování trasy. Můžete si zde nechat pouze sestavit a graf, případně zpomaleně pustit vyhledávací algoritmy. Tlačítko Build graph sestaví a vykreslí graf, hned pod ním jsou 2 karty: Run a Visibility. Na kartě Visibility můžete nestavit co všechno se bude vykreslovat, např. kotoučky kolem vrcholů grafu, čísla vrcholů grafu atd. Výběr pak potvrďte stisknutím Display. Změny se aplikují na právě vykreslený graf. 31

Na kartě Run si můžete nastavit velikost kotoučků kolem vrcholů grafu, šířku hran grafu a interval simulace. Samotnou simulaci spustíte kliknutím na tlačítko zvoleného algoritmu. Tlačítka STEP, STOP a GO slouží k ovládání simulace, tlačítko CLEAR ALL smaže všechny simulace.

32

Závěr Mým cílem v této práci bylo ukázat proces vyhledávání trasy v mapě se vším, co k tomu patří, představit několik nápadů na zlepšení a ověřit jejich funkčnost a účinnost. Z výsledků prvního experimentu vyplývá, že běh algoritmu A* lze výrazně zrychlit za cenu mírného prodloužení vyhledané trasy při volbě správného keoficientu k pro posílení vlivu heuristické funkce. Hodnota tohoto koeficientu by se měla pohybovat v intervalu (1.2; 1.5), přičemž pro trasy delší než 50 km je lepší použít nižší hodnoty k. Ve druhém experimentu jsem se pokusil najít takovou konfiguraci koeficientů, aby program nehledal nejkratší, ale nejlepší cestu (kap. 3.2). Zjistil jsem, že poměrně vhodnou metodou pro hledání nejlepší cesty je penalizace hran nepřímo úměrná maximální rychlosti povolené / dosažitelné na lineárech, které tyto hrany zastupují (v podstatě vyhledávání podle času místo vzdálenosti).

33

Seznam použité literatury [1] Cormen, Thomas H., Leiserson, Charles E., Rivest, Ronald R., Stein, Clifford. Introduction to algorithms. 2. vydání. Cambridge, Mass.: MIT Press, 2001. ISBN 0-262-53196-8. [2] Černý, Jakub. Základní grafové algoritmy. verze 0.95. vydáno 2010. http://kam.mff.cuni.cz/~kuba/ka/ [3] Goldberg, Andrew V., Harrelson, Chris. Computing the Shortest Path: A* Search Meets Graph Theory. Redmond: Microsoft Research, 2004. MSRTR-2004-24. [4] Kozicki, Stanislaw. cGPSmapper User Manual. verze 2.5 vydáno 2009. http://www.cgpsmapper.com/download/cGPSmapper-UsrMan-v02.5.pdf [5] Mareš, Martin. Krajinou grafových algoritmů : průvodce pro středně pokročilé. 1. vydání Praha: Institut teoretické informatiky, 2007. ISBN 978-80239-9049-2. [6] Matoušek, Jiří, Nešetřil, Jaroslav. Kapitoly z diskrétní matematiky. 2. vydání. Praha: Karolinum, 2000. ISBN 80-246-0084-6. [7] Moriš, Ondrej. Efficient Route-Planning in Huge Graphs With Limited Resources. Master Thesis, Masarykova univerzita. Brno: 2000. [8] Töpfer, Pavel. Algoritmy a programovací techniky. 2. vydání. Praha: Prometheus, 2007. ISBN 978-80-7196-350-9. [9] Wikipedia. http://en.wikipedia.org/wiki/A* search algorithm http://cs.wikipedia.org/wiki/Global Positioning System

34

Pojmy Cesta odpovídá definici z teorie grafu. Lineár je označení pro lineární objekt mapy. Jde o lomenou čáru, zadanou jako seznam bodů, jimiž prochází. Pokud je v textu zmínka o bodech lineáru, jedná se právě o tyto výše zmíněné body. Polygon je označení pro objekt mapy ve tvaru mnohoúhelníku (lesy apod.). Pravidlo bodu na křižovatce jsem navrhl jako možné řešení problému s vyhledáváním křižovatek (viz příslušnou sekci). Definice. Dvojice lineárů má společný bod právě tehdy, když se v daném bodě i ve skutečnosti stýkají nebo kříží.

35

Seznam použitých zkratek ALT — A*, Landmarks, Triangle inequality „A*, navigační body, trojúhelníková nerovnost (ve smyslu délek cest v grafu, nikoliv nějaké metriky)ÿ je třída velmi rychlých algoritmů na plánování trasy v grafu BD — Bidirectional „obou-/dvou-směrnýÿ – obvykle ve spojení s názvem algoritmu (A*, Dijkstra, . . .) CPU — Central Processing Unit je processor počítače GPS — Global Positioning System je vojenský globální družicový polohový systém provozovaný Ministerstvem obrany Spojených států amerických, s jehož pomocí je možno určit polohu a přesný čas kdekoliv na Zemi nebo nad Zemí s přesností do deseti metrů. Přesnost GPS lze s použitím dalších metod ještě zvýšit až na jednotky centimetrů. Část služeb tohoto systému s omezenou přesností je volně k dispozici i civilním uživatelům. Citováno z [9] GPSr — Global Positioning Satellite Receiver je přístroj k určování polohy pomocí systému GPS (známé „GPSkyÿ a „navigaceÿ) HDD — Hard Drive Device je pevný disk počítače POI — Point Of Interest „bod zájmuÿ je uživatelsky zadaný bod, který není součástí mapy RAM — Random Access Memory je operační paměť počítače

36

Příloha A Tabulky naměřených dat k experimentu s posilováním heuristiky algoritmu A* (kap. 4.1). Naměřené délky jsou uvedené na tolik desetinných míst proto, aby byly patrné přechody mezi různými nalezenými cestami, které jsou občas velmi jemné.

k # iterací délka [km] 1.0 1295 28.8268 1.1 1003 28.8474 1.2 511 28.8474 1.5 292 28.8519 1.7 158 30.9285 2.0 232 32.0980 3.0 247 31.8565 5.0 221 32.0380 7.0 235 32.5170 10.0 236 32.5170 Tabulka 5.1: Okres Benešov: N49 41.608 E014 35.746 → N49 52.273 E014 47.039

k # iterací délka [km] 1.0 206 10.7041 1.1 186 10.7041 1.2 163 10.7041 1.5 117 10.7041 1.7 89 10.7041 2.0 73 10.7041 3.0 110 10.7041 5.0 100 12.2276 7.0 105 12.2276 10.0 88 16.1282 Tabulka 5.2: Okres Benešov: N49 45.234 E014 31.976 → N49 48.298 E014 34.684

37

k # iterací délka [km] 1.0 2785 51.7818 1.1 1121 51.7818 1.2 538 51.7818 1.5 267 55.6455 1.7 270 55.6455 2.0 266 55.7475 3.0 238 58.2344 5.0 235 59.3915 7.0 235 59.4758 10.0 236 59.4758 Tabulka 5.3: Okres Benešov: N49 50.183 E014 35.395 → N49 36.479 E015 07.530

k # iterací délka [km] 1.0 2445 24.8907 1.1 1795 24.8907 1.2 1181 24.8907 1.5 812 24.9391 1.7 557 26.2518 2.0 442 26.2870 3.0 386 27.5752 5.0 358 26.9212 7.0 359 27.1719 10.0 368 27.1719 Tabulka 5.4: Praha a okolí: N49 59.829 E014 25.523 → N49 58.088 E014 10.192

k # iterací délka [km] 1.0 3588 16.6473 1.1 2585 16.6484 1.2 1348 16.6484 1.3 612 16.9306 1.5 154 16.9306 1.7 135 16.9306 2.0 106 17.0318 3.0 100 17.1176 5.0 100 17.2440 7.0 96 17.4323 10.0 95 17.4323 Tabulka 5.5: Praha: N50 06.518 E014 19.513 → N50 01.755 E014 26.584

38

k # iterací délka [km] 1.0 1062 6.9255 1.1 965 6.9289 1.2 872 6.9289 1.5 624 6.9289 1.7 570 7.1052 2.0 536 7.1018 3.0 321 8.7504 5.0 274 9.4273 7.0 274 9.4915 10.0 268 9.4915 Tabulka 5.6: Praha: N50 05.334 E014 21.372 → N50 03.202 E014 21.727

39

Obsah přiloženého CD • složka zdrojových kódů projektu SnailMap 2.3b: SnailMap-2_3b/ • doxymentace projektu SnailMap 2.3b: SnailMap-2_3b-doc/ • ukázkové soubory: Ukazkove_soubory/ • soubory tras ke druhému experimentu: EXP2/

40