Projekt előrehaladási jelentés

A kutatási területhez megfogalmazott kutatási célok – klasszikus és randomizált algoritmusok vizsgálata geometriai és gráfelméleti problémák algoritmikus megoldására –  közül a 2011. december 31-től 2012. június 30-ig tartó periódus során kutatásunk elsődleges tárgya egy randomizált algoritmus kifejlesztése, illetve továbbfejlesztése volt az ún. legközelebbipontpár-probléma megoldására.

A probléma lényege, hogy a d-dimenziós euklideszi térben bemenetként megadott n méretű 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 nagy elméleti jelentőséggel is bír, ugyanis nemcsak azon kérdéseknek volt egyike, amelyek megválaszolásával a geometriai algoritmusok tudományterületét mintegy három évtizeddel ezelőtt megalapozták, de egyben ez volt az a probléma is, melynek megoldásra az első randomizált algoritmus kidolgozásra került.

A feladatra eddig ismert algoritmusok döntően két osztályba sorolhatóak: összehasonlítás- és hash-elésalapú módszerekre. Az előbbi kategóriába tartozó algoritmusok a bemeneti ponthalmaz pontjainak konkrét koordinátáiba nem „nézhetnek bele”, csak összehasonlíthatják azokat más pontok koordinátáival, és ezen összehasonlítás kimenetele függvényében döntést hozhatnak. E megoldások vagy valamilyen térparticiónáló adatszerkezeteket használnak, vagy az „oszd meg és uralkodj elven alapulnak, lépésszámuk tipikusan O(nlogn). A hash-elés alapú módszerek lépésszáma általában O(n), azaz lineáris a pontok számában, ugyanakkor az általuk megkövetelt számítási modell is sokkal gazdagabb, tipikusan randomizálást, hash-elést és egészrészképzést is tartalmaz. Ez utóbbi kategóriába tartoznak az általunk is vizsgált, ún. rácsalapú módszerek is.

Mindezen algoritmusokra igaz azonban, hogy a fenti, lépésszámra vonatkozó becslések csak akkor érvényesek, ha a dimenziók d számát konstansnak tekintjük. Ezt a megkötést feloldva azt tapasztaljuk, hogy egyes algoritmusok lépésszáma valójában a dimenziószámtól exponenciálisan függ, vagy esetleg nem is határozható meg egykönnyen.

Kutatásunk során először a fentiekben ismertetett, meglévő algoritmusok viselkedését tanulmányoztuk a dimenziók számának függvényében. Ezt követően továbbfejlesztettük egy általunk korábban, a kétdimenziós esetre kidolgozott rácsalapú módszert. Ez a módszer a kétdimenziós legközelebbipontpár-feladatra ad az eddig ismert algoritmusoknál egy gyorsabb megoldást az ún. segédrácsok (egy kiegészítő térparticionáló adatszerkezet) bevezetésével. Ezt a térparticionáló ötletet, melyet tehát eredetileg a kétdimenziós esetre dolgoztunk ki, általánosítottuk d dimenzióra, ezáltal elértük, hogy módszerünk lépésszáma véletlen bemeneteken, aszimptotikus értelemben nemcsak a pontok számában, de a dimenziók számában is lineáris lett (az exponenciális függés helyett). Az aszimptotikus lépésszám megközelítéséhez ugyanakkor viszonylag nagy méretű bemeneti ponthalmazokra van szükség, ezért az elért eredményeink elsősorban elméleti jelentőségűek.

A most kidolgozott módszer lépésszámára vonatkozó állítás formális igazolásához – amely a kutatási munka jelentős hányadát tette ki – egy első ránézésre nem túl szorosan kapcsolódó témakörben, az ún. véletlen geometriai gráfokkal kapcsolatban elért eredményeket használtuk kiindulási alapként.

Végül számos mérést elvégezve kijelenthetjük, hogy a kidolgozott algoritmus elméleti jelentősége mellett a néhány dimenziós (d=2…6) problémák esetén a gyakorlatban is jelentősen gyorsabb a már ismert módszereknél, ha a bemeneti ponthalmaz mérete kellően nagy – de nem szükségképpen nagyobb annál a méretnél, amely a manapság használatos különféle architektúrájú számítógépeken rendelkezésre álló operatív tárban kényelmesen elfér.