Randomizált algoritmusok gráfelméleti és geometriai problémák megoldására

OData támogatás
Konzulens:
Dr. Friedl Katalin
Számítástudományi és Információelméleti Tanszék

Az elmúlt három évtized során az ún. randomizált algoritmusok, illetve az átlagos lépésszám elemzésének tudományterülete rohamos fejlődésen ment keresztül, és napjainkra már az algoritmikus bonyolultságelmélet legfontosabb (és legaktívabb) területei közé sorolhatóak. Mindkét témakör szorosan kapcsolódik a valószínűségszámításhoz, és arra a kérdésre keresi a választ, hogy miként tudunk a praktikus felhasználás során, átlagos értelemben hatékony algoritmusokat készíteni, illetve hogyan tudjuk ezeket elméleti síkon elemezni.

E diplomaterv keretében a fenti témaköröket az ún. legközelebbipontpár-probléma kapcsán fogjuk érinteni, amelynek lényege, hogy egy adott ponthalmazban meg kell határoznunk azt a két pontot, amelyek -- valamilyen távolságmérték szerint -- a legközelebb vannak egymáshoz. A feladat elméleti jelentősége nagy, ugyanis nemcsak azon kérdéseknek volt egyike, amelyek megválaszolásával a geometriai algoritmusok tudományterületét (többek között) Shamos és Bentley megalapozta, de egyben ez volt az a probléma is, melynek megoldására Rabin az első randomizált algoritmust kidolgozta.

Dolgozatunkban a legközelebbipontpár-probléma irodalmának áttekintése után a Golin, Raman, Schwarz és Smid által kidolgozott randomizált algoritmust elemezzük részletesebben. Az elméleti vizsgálathoz először részletesen áttekintjük az ún. véletlen geometriai gráfok területén elért eredményeket, és ezeket megfelelően átalakítva igazoljuk, hogy a Golin és társai által kidolgozott algoritmus bizonyos típusú bemenetek esetén sok felesleges műveletet végez. Ennek orvoslására bemutatunk az algoritmushoz két lehetséges kiegészítést, végül az így továbbfejlesztett két algoritmus átlagos lépésszámát az ún. valószínűségi analízis módszerével elemezzük. Ennek során a bemeneti pontok helyébe egyenletes eloszlású valószínűségi vektorváltozókat képzelünk, és ezen véletlen bemenet vonatkozásában határozzuk meg az algoritmusok lépésszámának várható értékét.

Míg a Golin és társai által kidolgozott eredeti algoritmus lépésszáma d dimenzió és n darab pont esetén várható értékben (3^d+2)n, tehát a dimenziótól exponenciálisan függ, addig az általunk továbbfejlesztett két módszer várható lépésszáma a valószínűségi analízis során aszimptotikusan csupán (3d+6)n-nek, illetve (d+2)n-nek adódik, azaz mind a dimenziók, mind a pontok számában csak lineáris. Ez az eredmény egyrészt elvi jelentőségű, másrészt már praktikus méretű bemenetekre is egy gyors alternatívát kínál a legközelebbipontpár-probléma megoldására. A szimulációs eredmények tanúsága szerint pedig algoritmusunk nemcsak az egyenletes eloszlású, hanem lényegében bármilyen más folytonos eloszlású bemenet esetére is jól alkalmazható, így számos gyakorlati probléma modellezésénél hatékonyan felhasználható.

Letölthető fájlok

A témához tartozó fájlokat csak bejelentkezett felhasználók tölthetik le.