Többtermékes folyam-algoritmusok

Többtermékes folyam-algoritmusok implementálása és összehasonlítása.

Háttér

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. E 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.

A 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.

Ha 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.

Feladat

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 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.

A feladatkör szakdolgozat, nagyprogram és TDK alapjául is szolgálhat, akár több jelentkező számára is.

Kapcsolódó ticket: #296.

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.

Előfeltételek

• C++ programozási nyelv ismerete
• alap gráfelméleti ismeretek
• angol nyelvismeret