Heuristikou řízené hledání optima v NP-těžkých úlohách
Název práce v češtině: | Heuristikou řízené hledání optima v NP-těžkých úlohách |
---|---|
Název v anglickém jazyce: | Heuristic-driven methods finding optimum for NP-hard problems |
Akademický rok vypsání: | 2008/2009 |
Typ práce: | bakalářská práce |
Jazyk práce: | čeština |
Ústav: | Katedra aplikované matematiky (32-KAM) |
Vedoucí / školitel: | RNDr. Martin Pergel, Ph.D. |
Řešitel: | skrytý![]() |
Datum přihlášení: | 04.11.2008 |
Datum zadání: | 04.11.2008 |
Datum a čas obhajoby: | 17.09.2010 00:00 |
Datum odevzdání elektronické podoby: | 17.09.2010 |
Datum proběhlé obhajoby: | 17.09.2010 |
Oponenti: | doc. RNDr. Pavel Surynek, Ph.D. |
Zásady pro vypracování |
Uchazeč po dohodě s vedoucím vybere vhodné problémy řesitelné v anotaci uvedenou metodou, implementuje jejich řešení a případně se pokusí metodu modifikovat resp. zobecnit k využití na dalších těžkých problémech. |
Seznam odborné literatury |
Jiří Ivánek, Jaroslav Morávek: Heuristic improvement of the dynamic programming treatment of the TSP. Ekonomicko-matematický obzor 17, 1981, č. 1, str. 13 - 27.
Stuart J. Russel, Peter Norvig: Artificial Intelligence. A Modern Approach. Second Edition. Prentice Hall, New Jersey 2003. S. Dasgupta, C. H. Papadimitriou, U. V. Vazirani: Algorithms. Penultimate draft. Berkeley 2006. G. Gambosi, P. Crescenzi, V. Kann, A. Marchetti-Spaccamela, M. Protasi: Complexity and Approximation. Combinatorial Optimization Problems and Their Approximability Properties. Second corrected printing. Springer-Verlag, Berlin 2003. Dorit S. Hochbaum (ed.): Approximation Algorithms for NP-hard Problems. PWS Publishing Comp, Boston 1997. Další dle vlastního uvážení a doporučení vedoucího. |
Předběžná náplň práce |
Předmětem práce je studium a využití některých heuristických metod založených na algoritmu A* na hledání optimálních řešení vybraných NP-těžkých problémů, analýza, na které problémy je tato metoda vhodná (vysvětlení proč) a zhodnocení úspěšnosti této metody na vybraných (NP-těžkých) problémech. |
Předběžná náplň práce v anglickém jazyce |
Subject to the thesis is study and use of methods based on A*-algorithm finding optimum solutions for particular NP-hard problems. The thesis includes analysis and explanation for which type of problems this method is suitable. Candidate also comments results reached by this method for particular (suitable) NP-hard problems. |