Heuristikou řízené hledání optima v NP-těžkých úlohách

• Thesis title in Czech: Heuristikou řízené hledání optima v NP-těžkých úlohách
• Thesis title in English: Heuristic-driven methods finding optimum for NP-hard problems
• Academic year of topic announcement: 2008/2009
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: RNDr. Martin Pergel, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 04.11.2008
• Date of assignment: 04.11.2008
• Date and time of defence: 17.09.2010 00:00
• Date of electronic submission: 17.09.2010
• Date of proceeded defence: 17.09.2010
• Opponents: doc. RNDr. Pavel Surynek, Ph.D.

Guidelines

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.

References

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.

Preliminary scope of work

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.

Preliminary scope of work in English

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.