Changes between Initial Version and Version 1 of Negatív körök keresése

Timestamp:

08/02/10 12:31:27 (14 years ago)

Author:

Peter Kovacs

Comment:

--

Negatív körök keresése

@@ +1 @@
+= Negatív körök keresése =
+
+Hatékony algoritmusok implementálása annak eldöntésére, hogy van-e negatív költségű irányított kör egy gráfban.
+
+== Háttér ==
+
+A legrövidebb utak kereséséhez szorosan kapcsolódó probléma annak eldöntése, hogy létezik-e negatív összköltségű irányított kör egy élsúlyozott gráfban. Ha ilyen kör nem létezik, akkor bármely két pont között létezik minimális költségű séta, amelyet a Bellman-Ford-algoritmussal meg is kereshetünk. Más megközelítésben azt mondhatjuk, hogy ilyenkor létezik megenegedett potenciálfüggvény: minden ''u'' csúcshoz hozzárendelhetünk egy d(''u'') potenciált, amelyre teljesül, hogy minden (''u'', ''v'') élen a c(''u'',''v'') + d(''u'') - d(''v'') redukált költség nemnegatív (vagyis d(''u'') + c(''u'',''v'') >= d(''v'')). Egy ilyen potenciálfüggvény ismeretében a legröviebb utak keresését hatékonyan tudjuk megoldani Dijkstra algoritmusával (a redukált költségeket használva).
+
+Egy érdekes és fontos feladat tehát annak eldöntése, hogy egy irányított, élsúlyozott gráf tartalmaz-e negatív kört. Olyan algoritmusokat keresünk, amelyek megadnak egy negatív kört, ha ilyen létezik, egyébként pedig egy megengedett potenciálfüggvényt. A klasszikus Bellman-Ford algoritmus alkalmas ezen probléma megoldására, de a gyakorlatban sokszor nem elég hatékony. Ugyanakkor számos hasonló, de a gyakorlatban jobban teljesítő algoritmus is született.
+
+Az alábbi cikk részletesen elemzi és összehasonlítja a különböző módszereket:
+  - [http://www.siam.org/proceedings/alenex/2008/alx08_012cherkasskyb.pdf] vagy
+  - [http://portal.acm.org/citation.cfm?id=1498698.1537602]
+
+
+== Feladat ==
+
+A feladat a fenti probléma megoldására született leghatékonyabb algoritmusok implementálása és összehasonlító elemzése különböző gráfokon.
+
+A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat, akár több jelentkező számára is.
+
+== Előfeltételek ==
+
+ - C++ programozási nyelv ismerete
+ - alapvető gráfelméleti ismeretek 
+ - angol nyelvismeret