Diplomová práce

Rychlé hledání cesty v obřích grafech

Efficient route-planning in huge graphs

Bc. Ondrej Moriš, učo 172887
Anotace

Táto práca je venovaná problému plánovania cesty v obrovských grafoch, akými sú cestné mapy. V tomto probléme je našou úlohou nájsť najlepšiu cestu medzi dvoma pozíciami vzhľadom k určitému kritériu optimality. Predkladáme nový dvojúrovňový heuristický prístup založený na vylepšení dobre známej metódy bunkového prehľadávania. Predstavujeme originálny pojem rozsahu hrany, ktorý je schopný zachytiť pomerne …více

Abstract

In this work we are concerned with a route-planning problem in huge graphs such as real-world road maps. In this problem we are given two end positions and we want to find the best route between them with respect to chosen criteria. We propose a new two-level heuristic approach based on a clarification of a well-known cell search method. We introduce a notion of edge scope that is able to ensure a …více

Klíčová slova
route-planning road map scope cell boundary graph
Zadání práce
Náplní práce je prakticky použitelné řešení problému hledání optimální cesty pro velmi velké grafy cestních sítí v GPS navigacích (pro které jsou již klasické algoritmy nevhodné). Diplomant již tuto úlohu částečne rozpracoval ve své bakalářské práci. Cílem práce je nalezení prakticky použitelné metody předzpracování mapových dat (tj. grafu cestní sítě) a následného rychlého hledání optimální cesty mezi zadanými body s důrazem na šetření pracovní paměti i úložiště. Pro tento účel diplomant využije nově navržený pojem rozsahu (scope) cesty a volně dostupná mapová data. Dalším cílem práce je také analýza efektivity nového přístupu ve srovnání s jinými známými postupy. Diplomant také zmíní praktické možnosti dalších rozšíření svého přístupu.
Administrativní informace
Práce zkontrolována:
1. 6. 2010 07:39, prof. RNDr. Petr Hliněný, Ph.D., učo 168881
Plný text práce
1,8 MB / soubor PDF
Jazyk práce
angličtina angličtina
Termín obhajoby
1. 7. 2010
Práce byla úspěšně obhájena

Vedoucí

prof. RNDr. Petr Hliněný, Ph.D., učo 168881
KTP FI MU

Oponent

doc. Mgr. Hana Rudová, Ph.D., učo 3840
KSUZD FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Informatika
Obor

Práce na příbuzné téma

Seznam prací, které mají shodná klíčová slova.

Podobné práce

  • Přidání souboru

    Soubor nebo složku lze nahrát pomocí tlačítka Přidat.

  • Další operace se soubory

    Podrobnosti lze zjistit označením příslušného řádku.

  • Pohled pro experty

    Pro častou práci je možné zvolit režim Více možností.

  • Vyhledávání souborů

    Vyhledávaný výraz můžete zadat přímo do adresního řádku.

  • Rychlý přístup k souborům

    Pomocí funkce Nedávné je možné se rychle vrátit k právě prohlíženým souborům. Oblíbené soubory je také možné označit Hvězdičkou.