Diszkrét optimalizáló algoritmusok vizsgálata

Abstract

A diszkrét optimalizáció a matematikai optimalizáció egy olyan ága, amely olyan problémák megoldásával foglalkozik, ahol a változók diszkrét, tipikusan egész vagy bináris értékeket vesznek fel. Ez a terület szoros kapcsolatban áll az operációkutatással, a kombinatorikával, és számos alkalmazási területen megjelenik, például a logisztikában, a pénzügyekben, a számítástechnikában és a mesterséges intelligenciában. A diszkrét optimalizációs problémák gyakran NP-nehéz problémák, ami azt jelenti, hogy a probléma megoldásához szükséges számítási idő a bemenet méretének növekedésével várhatóan exponenciálisan növekszik így különböző heurisztikus algoritmusokat fejlesztettek ki ezeknek a problémáknak a megoldására. Mivel minden NP-ben található probléma átalakítható polinomiális időben egy adott NP-nehéz problémává, ezért fokuszálhatunk az adott problémában való heurisztikák és egyéb megoldások vizsgalatára. Egy új megközelítés jelentősen előrelépést jelenthet ebben az ágban és ezt úgy igyekszünk előállítani, hogy jelenleg ismert paradigmákat és algoritmusokat ötvözünk, vagy pont ezeket kerüljük el. A kutatás során, a részösszeg problémával foglalkozunk, illetve annak részproblémájával.