COIN-OR::LEMON - Graph Library

Changes between Version 1 and Version 2 of Többtermékes folyam-algoritmusok


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

--

Legend:

Unmodified
Added
Removed
Modified
  • Többtermékes folyam-algoritmusok

    v1 v2  
    1 == Többtermékes folyam-algoritmusok ==
     1= Többtermékes folyam-algoritmusok =
    22
    33Többtermékes folyam-algoritmusok implementálása és összehasonlítása.
    44
    5 === Háttér ===
     5== Háttér ==
    66
    7 A többtermékes folyamok a hagyományos folyam-feladatok általánosításai több forrás-cél pár esetére. A különböző forrás-cél párok közötti forgalmak ("termékek") együttesen használják az éleken levő kapacitásokat.
    8 
     7A többtermékes folyamok a hagyományos folyam feladatok általánosításai több forrás--cél pár esetére. A különböző forrás--cél párok közötti forgalmak ("termékek") együttesen használják az éleken levő kapacitásokat.
    98E feledatkör fontos szerephez jut például különféle hálózattervezési (telekommunikációs, közlekedési), útvonalválasztási és áramkörtervezési feladatok megoldásakor.
    109
    11 Elméleti szempontból ez a problémaosztály könnyen kezelhető - azaz létezik polinomiális futásidejű algoritmus - azonban alkalmazásokban gyakran felmerülnek olyan méretű feladatok, amiket ezek az algoritmusok már nem képesek elfogadható időn belül megoldani. Ezért az egzakt megoldó algorimusok mellett hatékony közelítő eljárásokat és heurisztikus módszereket is kifejlesztettek.
     10A valós értékű többtermékes folyam feladatok elméleti szempontból könnyen kezelhetők - azaz létezik polinomiális futásidejű algoritmus - azonban alkalmazásokban gyakran felmerülnek olyan méretű feladatok, amelyeket ezek az algoritmusok már nem képesek elfogadható időn belül megoldani. Ezért az egzakt megoldó algorimusok mellett hatékony közelítő eljárásokat és heurisztikus módszereket is kifejlesztettek.
    1211
    13 === Feladat ===
     12Ha azonban egészértékű többtermékes folyamokat keresünk, illetve megköveteljük, hogy a folyam termékenként osztatlan legyen (azaz minden terméket egyetlen út mentén szállítsunk el), akkor általában NP-nehéz feladatokat kapunk, amelyek a gyakorlati alkalmazásaik miatt szintén fontosak. Ezekre különféle közelítő és heurisztikus módszereket dolgoztak ki.
    1413
    15 A jelentkezők feladata az irodalomban fellelhető többtermékes folyam-algoritmusok áttekintése, a gyakorlatban alkalmazhatók közül néhány implementálása, összehasonlítása esetleg továbbfejlesztése. Cél, hogy a minél több alfeladatra hatékony megoldás szülessen és a letisztázott implementáció bekerüljön a LEMON programkönyvtárba.
     14== Feladat ==
     15
     16A jelentkezők feladata az irodalomban fellelhető többtermékes folyam-algoritmusok áttekintése, a gyakorlatban alkalmazhatók közül néhány implementálása, összehasonlítása, esetleg továbbfejlesztése. Cél, hogy minél több alfeladatra hatékony megoldás szülessen és a letisztázott implementáció bekerüljön a LEMON programkönyvtárba.
    1617
    1718A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.
    1819
    19 === Előfeltételek ===
     20'''''Megjegyzés''': Néhány feladatra már születtek implementációk a LEMON-hoz, ezért a téma választása előtt ajánlatos ezzel kapcsolatban érdeklődni.''
     21
     22== Előfeltételek ==
    2023
    2124 - C++ programozási nyelv ismerete