COIN-OR::LEMON - Graph Library

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


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

--

Legend:

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

    v2 v3  
    1 == Approximációs algoritmus Steiner-hálózat keresésére ==
     1= Steiner-hálózat keresése =
    22
    33Lineá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.
    44
    5 === Háttér ===
     5== Háttér ==
    66
    77A 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.
     
    1313
    1414A 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 ===
     15
     16== Feladat ==
    1617
    1718A 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.
     
    2324A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.
    2425
    25 === Előfeltételek ===
     26== Előfeltételek ==
    2627
    2728 - C++ programozási nyelv ismerete