COIN-OR::LEMON - Graph Library

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:
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.

Kapcsolódó ticket: #386.

Megjegyzés: A szimmetrikus és metrikus TSP feladatra az alapvető heurisztikus algoritmusok már elkészültek. Ugyanakkor pl. Lin és Kernighan algoritmusát érdemes lenne még implementálni (l. http://www.cs.elte.hu/~tkiraly/students/egeszerteku_jegyzet.pdf).

Előfeltételek

  • C++ programozási nyelv ismerete
  • gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
  • angol nyelvismeret
Last modified 4 years ago Last modified on 04/30/14 01:16:44