Problém obchodního cestujícího: řešení s pomocí grafových a genetických algoritmů
Název práce v češtině: | Problém obchodního cestujícího: řešení s pomocí grafových a genetických algoritmů |
---|---|
Název v anglickém jazyce: | Traveling Salesman Problem: Solutions using graph and genetic algorithms |
Akademický rok vypsání: | 2007/2008 |
Typ práce: | diplomová práce |
Jazyk práce: | čeština |
Ústav: | Katedra aplikované geoinformatiky a kartografie (31-370) |
Vedoucí / školitel: | doc. Ing. Tomáš Bayer, Ph.D. |
Řešitel: | skrytý - zadáno a potvrzeno stud. odd. |
Datum přihlášení: | 23.01.2008 |
Datum zadání: | 03.02.2008 |
Datum proběhlé obhajoby: | 22.09.2008 |
Zásady pro vypracování |
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. |
Seznam odborné literatury |
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. |