COIN-OR::LEMON - Graph Library

Changes between Initial Version and Version 1 of Steiner-hálózat keresése


Ignore:
Timestamp:
03/26/09 15:33:25 (13 years ago)
Author:
veghal
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Steiner-hálózat keresése

    v1 v1  
     1== Approximációs algoritmus Steiner-hálózat keresésére ==
     2
     3Lineáris programozást használó 2-approximációs algoritmus implementálása irányítatlan gráfban Steiner-hálózat keresésére.
     4
     5=== Háttér ===
     6
     7A kérdés gyakorlati alkalmazása, hogy egy meglévő hálózatot (pl. telekommunikációs vagy elektromos ellátó hálózat) szeretnénk minimális költségráfordítással minél biztonságosabbá tenni.
     8
     9Formálisan, egy ''G=(V,E)'' gráf bármely két csúcsa között adott egy lokális élösszefüggőségi igény: az ''u'' és ''v'' pontok között ''r(u,v)''.
     10Az ''uv'' él behúzásának költsége ''c(uv)'', kapacitása pedig ''f(uv)''. Célunk ''G''-nek egy minimális ''c''-költségű
     11''H=(V,F)'' részgráfját megtalálni, amelyben minden ''uv'' él legfeljebb ''f(uv)''-szer szerepel, és minden ''u,v'' csúcspárra a két pont között létezik
     12''r(u,v)'' éldiszjunkt út. Ez azzal ekvivalens, hogy még ha tetszőleges ''r(u,v)-1'' élet ki is törlünk a gráfból, ''u'' és ''v'' közt még mindig fog vezetni út.
     13
     14A probléma NP-teljes már a legegyszerűbb esetekben is. Speciális esete a Lemonban már implementált [http://lemon.cs.elte.hu/pub/doc/latest-svn/a00532.html Steiner-fa approximációs probléma].
     15=== Feladat ===
     16
     17A feladat a Kamal Jaintől származó 2-approximációs algoritmus implementálása. Az algoritmus lényege a következő: a probléma természetes LP-relaxáltjának keresünk egy bázismegoldását. Bizonyítható, hogy ebben van olyan él, ami a megoldásban legalább ''1/2'' értékkel szerepel.
     18Ezt az élt bevesszük a gráfba, újra felírjuk és újra megoldjuk a lineáris programot, és ezt az eljárást iteráljuk.
     19
     20A probléma megoldása tehát lineáris programok egy sorozatának megoldása. Ez az iterált kerekítések módszerének nevezett eljárás, melyet később számos
     21approximációs algoritmusban alkalmaztak, köztük több is implementálásra érdemes lehet.
     22
     23A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.
     24
     25=== Előfeltételek ===
     26
     27 - C++ programozási nyelv ismerete
     28 - gráfelméleti ismeretek, kombinatorikus optimalizálási alapok
     29 - angol nyelvismeret