Nejkratší cesty při vyhledávání dopravního spojení

• Název práce v češtině: Nejkratší cesty při vyhledávání dopravního spojení
• Název v anglickém jazyce: Shortest paths when searching for travel connections
• Akademický rok vypsání: 2005/2006
• Typ práce: diplomová práce
• Jazyk práce: čeština
• Ústav: Katedra aplikované matematiky (32-KAM)
• Vedoucí / školitel: doc. Mgr. Petr Kolman, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 05.01.2006
• Datum zadání: 05.01.2006
• Datum a čas obhajoby: 18.09.2007 00:00
• Datum odevzdání elektronické podoby: 18.09.2007
• Datum proběhlé obhajoby: 18.09.2007
• Oponenti: Mgr. Petr Škovroň, Ph.D.

Zásady pro vypracování

Úkolem diplomanta bude seznámit se s existujícími algoritmy na hledání
nejkratší cesty a prověřit jejich použitelnost (vhodnost) pro aplikaci
vyhledávání dopravního spojení. Diplomant
porovná na reálných (případně náhodných) datech chování různých algoritmů, např.
Dijkstrova algoritmu, heuristických algoritmů, algoritmů asymptoticky
rychlejších než Dijkstrův, algoritmy využívající možnost předzpracování
vstupních dát, algoritmy využívající (skoro) rovinnost prohledávané sítě
(a porovná reálná data s náhodnými),nejlepší algoritmy zpřístupní jako webovou
aplikaci, ve které umožní vyhledávání spojení vzhledem k různým cenovým
(hodnotícím) funkcím a dále umožní flexibilnější zadávání startu a cíle cesty.

Seznam odborné literatury

Uri Zwick: Exact and approximate distances in graphs - a survey;
další články podle zadání školitele