= Utazóügynök feladat = Approximációs, heurisztikus és exponenciális algoritmusok implementálása és összehasonlítása az utazóügynök problémára. == Háttér == Az utazóügynök probléma (''travelling salesman problem'', TSP) az egyik legismertebb és legtöbbet vizsgált NP-teljes probléma, amelynek számtalan gyakorlati alkalmazása van. Adott ''n'' város, és ismerjük bármely kettőnek a távolságát. Keressünk egy minimális költségű körutazást, amely minden várost pontosan egyszer érint. A problémának több változatát szokták vizsgálni a városok között távolságfüggvény tulajdonságai alapján (szimmetrikus/aszimmetrikus, metrikus/nem metrikus). Részletesebben:[[BR]] http://en.wikipedia.org/wiki/Travelling_salesman_problem == Feladat == A feladat az irodalomban fellelhető, minél többféle alkalmazott módszer megismerése, előnyeik/hátrányaik feltérképezése, ezek némelyikének implementálása, összehasonlítása és esetleg új módszerek, heurisztikák keresése. A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat, akár több jelentkező számára is. '''''Megjegyzés''': A szimmetrikus és metrikus TSP feladatra az alapvető heurisztikus algoritmusok már elkészültek.'' == Előfeltételek == - C++ programozási nyelv ismerete - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok - angol nyelvismeret