COIN-OR::LEMON - Graph Library

Changes between Version 3 and Version 4 of Utazóügynök feladat


Ignore:
Timestamp:
07/02/10 19:40:58 (9 years ago)
Author:
Peter Kovacs
Comment:

--

Legend:

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

    v3 v4  
    77Az 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.
    88
    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.
     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.
     10
     11A 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).
     12
     13Részletesebben:[[BR]]
     14http://en.wikipedia.org/wiki/Travelling_salesman_problem
    1015
    1116== Feladat ==
     
    1520A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat, akár több jelentkező számára is.
    1621
    17 '''''Megjegyzés''': A témakörön már dolgozott/dolgozik szakdolgozó, ezért a részletekről érdemes érdeklődni.''
     22'''''Megjegyzés''': A szimmetrikus és metrikus TSP feladatra az alapvető heurisztikus algoritmusok már elkészültek.''
    1823
    1924