Heuristické a metaheuristické metody řešení úlohy obchodního cestujícího - Burdová, Jana; Kalčevová, Jana; Zouhar, Jan, 1982-; Vysoká škola ekonomická v Praze. Fakulta informatiky a statistiky (2011)
Tato diplomová práce se zabývá otázkou nalezení minimální trasy pro úlohu obchodního cestujícího. Obchodní cestující musí projít každé místo právě jednou a vrátit se zpět do výchozího místa. Tento problém může být znázorněn jako úloha teorie grafů, kde místa odpovídají uzlům, cesty hranám a vzdálenosti mezi uzly ohodnocení hran. Optimální cesta úlohy obchodního cestujícího odpovídá nejkratšímu Hamiltonovu cyklu v grafu. Jedná se o klasickou NP-úplnou úlohu. Není znám žádný algoritmus, který řeší tuto úlohu v polynomiálním čase. Tento problém je možné řešit pomocí různých aproximačních algoritmů, které jsou rychlejší, ale méně kvalitní, než optimalizace. Mezi aproximační algoritmy, kterým se tato práce věnuje, patří například: metoda nejbližšího souseda, metoda minimální kostry grafu, Christofidova metoda, 2 opt., genetický algoritmus a další.
Vedoucí práce: Jana Kalčevová
Obsahuje bibliografii
Textový (vysokoškolská kvalifikační práce)
Způsob přístupu: Internet
Diplomová práce (Ing.)—Vysoká škola ekonomická v Praze. Fakulta informatiky a statistiky, 2011
Rok obhajoby 2011
Keywords: ekonometrie a operační výzkum [obor dipl. práce]; diplomové práce; master's theses