Očekávaný algoritmus MST s lineárním časem - Expected linear time MST algorithm

The očekávaný algoritmus MST s lineárním časem je randomizovaný algoritmus pro výpočet minimální les a vážený graf bez č izolované vrcholy. Byl vyvinut společností David Karger, Philip Klein a Robert Tarjan.^[1] Algoritmus se opírá o techniky z Borůvkův algoritmus spolu s algoritmem pro ověření minimálního kostry v lineárním čase.^[2][3] Kombinuje paradigmata designu algoritmy rozděl a panuj, chamtivé algoritmy, a randomizované algoritmy dosáhnout očekávaný lineární výkon.

Mezi ně patří deterministické algoritmy, které najdou minimální kostru Primův algoritmus, Kruskalův algoritmus, algoritmus zpětného mazání, a Borůvkův algoritmus.

Přehled

Klíčovým vhledem do algoritmu je krok náhodného vzorkování, který rozděluje graf na dva podgrafy náhodným výběrem hran, které se mají zahrnout do každého podgrafu. Algoritmus rekurzivně najde minimální les prvního dílčího problému a používá řešení ve spojení s algoritmem lineárního ověřování času k vyřazení hran v grafu, které nemohou být v minimálním rozpětí stromu. Ke snížení velikosti grafu u každého se také používá postup převzatý z Borůvkova algoritmu rekurze.

Borůvka Step

Každá iterace algoritmu závisí na adaptaci Borůvkova algoritmu označovaného jako a Borůvka krok:

 Vstup: Graf G bez izolovaných vrcholů 1 Pro každý vrchol proti, vyberte nejsvětlejší hranu dopadající na proti    2 Vytvořte kontraktovaný graf G' nahrazením každé součásti G spojeny hranami vybranými v kroku 1 jediným vrcholem 3 Odeberte všechny izolované vrcholy, smyčky a minimální opakující se hrany z G'  Výstup: Hrany vybrané v kroku 1 a kontrakční graf G'

Krok Borůvka je ekvivalentní vnitřní smyčce Borůvkova algoritmu, který běží dovnitř Ó(m) čas kde m je počet hran v G. Kromě toho, protože každou hranu lze vybrat maximálně dvakrát (jednou každým dopadajícím vrcholem), maximální počet odpojených komponent po kroku 1 se rovná polovině počtu vrcholů. Krok Borůvka tedy snižuje počet vrcholů v grafu alespoň o faktor dva a odstraní alespoň n/ 2 hrany kde n je počet vrcholů v G.

Příklad provedení kroku Borůvka

obraz	Popis
	Nejsvětlejší hrana dopadající na každý vrchol je zvýrazněna zeleně.
	Graf je zkrácen a každá složka spojená hranami vybranými v kroku 1 je nahrazena jediným vrcholem. Tak vzniknou dva supernody. Všechny hrany z původního grafu zůstanou.
	Okraje, které vytvářejí vlastní smyčky k supernodům, jsou odstraněny.
	Minimální redundantní hrany mezi supernody jsou odstraněny.
	Výsledkem jednoho kroku Borůvka na ukázkovém grafu je graf se dvěma supernody spojenými jedinou hranou.

F-těžké a F-světlé hrany

V každé iteraci algoritmus odstraní hrany s konkrétními vlastnostmi, které je vylučují z minimální kostra. Tito se nazývají F-těžké hrany a jsou definovány následovně. Nechat F být lesem na graf H. F-těžká hrana je hrana E spojovací vrcholy u,proti jehož váha je přísně větší než váha nejtěžší hrany na cestě od u na proti v F. (Pokud cesta neexistuje v F považuje se za nekonečnou váhu). Jakákoli hrana, která není F-těžká, je Let. Li F je podgraf z G pak jakýkoli F-těžký okraj dovnitř G nemůže být v minimálním kostře stromu G podle vlastnost cyklu. Vzhledem k lesu lze vypočítat F-těžké hrany lineární čas pomocí algoritmu pro ověření minimálního spanningového stromu.^[2][3]

Algoritmus

Vstup: Graf G bez izolovaných vrcholů

1. Li G je prázdný vrátí prázdný les
2. Vytvořte smluvní graf G' spuštěním dvou po sobě jdoucích kroků Borůvky G
3. Vytvořte podgraf H výběrem každé hrany v G' s pravděpodobností 1/2. Rekurzivně použijte algoritmus na H získat jeho minimální les F.
4. Odstraňte všechny F-těžké hrany z G' (kde F je les z kroku 3) pomocí algoritmu ověření lineárního minimálního rozpětí stromu.^[2][3]
5. Rekurzivně použijte algoritmus na G' získat jeho minimální les.

Výstup: Minimální lesní oblast o G' a smrštěné hrany z Borůvkových schodů

Správnost

Správnost se dokazuje indukcí počtu vrcholů v grafu. Základní případ je triviálně pravdivý. Nechat T * být minimálním kostrou stromu G. Každá hrana vybraná v kroku Borůvka je uvnitř T * podle vlastnost cut a žádný z okrajů odstraněných pro vytvoření kontraktovaného grafu není T * podle vlastnost cut (pro nadbytečné okraje) a vlastnost cyklu (pro vlastní smyčky). Zbývající okraje T * není vybrán v kroku 2 z minimální kostra smluvního grafu vlastnost cut (ať je každý řez supernodou). Každý F-těžká hrana odstraněno není v minimálním spanning stromu stromem vlastnost cyklu. Konečně F' je minimální rozpětí stromu kontraktovaného grafu indukční hypotézou. Tím pádem F' a hrany smrštěné hrany z kroků Borůvky tvoří minimální kostru.

Výkon

Očekávaný výkon je výsledkem kroku náhodného vzorkování. Účinnost kroku náhodného vzorkování je popsána následujícím lemmatem, které omezuje počet Let hrany dovnitř G čímž se omezuje velikost druhého dílčího problému.

Lema náhodného vzorkování

Lemma- Nechte H být podgrafem G tvořený zahrnutím každého okraje G nezávisle s pravděpodobností str a nechte F být minimálním lesem o velikosti H. The očekávané číslo z Let hrany dovnitř G je nanejvýš n / p kde n je počet vrcholů v G

Chcete-li dokázat, že lemma prozkoumá okraje G jak jsou přidávány H. Počet Let hrany dovnitř G je nezávislá na pořadí, ve kterém jsou hrany H jsou vybrány od minimálního lesního porostu o H je stejný pro všechny objednávky výběru. Z důvodu kontroly zvažte výběr hran pro H tím, že hrany G jeden po druhém v pořadí podle hmotnosti hran od nejlehčí po nejtěžší. Nechat E být uvažovaná aktuální hrana. Pokud jsou koncové body E jsou ve dvou odpojených součástech H pak E je nejlehčí hrana spojující tyto komponenty a pokud je přidána do H bude to v F podle vlastnost cut. To také znamená E je Let bez ohledu na to, zda je či není přidán do H protože následně jsou uvažovány pouze těžší hrany. Pokud jsou oba koncové body E jsou ve stejné složce H pak je (a vždy bude) F-těžký vlastnost cyklu. Okraj E je poté přidán do H s pravděpodobností str.

Maximální počet Let okraje přidány do H je n-1 od jakéhokoli minimálního kostry o H má n-1 hrany. Jednou n-1 F-light edge have been added to H žádná z následujících hran považovaných za F-light není vlastnost cyklu. Tedy počet hran F světla v G je omezen počtem hran F světla uvažovaných pro H před n-1 F-light edge are actually added to H. Protože jakýkoli okraj F-světla je přidán s pravděpodobností str to odpovídá převrácení mince s pravděpodobností str přicházet hlavy až do nObjevilo se -1 hlav. Celkový počet otočení mince se rovná počtu hran F světla G. Rozdělení počtu otočení mince je dáno číslem inverzní binomické rozdělení s parametry n-1 a str. U těchto parametrů je očekávaná hodnota této distribuce (n-1)/str.

Očekávaná analýza

Ignorování práce provedené v rekurzivních dílčích problémech je celkové množství práce vykonané v jediném vyvolání algoritmu lineární v počtu hran ve vstupním grafu. Krok 1 trvá konstantní čas. Kroky Borůvky lze provádět časově lineárně v počtu hran, jak je uvedeno v Borůvka krok sekce. Krok 3 iteruje přes okraje a převrátí jednu minci pro každou z nich, takže je lineární v počtu okrajů. Krok 4 lze provést v lineárním čase za použití modifikovaného algoritmu pro ověření minimálního lineárního času přes rozpětí stromu.^[2][3] Vzhledem k tomu, že práce provedená v jedné iteraci algoritmu je lineární v počtu hran, je práce vykonaná v jednom úplném běhu algoritmu (včetně všech rekurzivních volání) omezena konstantním faktorem krát celkový počet hran v původním problému a všechny rekurzivní dílčí problémy.

Každé vyvolání algoritmu vytváří nejvýše dva dílčí problémy, takže sada dílčích problémů tvoří a binární strom. Každý Borůvka krok snižuje počet vrcholů alespoň o faktor dva, takže po dvou krocích Borůvky byl počet vrcholů snížen o faktor čtyři. Pokud tedy původní graf má n vrcholy a m hrany pak do hloubky d stromu je každý dílčí problém maximálně na grafu n/4^d vrcholy. Také strom má nanejvýš log₄n úrovně.

Levé cesty binárního stromu jsou zakroužkovány modře

Chcete-li uvažovat o rekurzivním stromu, nechte problém levého dítěte být dílčím problémem v rekurzivním volání v kroku 3 a problém pravého dítěte je dílčím problémem v rekurzivním volání v kroku 5. Spočítejte celkový počet hran v původním problému a všech dílčích problémech spočítáním počtu hran v každé levé cestě stromu. Levá cesta začíná buď u pravého potomka, nebo u kořene a zahrnuje všechny uzly dosažitelné cestou levých dětí. Levé cesty binárního stromu jsou v diagramu vpravo zobrazeny modře zakroužkované.

Každá hrana v levém podřízeném problému je vybrána z okrajů jeho nadřazeného problému (bez hran smluvně v Borůvka kroky ) s pravděpodobností 1/2. Pokud má problém rodič X hrany pak očekávané číslo hran v levém podřízeném problému je nanejvýš X/ 2. Li X je nahrazena náhodnou proměnnou X pak u linearita očekávání očekávaný počet hran v levém podřízeném problému Y darováno ${ displaystyle E [Y] leq E [X] / 2}$. Pokud je tedy očekávaný počet hran v problému v horní části levé cesty k pak je součet očekávaného počtu hran v každém dílčím problému v levé dráze nanejvýš ${ displaystyle sum _ {d = 0} ^ { infty} { frac {k} {2 ^ {d}}} = 2k}$ (vidět Geometrická řada ). Kořen má m hrany tak očekávané číslo hran se rovná 2m plus dvojnásobek očekávaného počtu hran v každém pravém dílčím problému.

Očekávaný počet hran v každém pravém dílčím problému se rovná počtu Let hrany v nadřazeném problému, kde F je minimální kostra levého dílčího problému. Počet hran F světla je menší nebo roven dvojnásobku počtu vrcholů v dílčím problému pomocí odběrové lemma. Počet vrcholů v dílčím problému v hloubce d je n/4^d takže celkový počet vrcholů ve všech pravých dílčích problémech je dán vztahem ${ displaystyle sum _ {d = 1} ^ { infty} { frac {2 ^ {d-1} n} {4 ^ {d}}} = n / 2}$. Očekávaný počet hran v původním problému a všech dílčích problémech je tedy maximálně 2m+n. Od té doby n maximálně 2m pro graf bez izolovaných vrcholů se algoritmus spustí v očekávaném čase Ó(m).

Analýza nejhorších případů

Nejhorší případ runtime je ekvivalentní runtime Borůvkův algoritmus. K tomu dojde, pokud jsou při každém vyvolání přidány všechny hrany k levému nebo pravému dílčímu problému. V tomto případě je algoritmus identický s Borůvkův algoritmus který běží dovnitř Ó(min {n², mlogn}) na grafu s n vrcholy a m hrany.

Reference

Další čtení

• Minimální ověření stromu v lineárním čase