Prim-algoritmus
A Prim-algoritmus egy összefüggő súlyozott gráf minimális feszítőfáját határozza meg mohó stratégia segítségével. Működési elve, hogy csúcsonként haladva építi fel a fát, egy tetszőleges csúcsból kiindulva és minden egyes lépésben a lehető legolcsóbb élt keresi meg egy következő csúcshoz. Az algoritmust először Vojtěch Jarník írta le 1930-ban, de ez az eredmény ismeretlen maradt. Tőle függetlenül Robert C. Prim 1957-ben és Edsger Dijkstra 1959-ben újra felfedezték. Ezért az algoritmust nevezik még DJP-algoritmusnak, Jarník-algoritmusnak vagy Prim−Jarník-algoritmusnak is.
További ehhez hasonló algoritmus még a Kruskal-algoritmus és a Boruzvka-algoritmus. Ezek az algoritmusok megkeresik egy feltehetőleg nem összefüggő gráf minimális feszítő erdejét. Ezzel szemben a Prim-algoritmus egyszerű verziója egy összefüggő gráfban találja meg a minimális feszítőfát. Azonban a Prim-algoritmus alkalmazása a gráf különböző kapcsolódási pontjain szintén megtalálja a minimális feszítőerdőt. Ami a bonyolultságot illeti, mindhárom algoritmus egyformán gyors sűrű gráfokban, de lassabb más kifinomultabb algoritmusoknál. Az elég sűrű gráfok esetén a Prim-algoritmus lineáris idő alatt lefuttatható, azonosan vagy túlteljesítve más algoritmusok időbeli megkötéseit.
Az algoritmus leírása
Az algoritmus lépésenként építi fel a minimális feszítőfát, minden lépésben egy csúcsot adva hozzá.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9b/PrimAlgDemo.gif/200px-PrimAlgDemo.gif)
Az algoritmus lépései a következők:
- Válasszuk ki a gráf egy tetszőleges csúcsát, legyen ez egy egycsúcsú fa.
- Ameddig van a gráfnak olyan csúcsa, amelyik nincs benne a fában, végezzük el a következőket:
- Válasszuk ki a fa csúcsai és a gráf többi csúcsa között futó élek közül a legkisebb súlyút.
- A kiválasztott él nem fabeli csúcsát tegyük át a fába az éllel együtt.
Formálisabban:
00 Jelöljük V-vel a gráf csúcsainak halmazát. Jelöljük a feszítőfa csúcsainak halmazát X-szel, éleinek halmazát pedig F-fel. 01 Válasszunk ki tetszőlegesen egy csúcsot, legyen ez v. 02 X:={v}; Y:= V-X; F:=üres 03 while X ≠ V do 04 legyen {x,y}, ahol x X, y Y, a legkisebb súlyú él az X és Y közötti élek közül 05 F:=F {(x,y)}; X:= X {y}; Y:= Y-{y} 06 Eredmény: az (X,F) fa
Példa
A következő példában, lépésenként bemutatjuk az algoritmust. A táblázat második oszlopában az X és Y csúcshalmazokat egy szaggatott függőleges vonallal választjuk el, és csak a fa, valamint az X és Y közötti éleket jelöljük a megfelelő súlyokkal. Az első oszlopban mindig az eredeti gráf szerepel, hogy könnyen ellenőrizhessük az X és Y közötti éleket.
Kiválasztjuk az a csúcsot, kezdetben ez a fa. Kiválasztjuk a hozzá illeszkedő élek közül a legkisebb súlyút. Ez a c csúcs. Most az a és c csúcs, valamint az ezeket összekötő él képezi az új fát. A fa és a gráf többi csúcsa közötti élek közül a {c,h} él a legkisebb súlyú. | ||
A h csúcs és a {c,h} él átkerül a fába. A fa és a gráf többi csúcsa közötti élek közül a {h,g} él a legkisebb súlyú. | ||
A g csúcs és a {h,g} él átkerül a fába. A fa és a gráf többi csúcsa közötti élek közül a {g,e} él a legkisebb súlyú. | ||
Az e csúcs és a {g,e} él átkerül a fába. A fa és a gráf többi csúcsa közötti élek közül a {c,d} és {h,d} élek mindegyike legkisebb súlyú. Bármelyiket választhatjuk. Válasszuk a {c,d} élt! | ||
A d csúcs és a {c,d} él átkerül a fába. A fa és a gráf többi csúcsa közötti élek közül a {c,b} él a legkisebb súlyú. | ||
A b csúcs és a {c,b} él átkerül a fába. A fa és a gráf többi csúcsa közötti élek közül az {a,f} él a legkisebb súlyú. | ||
Az f csúcs és az {a,f} él átkerül a fába, amely feszítőfa, mivel a gráf minden csúcsát tartalmazza. | ||
Az eredmény az eredeti gráf csúcselrendeződése szerint. |
Amennyiben minden lépésben csupán egy legkisebb súlyú él van, a megoldás egyértelmű. Különben több minimális értékű feszítőfa létezhet.
Bonyolultsága
A Prim-algoritmus bonyolultsága az gráfnál alkalmazott adatszerkezettől és az élek súly szerinti rendezettségétől függ, ami az elsőbbségi sor segítségével lehetséges. Az alábbi táblázat a gyakori választásokat mutatja be:
Minimális élű adatszerkezet | Teljes bonyolultság |
Szomszédsági mátrix, keresés | O(|V|2) |
Bináris kupac és szomszédsági lista | O((|V| +|E|) log |V|) = O(|E| log |V| ) |
Fibonacci kupac és szomszédsági lista | O(|E| +|V|log |V|) |
A Prim-algoritmus egy egyszerű megvalósítása, ami lineárisan nézi végig a súlyok listáját, hogy megtalálja a minimális hozzáadandó élt, O(|V|2) futási időbe telik. Ez a futási idő azonban jelentősen javítható, ha kupacokat használunk a minimális súlyú élek megtalálására a belső hurokban.
Az első továbbfejlesztett verziója kupacot használ, hogy eltárolja a súly szerint rendezett bemeneti gráf összes élét. Azonban élek helyett a csúcsok eltárolása még tovább fejlesztheti az algoritmust. A kupac a csúcsokat azon legkisebb él súlyok szerint rendezi,melyek tetszőleges a csúcsokkal kötik össze őket, a részlegesen felépített minimális feszítőfában (MFF) (vagy végtelen, ha nem létezik ilyen él). Mindig, amikor egy v csúcs kiválasztásra kerül és hozzáadódik a minimális feszítőfához, egy kulcs-csökkentő művelet lefut minden olyan a feszítőfán kívül eső w csúcson, ahol v össze van kötve w –vel és a kulcs az ezt megelőző érték minimumára van állítva és a élek költsége (v,w).
Egy egyszerű bináris kupac adatszerkezetet használva a Prim-algoritmus most már O(|E| log |V| ) idő alatt fut le, ahol |E| az élek száma |V| pedig a csúcsok száma. Az ennél precízebb Fibonacci-kupacot használva a bonyolultság O(|E| +|V|log |V|) –ra redukálható, ami aszimptotikusan gyorsabb, ha a gráf elég sűrű. Az ennél is sűrűbb gráfok esetén (legalább |V|c éllel, ahol c>1), a Prim-algoritmus lineáris idejű futása még egyszerűbb, a Fibonacci helyett egy d-kupac (speciális bináris kupac) használatával.
Helyessége
A helyesség bizonyítása Andrásfai Béla[1] ötletén alapszik. Könnyű belátni, hogy az algoritmus eredményeként mindegyik csúcshoz illeszkedő élek közül a legkisebb súlyú biztos benne van a megoldásban. Tehát színezzük ki pirossal az eredeti gráf azon éleit, amelyek az egyes csúcsokhoz illeszkedők közül a legkisebb súlyúak. Ha a piros élek egy feszítőfa élei, akkor ez a fa nyilván minimális. Ha az eredmény nem feszítőfa, akkor a piros élek több fa élei. Vonjuk össze ezen fák mindegyikét egy-egy csúcsba. Az így kapott fára alkalmazzuk újra az élek kifestését a fenti módon. Amikor a színezés befejeződik, az eredeti gráf ilyen módon kiszínezett élei egy feszítő fa élei lesznek, és pont azok, amelyeket az algoritmus is kiválaszt. Ez a fa természetesen minimális feszítőfa.
Formálisabban:
Legyen P egy összefüggő, súlyozott gráf. A Prim-algoritmus minden lépésében találnunk kell egy élt, ami egy részgráf egy élét a részgráfon kívüli éllel köti össze. Mivel P összefüggő, minden csúcshoz lesz út. Az algoritmus kimenetele legyen az Y fa. Legyen Y1 a gráf minimális feszítőfája. Ha Y1 = Y, akkor Y a minimális feszítőfa. Egyébként, legyen e az első hozzáadott él az Y fa elkészítésekor, ami nincs benne az Y1 fában és V az olyan élek által összekötött csúcsok halmaza melyek e előtt lettek hozzáadva. Ekkor az e él egyik végpontja eleme a V halmaznak , a másik nem. Mivel Y1, a P gráf egy feszítőfája, van Y1-nek olyan útja, ami a két végpontot köti össze. Ahogy bejárjuk az utat, találkoznunk kell egy olyan f éllel, ami egy V-beli csúcsot egy nem V-belivel köt össze. Annál a lépésnél, amikor az e él hozzá lett adva az Y fához, f–et is hozzá lehetett volna adni, méghozzá e helyett, ha a súlya kisebb mint e-nek, de mivel f-et nem adtuk hozzá, levonhatjuk azt a következtetést, hogy
w(f) ≥ w (e).
Legyen Y2 az a fa, amit úgy kaptunk, hogy eltávolítottuk az f élt és hozzáadtuk e-t az Y1 fához. Könnyen belátható, hogy Y1 összefüggő, ugyanannyi éle van, mint Y1-nek és az élek összsúlya nem nagyobb Y1 élei összsúlyának, így hát Y2 is egy minimális feszítőfája a P gráfnak, tartalmazza az e élt és minden más élt ami e előtt lett hozzáadva a V halmaz készítése során. A fenti lépéseket véges sokszor alkalmazva megkapjuk az Y minimális feszítőfát.
Párhuzamos algoritmusok
A Prim-algoritmus fő hurka eredendően szekvenciális, tehát nem párhuzamosítható. A belső hurok, amely meghatározza a következő minimális súlyú élt, ami nem alkot kört, párhuzamosítható úgy, hogy a csúcsokat és az éleket megosztja a rendelkezésre álló processzorok között.[2] A következő pszeudokód ezt szemlélteti.
1. Rendeljünk hozzá minden egyes Pi processzorhoz egy Vi halmazt az egymást követő csúcsok halmazából, melyek hossza . |
2. Hozzuk létre a C, E , F és Q halmazokat, mint a szekvenciális algoritmusban, és osszuk fel C-t, E-t, valamint a gráfot az összes processzor között, mégpedig úgy, hogy minden processzor tárolja a bejövő éleket a csúcsok halmazában. |
3. Ismételjük a következő lépéseket addig, amíg Q nem üres. a, Minden processzor: keresse meg a vi csúcsot, aminek a Ci[vi] (helyi megoldás) értéke minimális. b, Csökkentsük ezeket az értékeket (minimumcsökkentés), hogy megtaláljuk azt a v csúcsot, amelyre a lehető legkisebb a C[v] érték (globális megoldás). c, Adjuk meg a kiválasztott csomópontot minden processzornak. d, Adjuk hozzá v-t az F halmazhoz, és ha E[v] nem az indikátorérték, adjuk hozzá E[v]-t is az F halmazhoz. e, Minden processzoron frissítsük Ci és Ei halmazokat. |
4. Térjünk vissza F-fel. |
Ez az algoritmus általában megosztott gépeken,[2] valamint megosztott memóriákat használó eszközökön is megvalósítható.[3] Grafikus feldolgozó egységeken (GPU) is futtatták már.[4] A futási idő , feltételezve, hogy a redukciós és a sugárzási műveletek végrehajthatók időn belül.[2] A Prim egy olyan változata is létezik már, amelyben a Prim szekvenciális algoritmust párhuzamosan hajtjuk végre, különböző csúcsoktól indulva, olyan eszközökön, melyek megosztják a memóriakapacitásukat.[5] Meg kell azonban jegyezni, hogy léteznek kifinomultabb algoritmusok az megosztott minimális feszítőfa probléma hatékonyabb megoldására.
Jegyzetek
Dijkstra algoritmusa, egy nagyon hasonló algoritmus a legrövidebb út problémájához.
Források
- V. Jarník: O jistém problému minimálním (Egy bizonyos minimális problémáról), Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57–63. (cseh nyelven)
- R. C. Prim: Shortest connection networks and some generalizations, Bell System Technical Journal, 36 (1957), pp. 1389–1401. Online hozzáférés
- D. Cheriton, R. E. Tarjan: Finding minimum spanning trees, SIAM Journal on Computing, 5 (Dec. 1976), pp. 724–741
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Új algoritmusok, Scolar Kiadó, 2003.
- Rosen, Kenneth (2011) Discrete Mathematics and Its Applications, (7th ed.), McGraw-Hill Science, p. 798
- Wang, Wei; Huang, Yongzhong; Guo, Shaozhong (2011). "Design and Implementation of GPU-Based Prim's Algorithm". International Journal of Modern Education and Computer Science 3.4.
- Setia, Rohit (2009). "A new parallel algorithm for minimum spanning tree problem". Proc. International Conference on High Performance Computing (HiPC).
Kapcsolódó szócikkek
- Minimális feszítőfa
- Kruskal-algoritmus
Jegyzetek
- ↑ Andrásfai Béla: Ismerkedés a gráfelmélettel, Tankönyvkiadó, Budapest, 1971,
- ↑ a b c Grama, Ananth. Introduction to Parallel Computing, 444–446. o. (2003). ISBN 978-0201648652
- ↑ Quinn (1984. szeptember 9.). „Parallel graph algorithms”. ACM Computing Surveys 16 (3), 319–348. o. DOI:10.1145/2514.2515.
- ↑ Wang (2011. szeptember 9.). „Design and Implementation of GPU-Based Prim's Algorithm”. International Journal of Modern Education and Computer Science 3.4.
- ↑ Setia (2009. szeptember 9.). „A new parallel algorithm for minimum spanning tree problem”. Proc. International Conference on High Performance Computing (HiPC).
További információk
- Animáció
- Java applet
Informatikai portál
Matematikaportál