= Steiner-fa keresése =

Minél hatékonyabb közelítő és heurisztikus algoritmusok implementálása a Steiner-fa feladatra.

== Háttér ==

A Steiner-fa feladat a minimális költségű feszítőfa keresésének általánosítása.

Adott 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.

A 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.

A probléma általánosítása a [wiki:"Steiner-hálózat keresése" Steiner-hálózat feladat].

== Feladat ==

A 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.

Mindenké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.

A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.

== Előfeltételek ==

 - C++ programozási nyelv ismerete
 - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
 - angol nyelvismeret