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

Timestamp:

06/17/09 08:32:53 (15 years ago)

Author:

Peter Kovacs

Comment:

--

Többtermékes folyam-algoritmusok

@@ -1 @@
-== Többtermékes folyam-algoritmusok ==
+= Többtermékes folyam-algoritmusok =
 
 Többtermékes folyam-algoritmusok implementálása és összehasonlítása.
 
-=== Háttér ===
+== 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.
-
+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.
 
-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.
+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.
 
-=== Feladat ===
+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.
 
-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.
+== 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.
 
-=== Előfeltételek ===
+'''''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