| | 1 | = Steiner-fa keresése = |
| | 2 | |
| | 3 | Minél hatékonyabb közelítő és heurisztikus algoritmusok implementálása a Steiner-fa feladatra. |
| | 4 | |
| | 5 | == Háttér == |
| | 6 | |
| | 7 | A Steiner-fa feladat a minimális költségű feszítőfa keresésének általánosítása. |
| | 8 | |
| | 9 | 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. |
| | 10 | |
| | 11 | 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. |
| | 12 | |
| | 13 | A probléma általánosítása a [wiki:"Steiner-hálózat keresése" Steiner-hálózat feladat]. |
| | 14 | |
| | 15 | == Feladat == |
| | 16 | |
| | 17 | 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. |
| | 18 | |
| | 19 | 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. |
| | 20 | |
| | 21 | A 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 |
