COIN-OR::LEMON - Graph Library

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:

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
Last modified 4 years ago Last modified on 04/30/14 02:31:53