= 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. Vagyis keressük meg egy irányítatlan gráf legkisebb költségű Hamilton-körét.

== 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 témakörön már dolgozott/dolgozik szakdolgozó, ezért a részletekről érdemes érdeklődni.''


== Előfeltételek ==

 - C++ programozási nyelv ismerete
 - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok 
 - angol nyelvismeret