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