Elérhetőség dinamikus gráfokban
Míg a gráfokat a klasszikus algoritmuselméletben általában statikus, nem változó objektumokként tanulmányozzák, addig néhány modern alkalmazása a gráfelméletnek (például kommunikációs és szociális hálózatok, számítógépes grafika és mesterséges intelligencia) a gráfokat olyan objektumoknak tekinti, a...
Elmentve itt :
| Szerző: | |
|---|---|
| További közreműködők: | |
| Dokumentumtípus: | Szakdolgozat |
| Megjelent: |
2018
|
| Tárgyszavak: | |
| Online Access: | http://diploma.bibl.u-szeged.hu/73613 |
| Tartalmi kivonat: | Míg a gráfokat a klasszikus algoritmuselméletben általában statikus, nem változó objektumokként tanulmányozzák, addig néhány modern alkalmazása a gráfelméletnek (például kommunikációs és szociális hálózatok, számítógépes grafika és mesterséges intelligencia) a gráfokat olyan objektumoknak tekinti, amelyek diszkrét változásokra képesek. Az utóbbi néhány évtizedben egy gyorsan növő kutatási terület lett az ilyen, úgynevezett dinamikusan változó gráfokra alkalmazott algoritmusok és adatszerkezetek témaköre, hiszen dinamikus gráfokra számos probléma (úgy mint az elérhetőség, minimális vágás, minimális feszítőfa [7, 13]) esetere hatékony algoritmus kidolgozása sokkal nagyobb kihívás, mint a statikus megfelelőjükre. Az egyik legtöbbet kutatott téma az elérhetőség, ahol a kérdés az, hogy elérhető-e a gráf egy adott állapotában egy rács egy másikból, vagy akar kérdezhetjük azt is általánosan, hogy a gráf összefüggő-e. Általában a gráf csucsai állandóak, azonban éleket zárhatunk be és törölhetünk abból ki. Attól függően, hogy az algoritmus mely élműveleteket tudja támogatni, beszelhetünk inkrementális (ekkor csak a bezárás támogatott), dekremenrális (ekkor csak a törlés), vagy teljesen dinamikus (avagy fully dynamic, ekkor mindkét művelet támogatott) algoritmusokról. Egy ilyen algoritmus minden módosítás urán olyan műveleteket végez és tárol el valamilyen formában információt, hogy a gráftulajdonságra vonatkozó kérdést gyorsan képes legyen megválaszolni. Tehát a cél egy olyan algoritmus (és adatszerkezet) megalkotása, amely képes adaptálódni a módosítások urán, ezzel hatékonyabban megválaszolni a kérdést, mintha minden egyes lekérdezéskor újrafuttatnánk egy klasszikus algoritmust [8]. Attól függően, hogy mely műveleteket támogatja az algoritmus, lehet nehezebb vagy könnyebb dolgunk. A dolgozatban megvizsgáljuk a könnyebben megvalósítható inkrementális algoritmust, melyet egy szeles körben ismert adatszerkezettel, a Unionfind erdővel [2] egyszerűen megvalósíthatunk. Továbbá adunk egy példát a teljesen dinamikus eset egy lehetséges megvalósításara is. Az ebben az esetben használt adatszerkezetet, az úgynevezett Euler-tour fák hatékony megvalósítását 1995-ben írta le Valerie King és Monika Henzinger [5], viszont azóta sem született szeles körben elérhető implementáció, s ha szolgált is kutatások alapjául, a forráskódokat a szerzők nem publikáltak. Az erre az adatszerkezetre épülő teljesen dinamikus algoritmus [7] a gráf egy feszítőerdejét tartja nyilván Euler körutakkal reprezentálva, s ezt a struktúrát módosítja a gráf minden egyes változásakor. Az algoritmus legnagyobb kihívása annak a megválaszolása, hogy egy olyan él törlésekor, amit a feszítőerdőben nyilvántartottunk, vajon tényleg szétesik-e a fa, vagy van a gráfban olyan el, ami helyettesíteni tudja ezt. Ahhoz, hogy ezt elég gyorsan meg tudjuk válaszolni, nem elég, ha csupán az egész gráfot tároljuk, hiszen egy ilyen helyettesítő el keresésekor elképzelhető, hogy akar az összes élet meg kell vizsgálni, ami nem eredményezne hatékony eljárást. Ahhoz, hogy a lehetőségekhez merten kevés élet kelljen bejárnunk, a gráfot elei szerint különböző szintekbe soroljuk, s szint szerint tesszük kereshetővé a gráfot. Láthatjuk tehát, hogy a lehetséges megoldások korántsem triviálisak. A kutatok a mai napig dolgoznak további algoritmusok és adatszerkezetek megadásán, amelyek vagy egy lekérdezés megválászolását vagy egy él törlésének vagy beszúrásának lekezelését gyorsabbá teszi. Ennek okán pedig a témával érdemes megismerkedni, hiszen algoritmusok és adatszerkezetek terén is rendkívül sok új, a mindennapokban nem használt technikákról tanulhatunk. |
|---|