COIN-OR::LEMON - Graph Library

Changes between Version 3 and Version 4 of Steiner-hálózat keresése


Ignore:
Timestamp:
06/17/09 10:54:33 (10 years ago)
Author:
Peter Kovacs
Comment:

--

Legend:

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

    v3 v4  
    55== Háttér ==
    66
     7Adott egy irányítatlan ''G=(V,E)'' gráf és bármely két csúcsa között egy lokális élösszefüggőségi igény: az ''u'' és ''v'' pontok között ''r(u,v)''.  Az ''uv'' él használatának költsége ''c(uv)'', kapacitása pedig ''f(uv)''. Célunk ''G''-nek egy minimális ''c''-költségű ''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 ''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 vezet út.
     8
     9A probléma NP-teljes már a legegyszerűbb esetekben is. Speciális esete a [wiki:"Steiner-fa feladat"], amelyre a LEMON már tartalmaz egy [http://lemon.cs.elte.hu/pub/doc/0.7/a00533.html 2-approximációs algoritmust].
     10
    711A 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 
    9 Formá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)''.
    10 Az ''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 
    14 A 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].
    1512
    1613== Feladat ==
    1714
    18 A 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.
    19 Ezt 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.
     15A 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, amely a megoldásban legalább ''1/2'' értékkel szerepel. Ezt 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.
    2016
    21 A 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
    22 approximációs algoritmusban alkalmaztak, köztük több is implementálásra érdemes lehet.
     17A probléma megoldása tehát LP feladatok 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 approximációs algoritmusban alkalmaztak, köztük több is implementálásra érdemes lehet.
    2318
    2419A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.