Algoritmikus problémák bonyolultságának előrejelzése tömörítéssel

Papp Pál András II. Inf., papp.pal.andras@gmail.com

Konzulens: Dr. Mann Zoltán, Számítástudományi és Információelméleti Tanszék, zoltan.mann@cs.bme.hu

A számítástudományban az egyik legnagyobb kihívást az NP-teljes problémák jelentik, így ezek vizsgálata kiemelten fontos. Mivel ezeknek jelentős része gráfelméleti probléma, a gráfok vizsgálata egy gyakori megközelítése a problémakörnek.

Bár a bonyolultságelméletben a probléma nehézségét szinte kivétel nélkül mindig az input méretével jellemzik, a gyakorlati tapasztalatok azt mutatják, hogy azonos méretű bemenetek esetén a bonyolultság nagyon eltérő lehet. Ezen tapasztalatok egyik jellegzetessége, hogy adott input-méretű véletlen gráfokkal az algoritmusok általában lényegesen nehezebben boldogulnak, mint az ugyanekkora mesterségesen generált – tehát különböző alkalmazási területeken ember által létrehozott –, „strukturáltabb” példányokkal. Természetesen merül fel ekkor a kérdés, hogy egy mérték, ami a gráfban jelenlevő strukturális információ mennyiségének mérőszáma – konkrétan a gráf tömörített mérete – vajon jobban előrejelzi-e a probléma nehézségét, mint az input nagysága.

Dolgozatomban ezért azt vizsgáltam, hogy egy adott gráf tömöríthetőségéből mennyire adhatunk jó predikciót a hozzá kapcsolódó probléma bonyolultságáról. A kutatás során strukturált gráfként regiszter allokációs problémák gráfjait, illetve véletlen gráfokat használtam fel. Egy adott NP-teljes problémán (a gráfszínezésen) futó két különböző algoritmust figyeltem meg, egy egzakt, ám így exponenciális futásidejű BranchAndBound-ot, illetve heurisztikaként egy genetikus algoritmust. A probléma bonyolultságának jelzésére előbbi esetben a backtrackek számát, utóbbiban az algoritmus futásidejét figyeltem, és azt vizsgáltam, hogy ezek mennyire jósolhatók különböző tömörítési eljárásokkal.

A dolgozatban négy különböző tömörítési eljárás kerül összehasonlításra, melyből három külső programokat használ fel. Az első a gráf szomszédossági mátrixának ZIP fájllá való tömörítése, a második a gráf tömörítése a Minimum Description Length elv segítségével, a harmadik pedig a Subdue program, mely ismétlődő részstruktúrák keresésével tömörít egy gráfot. Megmutatom, hogy sok esetben már az így tömörített méretek is lényegesen jobb becsléshez vezetnek, mintha csupán a gráf csúcsainak számából vonnánk le következtetéseket.

A negyedik egy általam írt program (Graph Structure Analyzer, GSA), amelynek célja kifejezetten a gráfok tömörítése és struktúrájának leírása. A GSA egy genetikus algoritmus, amelyben a gráfok különböző leírásai fejlődnek, és a program ezek közül próbálja megkeresni a legjobbat. Az egyes leírásokban a gráfot olyan (esetleg egymást átfedő) struktúrákból építi fel (pl. teljes gráfok, utak), amelyek a gráfproblémák bonyolultságában gyakran meghatározó szerepet játszanak. Dolgozatomban megmutatom, hogy a GSA valóban alkalmas gráfok tömörítésére, és a tömörítéssel kapott méret adott esetben az előző három programnál is jobban előrejelzi a problémák bonyolultságát.

szerző

Papp Pál András
mérnök informatikus
nappali

konzulens

Dr. Mann Zoltán Ádám
, (külső)

helyezés

I. helyezett

letöltés
385 kB