Maximális folyam algoritmusok
A klasszikus maximális folyam problémára kidolgozott új algoritmusok hatékony implementálása és összehasonlító elemzése.
Háttér
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:
- 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.
- Chandran, Hochbaum. A Computational Study of the Pseudoflow and Push-Relabel Algorithms for the Maximum Flow Problem, 2009.
- Hochbaum, Orlin. Simplifications and speedups of the pseudoflow algorithm, 2013.
- Goldberg et al. Maximum Flows by Incremental Breadth-First Search, 2011.
Az algoritmusok teszteléséhez jól használható gráfgenerátorokat lehet találni pl. itt. Computer vision alkalmazásokból származó nagyon nagy méretű tesztadatokat pedig le lehet tölteni innen.
Feladat
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.).
A feladatkör BSc/MSc szakdolgozat és TDK alapjául is szolgálhat, akár több jelentkező számára is.
Előfeltételek
- C++ programozási nyelv ismerete
- alapvető gráfelméleti ismeretek
- angol nyelvismeret
