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.