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

Timestamp:

07/02/10 17:40:58 (14 years ago)

Author:

Peter Kovacs

Comment:

--

Utazóügynök feladat

@@ -7 +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.
 
-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.
+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:[[BR]]
+http://en.wikipedia.org/wiki/Travelling_salesman_problem
 
 == Feladat ==
@@ -15 +20 @@
 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.''
+'''''Megjegyzés''': A szimmetrikus és metrikus TSP feladatra az alapvető heurisztikus algoritmusok már elkészültek.''