Problém obchodního cestujícího: řešení s pomocí grafových a genetických algoritmů
| Thesis title in Czech: | Problém obchodního cestujícího: řešení s pomocí grafových a genetických algoritmů |
|---|---|
| Thesis title in English: | Traveling Salesman Problem: Solutions using graph and genetic algorithms |
| Academic year of topic announcement: | 2007/2008 |
| Thesis type: | diploma thesis |
| Thesis language: | čeština |
| Department: | Department of Applied Geoinformatics and Cartography (31-370) |
| Supervisor: | doc. Ing. Tomáš Bayer, Ph.D. |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 23.01.2008 |
| Date of assignment: | 03.02.2008 |
| Date of proceeded defence: | 22.09.2008 |
| Guidelines |
| Diplomová práce se bude zabývat analýzou problému obchodního cestujícího (Travelling
salesman problem) a možnostmi jeho řešení s využitím vybraných grafových a genetických algoritmů. Problém obchodního cestujícího patří mezi známé NP-úplné problémy, řadu podob- ných geoinformatických problémů lze na tuto úlohu převést. Práce se bude snažit o zhodnocení efektivity řešení tohoto problému vzhledem ke zvolené metodě a charakteru vstupních dat. V prvotní fázi práce bude provedeno zmapování současných možností řešení tohoto pro- blému ve vybraných GIS (ArcGIS, GRASS atd.). Na základě analýzy existujících řešení na bázi grafových nebo genetických algoritmů se autor pokusí nalézt nejvhodnější metodu pro aplikaci v geoinformatice. Rozhodujícími parametry budou konfigurace vstupních dat, pamě- ťová a časová složitost algoritmu a kvalita řešení. Tuto metodu se diplomant pokusí implementovat ve zvoleném programovacím jazyce a na vzorových datech tak ověřit teoreticky dosažené výsledky. |
| References |
| Demel J.: Grafy a jejich aplikace, Academia, 2002.
Kužel R.: Hamiltonovské vlastnosti grafů, Západočeská univerzita, 2004. Matoušek J., Nešetřil J.: Kapitoly z diskrétní matematiky, MatFyz Press, 1996. Worboys M.F., Duckham M.: Geographic Information Systems: A Computing Perspective, CRC Press, 2004. Němec M.: Optimalizace pomocí mravenčích kolonií, ČVUT, 2006. |