Diplomová práce

Efektivní rozdělování obřích grafů pro potřeby navigace

Efficient decomposition of huge graphs in route planning

Bc. Martin Juránek
Anotace

Tato práce byla vytvořena ve spolupráci s firmou Aponia software. V této práci je popsán heuristický algoritmus na dělení vrcholů grafu na malé disjunktní podmnožiny (v této práci nazývané buňky) s co nejmenším množstvím hran mezi těmito podmnožinami. Tento algoritmus slouží k dělení grafů reprezentujících silniční síť na dostatečně malé části, které se vejdou do operační paměti malých zařízení (kapesní …více

Abstract

This diploma thesis was made in cooperation with company Aponia software. In this thesis algorithm decomposing graph's vertexes into small disjunct sets (called cells) minimizing ammount of edges between cells is described. This algoritm is meant to be used to decompose graph representing road network into small enough parts which can fit into RAM of small devices (GPS navigation gadgets, smartphones …více

Klíčová slova
graf graph manévr maneuver minimální řez minimal cut navigace navigation hledání nejkratší cesty routing dekompoyice grafu graph decomposition branch decomposition větvená dekompozice zjednodušení grafu graph simplification
Zadání práce
Náplní práce je zkoumání prakticky použitelných přístupů k dekompozici obřích téměř rovinných grafů, jako je cestní síť celé Evropy, do jednotlivých vhodných a nepříliš velkých "buněk". Tento výzkum je motivován přímou praktickou aplikací v oblasti GPS navigace, kde omezené kapesní zařízení musí takovéto obří grafy zpracovávat při hledání nejkratších cest.

Student rozebere teoreticky tento problém (ve spolupráci s firmou Aponia) a vyvine nové přístupy založené na hlubší znalosti teorie grafů. Výsledkem dekompozice by mělo být rozdělení celého obřího grafu na jednotlivé souvislé podgrafy s velikostí řádově do jednotek tisíců vrcholů, přičemž tyto podgrafy musí respektovat předdefinované "manévry". Tento přístup bude implementován jako modul preprocessingu v softwaru Be-on-Road zmíněné firmy Aponia a student v práci podrobně rozebere jeho přínosy a srovnání s předchozím naivním přístupem i s relevantními publikovanými výsledky.

Administrativní informace
Práce zkontrolována:
11. 10. 2008 12:57, (IS automaticky)
Plný text práce
2,1 MB / soubor PDF
Jazyk práce
čeština čeština
Termín obhajoby
14. 2. 2008
Práce byla úspěšně obhájena

Vedoucí

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

Oponent

Mgr. Ing. Petr Výmola
abs FI MU
Citovat tuto práci
Masarykova univerzita Fakulta informatiky
Studijní program
Aplikovaná informatika
Obor

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

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

Podobné práce
 
Název
Vložil
Vloženo
Práva
Archiv závěrečné práce Martin Juránek FI N-AP AP n6g81/13
Juránek, M.
6. 1. 2008
Složky
Soubory
AlmostAll.logs
Juránek, M.
6. 1. 2008
AlmostAll.treeStats
Juránek, M.
6. 1. 2008
Anotace anglicky annotation_english.txt
Juránek, M.
6. 1. 2008
Anotace česky annotation.txt
Juránek, M.
6. 1. 2008
BIG_IMAGES.ZIP
Juránek, M.
6. 1. 2008
CR_Vyvoj.zip
Juránek, M.
6. 1. 2008
deleni_grafu.odt
Juránek, M.
6. 1. 2008
deleni_grafu.pdf
Juránek, M.
6. 1. 2008
Klíčová slova keywords.txt
Juránek, M.
6. 1. 2008
Posudek oponenta posudek-oponenta.doc
Výmola, P.
25. 1. 2008
readme.txt
Juránek, M.
6. 1. 2008
Stromy.zip
Juránek, M.
6. 1. 2008

  • 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.