| | 1 | = Maximális folyam algoritmusok = |
| | 2 | |
| | 3 | A klasszikus maximális folyam problémára kidolgozott új algoritmusok hatékony implementálása és összehasonlító elemzése. |
| | 4 | |
| | 5 | == Háttér == |
| | 6 | |
| | 7 | A maximális folyam feladat egy alapvető optimalizálási probléma, amelynek megoldására számtalan különféle algoritmus született. Ezek közül néhány már implementálva van a LEMON-ban, köztük az egyik leghatékonyabb, a preflow push-relabel algoritmus is. Ugyanakkor vannak újabb algoritmusok is, amelyeket a gyakrolatban igen hatékonynak találtak. Például: |
| | 8 | * [http://www.cs.tau.ac.il/~sagihed/dsw10a/goldberg.pdf Goldberg. The Partial Augment–Relabel Algorithm for the Maximum Flow Problem, 2008.] Ez a preflow push-relabel algoritmusnak egy módosított változata, amely a gyakorlatban hatékonyabbnak, robusztusabbnak bizonyult. |
| | 9 | * [http://pubsonline.informs.org/doi/abs/10.1287/opre.1080.0572 Chandran, Hochbaum. A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem, 2009.] |
| | 10 | * [http://dl.acm.org/citation.cfm?id=2414855 Hochbaum, Orlin. Simplifications and speedups of the pseudoflow algorithm, 2013.] |
| | 11 | * [http://research.microsoft.com/pubs/150437/ibfs-proc.pdf Goldberg et al. Maximum Flows by Incremental Breadth-First Search, 2011.] |
| | 12 | |
| | 13 | Az algoritmusok teszteléséhez jól használható gráfgenerátorokat lehet találni pl. [ftp://dimacs.rutgers.edu/pub/netflow/generators/network/ itt]. Computer vision alkalmazásokból származó nagyon nagy méretű tesztadatokat pedig le lehet tölteni [http://vision.csd.uwo.ca/data/maxflow/ innen]. |
| | 14 | |
| | 15 | == Feladat == |
| | 16 | |
| | 17 | A feladat néhány új, ígéretesnek tűnő maximális folyam algoritmus implementálása és alapos összehasonlító elemzése különböző gráfokon. Továbbá érdemes lenne a már meglévő preflow push-relabel implementáció javítási lehetőségeit is megvizsgálni (pl. next arc heurisztika alkalmazása, meglévő heurisztikák paramétereinek felülvizsgálata stb.). |
| | 18 | |
| | 19 | A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat, akár több jelentkező számára is. |
| | 20 | |
| | 21 | == Előfeltételek == |
| | 22 | |
| | 23 | - C++ programozási nyelv ismerete |
| | 24 | - alapvető gráfelméleti ismeretek |
| | 25 | - angol nyelvismeret |
