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 Steiner-hálózat feladat.

Feladat

A feladat megoldására 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 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
• gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
• angol nyelvismeret