Prim-algoritmus

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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 összefüggő grfában 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 lasabb 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[szerkesztés]

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á.

Prim-algoritmus szemléltetése euklideszi távolságon alapulva.

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.

Ex prim.JPG Ex prim 1.JPG 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ú.

Ex prim.JPG Ex prim 2.JPG 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ú.

Ex prim.JPG Ex prim 3.JPG 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ú.

Ex prim.JPG Ex prim 4.JPG 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!

Ex prim.JPG Ex prim 5.JPG 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ú.

Ex prim.JPG Ex prim 6.JPG 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ú.

Ex prim.JPG Ex prim 7.JPG 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-
Ex prim.JPG Ex prim 8.JPG 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[szerkesztés]

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[szerkesztés]

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 hoázzadva 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[szerkesztés]

A Prim algoritmusának 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 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 a ezeket az értékeket (minimum csö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, Addjuk hozzá v 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- el.

Ez az algoritmus általában megosztott gépeken [3], valamint megosztott memóriákat használó eszközökön is megvalósítható. [4] Grafikus feldolgozó egységeken (GPU) is futatták már. [5] A futási idő , feltételezve, hogy a redukciós és a sugárzási műveletek végrehajthatók időn belül. [3] 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 eszkzökön melek megosztják a memóriakapacitásukat. [6] Meg kell azonban jegyezni, hogy léteznek kifinomultabb algoritmusok az megosztott minimális feszítőfa probléma hatékonyabb megoldására.

Jegyzetek[szerkesztés]

Dijkstra algoritmusa, egy nagyon hasonló algoritmus a legrövidebb út problémájához

Források[szerkesztés]

  • 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[szerkesztés]

Jegyzetek[szerkesztés]

  1. Andrásfai Béla: Ismerkedés a gráfelmélettel, Tankönyvkiadó, Budapest, 1971,
  2. Grama, Ananth. Introduction to Parallel Computing, 444–446. o. (2003). ISBN 978-0201648652 
  3. a b Grama, Ananth. Introduction to Parallel Computing, 444–446. o. (2003). ISBN 978-0201648652 
  4. Quinn (1984. szeptember 12.). „Parallel graph algorithms”. ACM Computing Surveys 16 (3), 319–348. o. DOI:10.1145/2514.2515.  
  5. Wang (2011. szeptember 12.). „Design and Implementation of GPU-Based Prim's Algorithm”. International Journal of Modern Education and Computer Science 3.4.  
  6. Setia (2009. szeptember 12.). „A new parallel algorithm for minimum spanning tree problem”. Proc. International Conference on High Performance Computing (HiPC).  

További információk[szerkesztés]