Tato práce se zabývá principy řešení optimalizační úlohy známé jako Problém obchodního cestujícího. První část je teoretickým úvodem do problematiky vázané na teorii složitosti a optimalizace. Dále je uveden popis principu užití a implementace metody větví a mezí, vybra-ných heuristických postupů a optimalizačního nástroje Gurobi optimizer.
Anotace v angličtině
This thesis deals with various solving principles of optimization problem known as the trav-elling salesman problem. The first part is a theoretical introduction to the problem related to the theory of complexity and optimization. It also describes the principles of using and imple-menting the branch and bound method, selected heuristics and the optimization tool Gurobi optimizer.
Klíčová slova
teorie grafů, Problém obchodního cestujícího, celočíselné programování, optimalizace, branch and bound, heuristika, Gurobi optimizer
Tato práce se zabývá principy řešení optimalizační úlohy známé jako Problém obchodního cestujícího. První část je teoretickým úvodem do problematiky vázané na teorii složitosti a optimalizace. Dále je uveden popis principu užití a implementace metody větví a mezí, vybra-ných heuristických postupů a optimalizačního nástroje Gurobi optimizer.
Anotace v angličtině
This thesis deals with various solving principles of optimization problem known as the trav-elling salesman problem. The first part is a theoretical introduction to the problem related to the theory of complexity and optimization. It also describes the principles of using and imple-menting the branch and bound method, selected heuristics and the optimization tool Gurobi optimizer.
Klíčová slova
teorie grafů, Problém obchodního cestujícího, celočíselné programování, optimalizace, branch and bound, heuristika, Gurobi optimizer
Problém obchodního cestujícího (Travelling Salesman Problem) je optimalizační problém, matematicky vyjadřující a zobecňující úlohu nalezení nejkratší možné cesty procházející všemi zadanými body na mapě. V teorii grafů zní úkol: "V daném ohodnoceném úplném grafu najděte nejkratší Hamiltonovskou kružnici." Problém je, že s rostoucím počtem měst počet možných cest velice rychle narůstá, a tím se doba potřebná k propočtu hrubou silou na počítačích stává zcela neúnosnou už při několika málo desítkách uzlů. Proto se používají heuristické metody. Cílem práce bude rešerše těchto metod, návrh a vypracování aplikace pro nalezení minimální Hamiltonovské kružnice.
Zásady pro vypracování
Problém obchodního cestujícího (Travelling Salesman Problem) je optimalizační problém, matematicky vyjadřující a zobecňující úlohu nalezení nejkratší možné cesty procházející všemi zadanými body na mapě. V teorii grafů zní úkol: "V daném ohodnoceném úplném grafu najděte nejkratší Hamiltonovskou kružnici." Problém je, že s rostoucím počtem měst počet možných cest velice rychle narůstá, a tím se doba potřebná k propočtu hrubou silou na počítačích stává zcela neúnosnou už při několika málo desítkách uzlů. Proto se používají heuristické metody. Cílem práce bude rešerše těchto metod, návrh a vypracování aplikace pro nalezení minimální Hamiltonovské kružnice.
Seznam doporučené literatury
BALAKRISHNAN, V. Schaum's outline of theory and problems of graph theory. New York: McGraw-Hill, c1997, viii, 293 p. ISBN 00-700-5489-4.
Seznam doporučené literatury
BALAKRISHNAN, V. Schaum's outline of theory and problems of graph theory. New York: McGraw-Hill, c1997, viii, 293 p. ISBN 00-700-5489-4.
Přílohy volně vložené
1 CD ROM
Přílohy vázané v práci
schémata
Převzato z knihovny
Ne
Plný text práce
Přílohy
Posudek(y) oponenta
Hodnocení vedoucího
Záznam průběhu obhajoby
Problém obchodního cestujícího je optimalizační problém, matematicky vyjadřující a zobecňující úlohu nalezení nejkratší možné cesty procházející všemi zadanými body na mapě. V teorii grafů zní úkol: V daném ohodnoceném úplném grafu najděte nejkratší Hamiltonovskou kružnici. Problém je, že s rostoucím počtem měst počet možných cest velice rychle narůstá. Proto se požívají heuristické metody. Cílem práce bude rešerše těchto metod, návrh a vypracování aplikace pro nalezení minimální Hamiltonovské kružnice. Diplomant vytvořil teoretickou část, popisující danou problematiku, vysvětlil používané metody včetně ilustrativních příkladů. Dále popsal vytvořenou aplikaci, včetně použitých návrhových vzorů, a přiložil uživatelskou dokumentaci, včetně srovnání výsledků jednotlivých algoritmů. Programová část je funkční.
Práce byla zkontrolována v systému IS STAG a byla vyhodnocena jako původní. Nejedná se o plagiát.