| | 1 | = Utazóügynök feladat = |
| | 2 | |
| | 3 | Approximációs, heurisztikus és exponenciális algoritmusok implementálása és összehasonlítása az utazóügynök problémára. |
| | 4 | |
| | 5 | == Háttér == |
| | 6 | |
| | 7 | 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. |
| | 8 | |
| | 9 | 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. |
| | 10 | |
| | 11 | == Feladat == |
| | 12 | |
| | 13 | 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. |
| | 14 | |
| | 15 | A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is. |
| | 16 | |
| | 17 | == Előfeltételek == |
| | 18 | |
| | 19 | - C++ programozási nyelv ismerete |
| | 20 | - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok |
| | 21 | - angol nyelvismeret |
