Práce řeší aplikaci algoritmu simulovaného žíhání pro nalezení optimální kružnice v úplném grafu. Motivací pro úlohu je optimalizace trasy závodu Jizerský Qaker. Úkolem závodníků je v omezeném čase 22 hodin zdolat co nejvíce vylosovaných skal. Tyto skály jsou obodovány dle oblasti, ve které se nachází. Vyhrává dvojice, která v tomto časovém úseku jako první nasbírá co nejvíce bodů. Matematicky tato úloha vede k nalezení optimální kružnice v úplném grafu. Optimální v našem případě znamená, že nepřekročí daný čas a má maximální hodnocení.
Anotace v angličtině
This thesis uses the application of the simulated annealing method to find an optimal circle in a graph. The motivation for this task is the optimization of the route of the competition Jizerský Qaker. Competitors have to climb on as many selected rocks as possible within a time frame of 22 hours. These rocks are rated according to the area where they lie. The winning team is the team that earns the most points in this time limit. Mathematically this task leads to the finding of an optimal cycle in a graph. An optimal cycle means that the cycle will not exceed the given time limit and will have the most points.
Klíčová slova
Simulované žíhání, problém obchodního cestujícího, teorie grafů, diskrétní matematika
Práce řeší aplikaci algoritmu simulovaného žíhání pro nalezení optimální kružnice v úplném grafu. Motivací pro úlohu je optimalizace trasy závodu Jizerský Qaker. Úkolem závodníků je v omezeném čase 22 hodin zdolat co nejvíce vylosovaných skal. Tyto skály jsou obodovány dle oblasti, ve které se nachází. Vyhrává dvojice, která v tomto časovém úseku jako první nasbírá co nejvíce bodů. Matematicky tato úloha vede k nalezení optimální kružnice v úplném grafu. Optimální v našem případě znamená, že nepřekročí daný čas a má maximální hodnocení.
Anotace v angličtině
This thesis uses the application of the simulated annealing method to find an optimal circle in a graph. The motivation for this task is the optimization of the route of the competition Jizerský Qaker. Competitors have to climb on as many selected rocks as possible within a time frame of 22 hours. These rocks are rated according to the area where they lie. The winning team is the team that earns the most points in this time limit. Mathematically this task leads to the finding of an optimal cycle in a graph. An optimal cycle means that the cycle will not exceed the given time limit and will have the most points.
Klíčová slova
Simulované žíhání, problém obchodního cestujícího, teorie grafů, diskrétní matematika
Cílem práce je navhrnout a implemetovat algoritmus simulovaného žíhání na zobecnění úlohy obchodního cestujícího a vyřešit modelový problém inspirovaný horolezeckým závodem Jizerský Qaker.
Student se seznámí s grafovou teorií, speciálně s klasickou NP-těžkou úlohou obchodního cestujícího. Dále se seznámí se stochastickým optimalizačním algoritmem simulovaného žíhání.
V praktické části student aplikuje simulované žíhání na plánování trasy závodu - zobecnění úlohy obchodního cestujícího. Algoritmus implemetuje v programovacím jazyce R.
Zásady pro vypracování
Cílem práce je navhrnout a implemetovat algoritmus simulovaného žíhání na zobecnění úlohy obchodního cestujícího a vyřešit modelový problém inspirovaný horolezeckým závodem Jizerský Qaker.
Student se seznámí s grafovou teorií, speciálně s klasickou NP-těžkou úlohou obchodního cestujícího. Dále se seznámí se stochastickým optimalizačním algoritmem simulovaného žíhání.
V praktické části student aplikuje simulované žíhání na plánování trasy závodu - zobecnění úlohy obchodního cestujícího. Algoritmus implemetuje v programovacím jazyce R.
Seznam doporučené literatury
[1] V. Černý, Thermodynamical approach to the traveling salesman problem: An effcient simulation algorithm, Journal of Optimization Theory and Applications, 45 (1985), pp. 4151.
[2] P. Fajgl, O. Simm, and M. Vrkoslav, Jizerské hory: Horolezecký průvodce, NH SAVANA,2009.
[3] J. Matoušek and J. Nešetřil, Kapitoly z diskrétní matematiky, Karolinum, V Praze, 2010.
[4] M. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing, SCIENCE, 220 (1983), pp. 671 -680.
Seznam doporučené literatury
[1] V. Černý, Thermodynamical approach to the traveling salesman problem: An effcient simulation algorithm, Journal of Optimization Theory and Applications, 45 (1985), pp. 4151.
[2] P. Fajgl, O. Simm, and M. Vrkoslav, Jizerské hory: Horolezecký průvodce, NH SAVANA,2009.
[3] J. Matoušek and J. Nešetřil, Kapitoly z diskrétní matematiky, Karolinum, V Praze, 2010.
[4] M. S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Optimization by simulated annealing, SCIENCE, 220 (1983), pp. 671 -680.