Primov algoritmus: Rozdiel medzi revíziami

z Wikipédie, slobodnej encyklopédie
Smazaný obsah Přidaný obsah
Juraj21 (diskusia | príspevky)
d →‎Referencie: externé odkazy
Juraj21 (diskusia | príspevky)
štylistika
Riadok 1: Riadok 1:
'''Primov algoritmus ''' (známy aj ako '''Jarníkov algoritmus''', '''Primov-Jarníkov algoritmus''' alebo aj '''DJP algoritmus''') je v informatike [[pažravý algoritmus|greedy algoritmus]] hľadajúci minimálnu [[kostra grafu | kostru]] ohodnoteného grafu. Nájde teda takú podmnožinu hrán grafu, ktorá tvorí [[strom (graf)|strom]] obsahujúci všetky vrcholy pôvodného grafu a súčet ohodnotenia hrán z tejto množiny je minimálny. Algoritmus patrí medzi najefektívnejšie a najelegantnejšie implementovateľné algoritmy s týmto účelom. Prvýkrát algoritmus popísal český matematik [[Vojtěch Jarník]] roku [[1930]]. V roku [[1957]] ho nezávisle na Jarníkovi popísal americký matematik a informatik Robert Clay Prim a potom ešte raz v roku [[1959]] tento algoritmus znovu objavil holandský informatik [[Edsger Wybe Dijkstra]] a na jeho základe vytvoril svoj [[Dijkstrov algoritmus]] na hľadanie najkratšej cesty v ohodnotenom grafe.
'''Primov algoritmus ''' (známy aj ako '''Jarníkov algoritmus''', '''Primov-Jarníkov algoritmus''' alebo aj '''DJP algoritmus''') je v informatike [[pažravý algoritmus|greedy algoritmus]] hľadajúci minimálnu [[kostra grafu | kostru]] ohodnoteného grafu. Nájde teda takú podmnožinu hrán grafu, ktorá tvorí [[strom (graf)|strom]] obsahujúci všetky vrcholy pôvodného grafu a súčet ohodnotenia hrán z tejto množiny je minimálny. Algoritmus patrí medzi najefektívnejšie a najelegantnejšie implementovateľné algoritmy s týmto účelom. Prvýkrát algoritmus popísal český matematik [[Vojtěch Jarník]] roku [[1930]]. V roku [[1957]] ho nezávisle na Jarníkovi popísal americký matematik a informatik Robert Clay Prim a potom ešte raz v roku [[1959]] tento algoritmus znovu objavil holandský informatik [[Edsger Wybe Dijkstra]] a na jeho základe vytvoril svoj [[Dijkstrov algoritmus]] na hľadanie najkratšej cesty v ohodnotenom grafe.



== Popis ==
== Popis ==
Riadok 10: Riadok 11:
** Pridaj ''v'' do V', pridaj (u,v) do E'
** Pridaj ''v'' do V', pridaj (u,v) do E'
* Výstup: T(V',E') je minimálna kostra grafu
* Výstup: T(V',E') je minimálna kostra grafu



== Časová zložitost ==
== Časová zložitost ==
Riadok 24: Riadok 26:
Jednoduchá implementácia s reprezentáciou grafu pomocou matice susednosti a prehľadávaním poľa ohodnotení má časovú zložitosť ''O(n<sup>2</sup>)''. S použitím binárnej haldy a zoznamu susedov dosiahneme zložitosť ''O(m log n)'', kde m je počet hrán a n je počet vrcholov. S použitím sofistikovanej Fibonacciho haldy zložitosť znížime až na ''O(m + n log n)'', čo je výhodné najmä pri grafoch, kde ''m'' je <math>\Omega(n)</math>.
Jednoduchá implementácia s reprezentáciou grafu pomocou matice susednosti a prehľadávaním poľa ohodnotení má časovú zložitosť ''O(n<sup>2</sup>)''. S použitím binárnej haldy a zoznamu susedov dosiahneme zložitosť ''O(m log n)'', kde m je počet hrán a n je počet vrcholov. S použitím sofistikovanej Fibonacciho haldy zložitosť znížime až na ''O(m + n log n)'', čo je výhodné najmä pri grafoch, kde ''m'' je <math>\Omega(n)</math>.


== Príklad ==


== Príklad ==
{| border=1 cellspacing=2 cellpadding=5 class="wikitable"
{| border=1 cellspacing=2 cellpadding=5 class="wikitable"
! Obrázok !! Popis
! Obrázok !! Popis
Riadok 53: Riadok 55:
|Teraz sú už vybrané všetky vrcholy a teda sme získali minimálnu kostru grafu (vyznačená zelenou farbou). Celková váha kostry je 39.
|Teraz sú už vybrané všetky vrcholy a teda sme získali minimálnu kostru grafu (vyznačená zelenou farbou). Celková váha kostry je 39.
|}
|}



== Dôkaz korektnosti algoritmu ==
== Dôkaz korektnosti algoritmu ==
Nech ''G'' je súvislý ohodnotený graf. V každej iterácii Primovho algoritmu je pridaná hrana, ktorá má jeden vrchol v podgrafe vytvárajúcom kostru a vrchol mimo tohto podgrafu. Pretože ''G'' je súvislý, existuje vždy cesta do každého vrcholu. Výstup ''Y'' Primovho algoritmu je strom, pretože vrchol a hrana, ktoré sú pridané do ''Y'' sú spojené. Nech ''Y1'' je minimálna kostra ''G''. Ak ''Y1=Y'', tak ''Y'' je minimálna kostra. Inak, nech ''e'' je prvá hrana pridaná počas konštrukcie ''Y'', ktorá nie je v ''Y1'', a ''V'' nech je množina vrcholov spojených hranami pridanými pred pridaním ''e''. Potom jeden koncový bod ''e'' je vo ''V'' a druhý nie je. Pretože ''Y1'' je kostra ''G'', existuje cesta v ''Y1'' spájajúca tieto dva koncové vrcholy. Keď prechádzame pozdĺž tejto cesty, musíme naraziť na hranu ''f'' spájajúcu vrchol vo ''V'' s vrcholom, ktorý nie je vo ''V''. Teraz, v iterácii, keď je pridávaná hrana ''e'' do ''Y'', ''f'' by mohla byť pridaná tiež a mohla by byť pridaná namiesto ''e'', ak by jej ohodnotenie bolo menšie ako ''e''. Pretože ''f'' nebola pridaná, ohodnotenie ''f'' nie je menšie ako ohodnotenie ''e''. Nech ''Y2'' je graf získaný z ''Y1'' odstránením ''f'' a pridaním ''e''. Je ľahké ukázať, že ''Y2'' je súvislý, má ten istý počet hrán ako ''Y1'' a celková váha jeho hrán nie je väčšia ako v ''Y1'', preto je to tiež minimálna kostra ''G'' a obsahuje ''e'' a všetky hrany pridané pred ''e'' počas konštrukcie ''V''. Opakovaním vyššie uvedených krokov vieme získať minimálnu kostru grafu ''G'', ktorá je identická s ''Y''. Toto dokazuje, že ''Y'' je minimálna kostra.
Nech ''G'' je súvislý ohodnotený graf. V každej iterácii Primovho algoritmu je pridaná hrana, ktorá má jeden vrchol v podgrafe vytvárajúcom kostru a vrchol mimo tohto podgrafu. Pretože ''G'' je súvislý, existuje vždy cesta do každého vrcholu. Výstup ''Y'' Primovho algoritmu je strom, pretože vrchol a hrana, ktoré sú pridané do ''Y'' sú spojené. Nech ''Y1'' je minimálna kostra ''G''. Ak ''Y1=Y'', tak ''Y'' je minimálna kostra. Inak, nech ''e'' je prvá hrana pridaná počas konštrukcie ''Y'', ktorá nie je v ''Y1'', a ''V'' nech je množina vrcholov spojených hranami pridanými pred pridaním ''e''. Potom jeden koncový bod ''e'' je vo ''V'' a druhý nie je. Pretože ''Y1'' je kostra ''G'', existuje cesta v ''Y1'' spájajúca tieto dva koncové vrcholy. Keď prechádzame pozdĺž tejto cesty, musíme naraziť na hranu ''f'' spájajúcu vrchol vo ''V'' s vrcholom, ktorý nie je vo ''V''. Teraz, v iterácii, keď je pridávaná hrana ''e'' do ''Y'', ''f'' by mohla byť pridaná tiež a mohla by byť pridaná namiesto ''e'', ak by jej ohodnotenie bolo menšie ako ''e''. Pretože ''f'' nebola pridaná, ohodnotenie ''f'' nie je menšie ako ohodnotenie ''e''. Nech ''Y2'' je graf získaný z ''Y1'' odstránením ''f'' a pridaním ''e''. Je ľahké ukázať, že ''Y2'' je súvislý, má ten istý počet hrán ako ''Y1'' a celková váha jeho hrán nie je väčšia ako v ''Y1'', preto je to tiež minimálna kostra ''G'' a obsahuje ''e'' a všetky hrany pridané pred ''e'' počas konštrukcie ''V''. Opakovaním vyššie uvedených krokov vieme získať minimálnu kostru grafu ''G'', ktorá je identická s ''Y''. Toto dokazuje, že ''Y'' je minimálna kostra.



== Referencie ==
== Referencie ==

Verzia z 18:37, 27. máj 2011

Primov algoritmus (známy aj ako Jarníkov algoritmus, Primov-Jarníkov algoritmus alebo aj DJP algoritmus) je v informatike greedy algoritmus hľadajúci minimálnu kostru ohodnoteného grafu. Nájde teda takú podmnožinu hrán grafu, ktorá tvorí strom obsahujúci všetky vrcholy pôvodného grafu a súčet ohodnotenia hrán z tejto množiny je minimálny. Algoritmus patrí medzi najefektívnejšie a najelegantnejšie implementovateľné algoritmy s týmto účelom. Prvýkrát algoritmus popísal český matematik Vojtěch Jarník roku 1930. V roku 1957 ho nezávisle na Jarníkovi popísal americký matematik a informatik Robert Clay Prim a potom ešte raz v roku 1959 tento algoritmus znovu objavil holandský informatik Edsger Wybe Dijkstra a na jeho základe vytvoril svoj Dijkstrov algoritmus na hľadanie najkratšej cesty v ohodnotenom grafe.


Popis

Algoritmus začína s jedným vrcholom a postupne pridáva ďalšie, čím zväčšuje veľkosť stromu dovtedy, kým neobsahuje všetky vrcholy.

  • Vstup: súvislý ohodnotený graf G(V,E)
  • Inicializácia: V' = {x}, kde x je ľubovoľný vrchol z V, E' = {}
  • Opakuj, kým neplatí, že V'=V:
    • Vyber hranu (u,v) z E s minimálnou cenou tak, že u patrí V' a v nepatrí V'
    • Pridaj v do V', pridaj (u,v) do E'
  • Výstup: T(V',E') je minimálna kostra grafu


Časová zložitost

Dátová štruktúra s ohodnotením hrán Celková časová zložitosť
matica susednosti O(n2)
binárna halda a zoznam susedov O((n + m) log(n)) = n log(n)
Fibonacciho halda a zoznam susedov O(m + n log(n))

Jednoduchá implementácia s reprezentáciou grafu pomocou matice susednosti a prehľadávaním poľa ohodnotení má časovú zložitosť O(n2). S použitím binárnej haldy a zoznamu susedov dosiahneme zložitosť O(m log n), kde m je počet hrán a n je počet vrcholov. S použitím sofistikovanej Fibonacciho haldy zložitosť znížime až na O(m + n log n), čo je výhodné najmä pri grafoch, kde m je .


Príklad

Obrázok Popis
Toto je náš pôvodný ohodnotený graf. Čísla na okrajoch hrán označujú ich váhu.
Z grafu vyberieme ľubovoľný vrchol. V tomto prípade vrchol D. Tým nám vznikne podgraf. Vrcholy A, B, E a F sú susednými vrcholmi D, teda sú s ním spojené hranou. Vrchol A je od vrcholu D vzdialený najmenej a bude vybraný ako druhý vrchol, spolu s hranou AD.
Ďalším vybraným vrcholom bude vrchol, ktorý ma najmenšiu vzdialenosť od D alebo A. B má vzdialenosť od A 7 a od D 9. E je od D vzdialený 15 a F zase 6. Cena hrany DF je najnižšia, preto ako ďalší vrchol vyberieme F a ako hranu DF.
Algoritmus pokračuje ako v predchádzajúcich krokoch. Vyberieme vrchol B, a hranu AB.
V tomto prípade si môžeme vybrať medzi troma ešte nevybranými vrcholmi C, E a G. Spomedzi nich má E najmenšiu vzdialenosť od už vybraných vrcholov (7 od B). Preto vyberieme vrchol E a hranu BE.
Jediné vrcholy prichádzajúce do úvahy sú C a G. C je vzdialený 5 od E a G je vzdialený 9 od E. Vyberieme C spolu s hranou EC.
Vrchol G je jediný zvyšný vrchol. Od F má vzdialenosť 11, a od E 9. K E je bližšie, preto spolu s ním vyberieme aj hranu EG.
Teraz sú už vybrané všetky vrcholy a teda sme získali minimálnu kostru grafu (vyznačená zelenou farbou). Celková váha kostry je 39.


Dôkaz korektnosti algoritmu

Nech G je súvislý ohodnotený graf. V každej iterácii Primovho algoritmu je pridaná hrana, ktorá má jeden vrchol v podgrafe vytvárajúcom kostru a vrchol mimo tohto podgrafu. Pretože G je súvislý, existuje vždy cesta do každého vrcholu. Výstup Y Primovho algoritmu je strom, pretože vrchol a hrana, ktoré sú pridané do Y sú spojené. Nech Y1 je minimálna kostra G. Ak Y1=Y, tak Y je minimálna kostra. Inak, nech e je prvá hrana pridaná počas konštrukcie Y, ktorá nie je v Y1, a V nech je množina vrcholov spojených hranami pridanými pred pridaním e. Potom jeden koncový bod e je vo V a druhý nie je. Pretože Y1 je kostra G, existuje cesta v Y1 spájajúca tieto dva koncové vrcholy. Keď prechádzame pozdĺž tejto cesty, musíme naraziť na hranu f spájajúcu vrchol vo V s vrcholom, ktorý nie je vo V. Teraz, v iterácii, keď je pridávaná hrana e do Y, f by mohla byť pridaná tiež a mohla by byť pridaná namiesto e, ak by jej ohodnotenie bolo menšie ako e. Pretože f nebola pridaná, ohodnotenie f nie je menšie ako ohodnotenie e. Nech Y2 je graf získaný z Y1 odstránením f a pridaním e. Je ľahké ukázať, že Y2 je súvislý, má ten istý počet hrán ako Y1 a celková váha jeho hrán nie je väčšia ako v Y1, preto je to tiež minimálna kostra G a obsahuje e a všetky hrany pridané pred e počas konštrukcie V. Opakovaním vyššie uvedených krokov vieme získať minimálnu kostru grafu G, ktorá je identická s Y. Toto dokazuje, že Y je minimálna kostra.


Referencie

V tomto článku je použitý preklad časti textu z článku Prim's algorithm na anglickej Wikipedii.