Primův algoritmus - Prim's algorithm

Demo pro Primův algoritmus založené na euklidovské vzdálenosti

Ve výpočetní technice je Primův algoritmus (také známý jako Jarníkův algoritmus) chamtivý algoritmus, který najde minimální kostru pro vážený neorientovaný graf . To znamená, že najde podmnožinu hran, která tvoří strom zahrnující každý vrchol , kde je celková hmotnost všech hran ve stromu minimalizována. Algoritmus funguje tak, že vytvoří tento strom po jednom vrcholu z libovolného počátečního vrcholu, přičemž v každém kroku přidá nejlevnější možné spojení ze stromu do jiného vrcholu.

Algoritmus byl vyvinut v roce 1930 českým matematikem Vojtěchem Jarníkem a později znovu objeven a znovu publikován počítačovými vědci Robert C. Prim v roce 1957 a Edsger W. Dijkstra v roce 1959. Proto je také někdy nazýván Jarníkovým algoritmem , Prim – Jarníkovým algoritmem , Prim –Dijkstra algoritmus nebo DJP algoritmus .

Mezi další známé algoritmy pro tento problém patří Kruskalův algoritmus a Borůvkův algoritmus . Tyto algoritmy najdou minimální lesní pole v případně odpojeném grafu; Naproti tomu nejzákladnější forma Primova algoritmu najde v propojených grafech pouze minimální stromy. Nicméně, když spustíte Primův algoritmus samostatně pro každou připojenou komponentu grafu, lze jej také použít k nalezení minimální struktury překlenutí. Pokud jde o jejich asymptotickou časovou složitost , tyto tři algoritmy jsou pro řídké grafy stejně rychlé , ale pomalejší než jiné sofistikovanější algoritmy. U grafů, které jsou dostatečně husté, lze však Primův algoritmus spustit tak, aby běžel v lineárním čase , což splňuje nebo zlepšuje časové limity pro jiné algoritmy.

Primův algoritmus začínající na vrcholu A. Ve třetím kroku mají hrany BD a AB váhu 2, takže BD se volí libovolně. Po tomto kroku již AB není kandidátem na přidání do stromu, protože spojuje dva uzly, které již ve stromu jsou.

Popis

Algoritmus lze neformálně popsat jako provádění následujících kroků:

  1. Inicializujte strom s jediným vrcholem, zvoleným libovolně z grafu.
  2. Pěstujte strom o jednu hranu: z hran, které spojují strom s vrcholy, které ještě ve stromu nejsou, najděte hranu s minimální hmotností a přeneste ji do stromu.
  3. Opakujte krok 2 (dokud nejsou všechny vrcholy ve stromu).

Podrobněji může být implementován podle níže uvedeného pseudokódu .

  1. Ke každému vrcholu v grafu přiřaďte číslo C [ v ] (nejlevnější náklady na připojení k v ) a hranu E [ v ] (hrana poskytující nejlevnější připojení). Chcete -li tyto hodnoty inicializovat, nastavte všechny hodnoty C [ v ] na +∞ (nebo na libovolné číslo větší než maximální hmotnost hrany) a nastavte každé E [ v ] na speciální hodnotu příznaku označující, že neexistuje žádná hrana spojující v s dříve vrcholy.
  2. Inicializujte prázdnou doménu F a množinu Q vrcholů, které ještě nebyly zahrnuty do F (zpočátku všechny vrcholy).
  3. Opakujte následující kroky, dokud není Q prázdné:
    1. Najděte a odeberte vrchol v z Q s minimální možnou hodnotou C [ v ]
    2. Přidejte v do F a pokud E [ v ] není speciální hodnota příznaku, přidejte také E [ v ] do F
    3. Smyčka přes okraje vw spojující v s jinými vrcholy w . Pokud pro každou takovou hranu w stále patří Q a vw má menší hmotnost než C [ w ], proveďte následující kroky:
      1. Nastavte C [ w ] na cenu edge vw
      2. Nastavte E [ w ] tak, aby směřovalo k okraji vw .
  4. Návrat F

Jak je popsáno výše, počáteční vrchol pro algoritmus bude vybrán libovolně, protože první iterace hlavní smyčky algoritmu bude mít sadu vrcholů v Q, které mají všechny stejnou váhu, a algoritmus automaticky spustí nový strom v F, když dokončí strom span každé připojené komponenty vstupního grafu. Algoritmus může být upraven tak, aby začít s některou konkrétní vrchol s nastavením C [ s ], že je číslo menší než ostatní hodnoty C (například nula), a může být modifikován tak, aby pouze najít jednu kostru, nikoli celý překlenovací les (přesněji odpovídá neformálnímu popisu) zastavením, kdykoli narazí na jiný vrchol označený jako bez přidruženého okraje.

Různé variace algoritmu se od sebe navzájem liší tím, jak je množina Q implementována: jako jednoduchý propojený seznam nebo pole vrcholů nebo jako komplikovanější datová struktura fronty . Tato volba vede k rozdílům v časové složitosti algoritmu. Obecně bude prioritní fronta rychlejší při hledání vrcholu v s minimálními náklady, ale bude znamenat nákladnější aktualizace, když se změní hodnota C [ w ].

Časová náročnost

Primův algoritmus má mnoho aplikací, například při generování tohoto bludiště, které aplikuje Primův algoritmus na náhodně vážený mřížkový graf .

Časová složitost Primova algoritmu závisí na datových strukturách použitých pro graf a pro řazení hran podle hmotnosti, což lze provést pomocí prioritní fronty . Následující tabulka ukazuje typické možnosti:

Datová struktura minimální hmotnosti hrany Časová náročnost (celkem)
sousední matice , hledání
binární hromada a sousední seznam
Fibonacciho hromada a sousední seznam

Jednoduchá implementace Prim's, pomocí matice sousednosti nebo grafu seznamu sousedních grafů a lineárního prohledávání pole vah k nalezení hrany minimální hmotnosti, která se má přidat, vyžaduje dobu běhu O (| V | 2 ). Tuto dobu běhu lze však dále výrazně zlepšit použitím haldy k implementaci nalezení hran minimální hmotnosti ve vnitřní smyčce algoritmu.

První vylepšená verze používá hromadu k uložení všech okrajů vstupního grafu seřazeného podle jejich hmotnosti. To vede k nejhorší době běhu O (| E | log | E |). Ale ukládání vrcholů místo hran to může ještě zlepšit. Halda by měla uspořádat vrcholy podle nejmenší hrany, která je spojuje s jakýmkoli vrcholem v částečně konstruovaném minimálním překlenovacím stromu (MST) (nebo nekonečno, pokud žádná taková hrana neexistuje). Pokaždé, když je zvolen vrchol v a přidán do MST, je provedena operace s klíčem snížení na všech vrcholech w mimo dílčí MST tak, že v je připojeno k w , přičemž je klíč nastaven na minimum jeho předchozí hodnoty a nákladů na hranu z ( v , w ).

Pomocí jednoduché binární datové struktury haldy lze nyní ukázat, že Primův algoritmus běží v čase O (| E | log | V |) kde | E | je počet hran a | V | je počet vrcholů. Pomocí sofistikovanější hromady Fibonacciho to lze snížit na O (| E | + | V | log | V |), což je asymptoticky rychlejší, když je graf dostatečně hustý , aby | E | je ω (| V |) a lineární čas, když | E | je nejméně | V | log | V |. U grafů s ještě větší hustotou (které mají alespoň | V | c hrany pro některé c  > 1) lze Primův algoritmus spustit tak, aby běžel v lineárním čase ještě jednodušeji, pomocí d -haldové hromady místo Fibonacciho hromady.

Demonstrace důkazu. V tomto případě je graf Y 1 = Y - f + e je již rovná Y . Obecně může být nutné proces opakovat.

Doklad o správnosti

Nechť P je spojený, vážený graf . Při každé iteraci Primova algoritmu musí být nalezena hrana, která spojuje vrchol v podgrafu s vrcholem mimo podgraf. Protože P je připojeno, vždy bude existovat cesta ke každému vrcholu. Výstupem Y Primova algoritmu je strom , protože hrana a vrchol přidané do stromu Y jsou propojeny. Nechť Y 1 je minimální kostra grafu P. Pokud Y 1 = Y, pak Y je minimální kostra. Jinak nechť e je první hrana přidaná během stavby stromu Y, která není ve stromu Y 1 , a V je množina vrcholů spojených hranami přidanými před hranu e . Pak je jeden koncový bod hrany e v sadě V a druhý ne. Protože strom Y 1 je klenutý strom grafu P , existuje ve stromu Y 1 cesta spojující dva koncové body. Jako jeden pohybuje podél dráhy, musí narazit na hranu f spojující vrchol v souboru V, na tu, která není v souboru V . Nyní, při iteraci, kdy byla hrana e přidána do stromu Y , mohla být také přidána hrana f a byla by přidána místo hrany e, pokud by její hmotnost byla menší než e , a protože hrana f nebyla přidána, usuzujeme, že

Nechť strom Y 2 je graf získaný odstraněním hrany f z a přidáním hrany e ke stromu Y 1 . Je snadné ukázat, že strom Y 2 je připojen, má stejný počet hran jako strom Y 1 a celková hmotnost jeho okrajů není větší než u stromu Y 1 , proto je také minimálním překlenovacím stromem grafu P a obsahuje okraj e a všechny hrany přidané před ním při stavbě nastavené v . Opakujte výše uvedené kroky a se konečně získá minimálně kostra graf P , která je identická s stromu Y . To ukazuje, že Y je minimální klenutý strom. Strom minimálního rozpětí umožňuje, aby byla první podmnožina podoblasti rozšířena na menší podmnožinu X , což považujeme za minimum.

Paralelní algoritmus

Matice sousednosti distribuovaná mezi více procesorů pro paralelní Primův algoritmus. V každé iteraci algoritmu každý procesor aktualizuje svou část C kontrolou řádku nově vloženého vrcholu ve své sadě sloupců v matici sousedství. Výsledky se poté shromáždí a globálně se vybere další vrchol, který se má zahrnout do MST.

Hlavní smyčka Primova algoritmu je ze své podstaty sekvenční, a proto není paralelizovatelná . Avšak vnitřní smyčka , která určuje další okraj minimální hmotnost, která není tvoří kruh, může být paralelizovat vydělením vrcholy a hrany mezi dostupnými procesory. Následující pseudokód to dokazuje.

  1. Přiřaďte každému procesoru sadu po sobě jdoucích vrcholů délky .
  2. Vytvořte C, E, F a Q jako v sekvenčním algoritmu a rozdělte C, E, stejně jako graf mezi všechny procesory tak, aby každý procesor držel příchozí hrany do své sady vrcholů. Nechť , označují části C , E uložena na procesoru .
  3. Opakujte následující kroky, dokud není Q prázdné:
    1. Na každém procesoru: najděte vrchol s minimální hodnotou v [ ] (lokální řešení).
    2. Minimálně zmenšete lokální řešení, abyste našli vrchol v s minimální možnou hodnotou C [ v ] (globální řešení).
    3. Vysílat vybraný uzel na každý procesor.
    4. Přidat VF , a pokud E [ v ] Není zvláštní hodnota vlajka, také přidat E [ v ] na F .
    5. Na každém procesoru: aktualizace a jako v sekvenčním algoritmu.
  4. Návrat F

Tento algoritmus lze obecně implementovat na distribuovaných počítačích i na počítačích se sdílenou pamětí. Byl také implementován na grafických procesorových jednotkách (GPU). Doba běhu je za předpokladu, že operace snížení a vysílání lze provádět v . Byla také prozkoumána varianta Primova algoritmu pro počítače se sdílenou pamětí, ve kterém je Primův sekvenční algoritmus spuštěn paralelně, počínaje různými vrcholy. Je však třeba poznamenat, že existují sofistikovanější algoritmy k efektivnějšímu řešení problému distribuovaného minimálního překlenovacího stromu .

Viz také

Reference

externí odkazy