COIN-OR::LEMON - Graph Library

Changes between Initial Version and Version 1 of Steiner-fa keresése


Ignore:
Timestamp:
06/17/09 11:32:53 (10 years ago)
Author:
Peter Kovacs
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Steiner-fa keresése

    v1 v1  
     1= Steiner-fa keresése =
     2
     3Minél hatékonyabb közelítő és heurisztikus algoritmusok implementálása a Steiner-fa feladatra.
     4
     5== Háttér ==
     6
     7A Steiner-fa feladat a minimális költségű feszítőfa keresésének általánosítása.
     8
     9Adott egy ''G=(V,E)'' irányítatlan, összefüggő gráf, és a terminál pontjainak egy ''T'' halmaza (''V'' része), továbbá minden élhez hozzárendelünk egy költséget. Keressünk egy minimális költségű fát, amely az összes ''T''-beli pontot tartalmazza. ''T=V'' esetén nyilván a minimális költségű feszítőfa feladatot kapjuk, egyébként pedig egy jóval nehezebb problémához jutunk, amelyben a ''T''-beli pontokhoz további "köztes" pontokat (ún. Steiner-pontokat) hozzávéve csökkenthetjük a feszítőfa költségét.
     10
     11A feladat általános esetben NP-teljes. Megoldására számos approximációs és heurisztikus algoritmust dolgoztak ki, továbbá néhány speciális változatára egzakt polinomiális módszerek is ismertek.
     12
     13A probléma általánosítása a [wiki:"Steiner-hálózat keresése" Steiner-hálózat feladat].
     14
     15== Feladat ==
     16
     17A feladat megoldására [http://lemon.cs.elte.hu/pub/doc/0.7/a00533.html Mehlhorn 2-közelítő approximációs algoritmusa] már szerepel a LEMON-ban. A jelentkezők feladata az irodalomban fellelhető további approximációs és heurisztikus algoritmusok áttekintése, a gyakorlatban alkalmazhatók közül néhány implementálása, összehasonlítása, esetleg továbbfejlesztése.
     18
     19Mindenképpen érdemes megvizsgálni G. Robins és A. Zelikovsky algoritmusát, amely az eddig ismert legjobb approximációs faktort (1.55) garantálja. Érdekes kérdés, hogy a gyakorlatban hogyan viszonyul a jóval egyszerűbb 2-approximációs algoritmushoz, valamint más módszerekhez.
     20
     21A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.
     22
     23== Előfeltételek ==
     24
     25 - C++ programozási nyelv ismerete
     26 - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
     27 - angol nyelvismeret