COIN-OR::LEMON - Graph Library

Changes between Initial Version and Version 1 of Utazóügynök feladat


Ignore:
Timestamp:
06/17/09 12:05:16 (15 years ago)
Author:
Peter Kovacs
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Utazóügynök feladat

    v1 v1  
     1= Utazóügynök feladat =
     2
     3Approximá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
     7Az 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
     9Adott ''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
     13A 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
     15A 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