2016-01-05

Kruskalův algoritmus - implementace a rozbor

Ve škole jsem měl v rámci zbrusu nového předmětu Matematika pro zpracování znalostí vytvořit implementaci Kruskalova algoritmu včetně dokumentace a hlavně teoretického rozboru. Protože nerad ukládám práci do šuplíku, rád se podělím s případnými dalšími řešiteli o své myšlenky.


Předně měla být kritériem hodnocení délka běhu programu. Cílem mělo být udělat program efektivní. resp. nedělat ho zbytečně neefektivní. Jenže zadávající vyučující nepředpokládal, že se do toho studenti pustí ve vyšších programovacích jazycích (C# / Java), kde třeba na prohledání slovníku stačí konstantní čas O(1), a to už je rozdíl proti seznamu s lineárním časem O(n). Stejně šlo všechno snažení mimo hlavní směr neboť nakonec se testování omezilo na minimálním vzorek dat... Nyní ale k algoritmu samotnému.


Zadání

V ohodnocených grafech určete všechny nejlevnější kostry grafu pomocí Kruskalova algoritmu. 

Motivace

Proč hledat minimální kostru v grafových úlohách? Zde uvádím pouze několik zjevných příkladů použití.

Návrh elektrické sítě

Máme k dispozici seznam odběrných míst a chceme je propojit tak, abychom využili co nejmenší množství drátů. Tímto problémem se zabýval mimo jiné český vědec Otakar Borůvka, který ve svém článku „O jistém problému minimálním“ z roku 1926 publikoval algoritmus, který se zabýval návrhem efektivní elektrické sítě na Moravě. Později jeho práci využil také americký matematik Joseph Kruskal.

Smyčky v počítačových sítích

Spanning Tree Protocol (v překladu protokol kostry grafu) je v informatice název pro síťový protokol, který v ethernetových sítích odstraňuje smyčky na druhé vrstvě ISO/OSI modelu. Výpočet provádí aktivní prvek (switch), který odpojí redundantní spoje, které v síti způsobují nezastavitelné množení zpráv určených všem příjemcům (broadcast). 

Teorie

Kruskalův algoritmus pracuje na principu spojování hran s nejmenším ohodnocením, dokud tyto hrany nespojí všechny vrcholy v grafu. Takto vzniklý podgraf nazýváme kostrou grafu. Význam “koster” spočívá v jejich minimalitě vzhledem k počtu hran, přičemž je zachována souvislost grafu.

 Matematický zápis: Je dán souvislý ohodnocený graf G s nezáporným ohodnocením hran w: E(G) → R0+. Problém minimální kostry znamená najít takovou kostru T v grafu G, která má nejmenší možnou váhu. MST (z anglického “Minimum spanning tree“) je tedy číslo, které udává váhu kostry s nejmenší možnou vahou.

Předpoklady

  • Graf je souvislý (projekt umí najít i více koster v nespojitém grafu)
  • Graf je neorientovaný (případnou orientaci zahazuje)
  • Graf je vážený (hrany mají kladné ohodnocení)

Pseudokód

Kruskal(vrcholy V, hrany H, ceny c)
{
MST := ∅; //kostra je prázdná
for každý vrchol v ∈ V
          do MAKE-SET(v); //vytvoří samostatný podstrom pro každý vrchol
for každou hranu h(x, y) ∈ H v pořadí neklesajících ceny c
          if FIND-SET(x) != FIND-SET(y) //pokud jsou podstromy různé
               then MST := MST ∪ h(x, y);  //přidej hranu do kostry
               UNION(x, y); //spoj odpovídající podstromy
return MST
}

Vizualizace hledání

Pro doplnění představy o způsobu přidávání hran do kostry.

Časová složitost Kruskalova algoritmu 

Nejprve je třeba uvážit čas nutný k setřízení hran podle velikosti ceny / váhy od největší po nejmenší. Je obecně známé, že u řazení, které je založeno na porovnávání dvojic klíčů (což je univerzální metoda použitelná pro libovolná data a která je v projektu implementována), je minimální časová složitost O(H log V).

Kruskalův algoritmus najde minimální kostru v čase:
O(H log V + H · Tfind (V) + V · Tunion(V))
kde Tfind(V) a Tunion(V) jsou časové složitosti operací Find a Union na grafech s V vrcholy a H hranami, které patří do struktury Union-Find, kterou jsem do projektu implementoval. H log V + H je již zmíněná časová náročnost řazení hran.
  • Operaci find (zjistí, zda vrcholy v1 a v2 leží v téže komponentě) implementuji ve svém projektu jako cyklus nad hranami, složitost je tedy O(H).
  • Operaci union (přidá hranu v1 a v2, čili dvě komponenty spojí do jedné) implementuji v projektu jako průchod cyklem nad vrcholy v menší komponentě před spojením dvou listů. Náročnost operace je opět O(Vmenšíkomponenty) kterou můžeme zjednodušeně vyjádřit jako O(V).
Pro shrnutí tedy:
O(H log V + H + V)
V souladu s pravidly asymptotické složitosti můžeme dále zanedbat aditivní konstanty, čímž dostaneme výslednou složitost:
O(H log V)
Tato složitost je ekvivalentní se složitosti O(H log H), protože pokud V je počet vrcholů a H počet hran, tak H = V2 v nejhorším případě. Při matematické úpravě H log V2 = 2 H log V to při  zjednodušení odpovídá O(H log V).

Třída algoritmu

Hladové algoritmy fungují na principu, že se prostřednictvím lokálního optima snažíme dospět ke globálnímu optimu neboli také, pokud se musím rozhodnout, pak vždy beru aktuálně nejlepší možnost bez ohledu na budoucnost.

Lze dokázat, že hladový algoritmus najde minimální kostru grafu. V případě Kruskalova algoritmu se hladovosti dobře využívá, neboť hrany jsou před začátkem seřazeny podle ceny od nejlevnější, po přidání hrany se zjišťuje, zda-li nevznikla minimální kostra a tak nevložením horších hran nedojde k ovlivnění výsledku.

Obecným příkladem je úloha „dobře se najíst“, což je žádoucí globální optimum. Chceme-li se dobře najíst a máme před sebou stůl plný potravin, začneme pravděpodobně tím, na co máme největší chuť (lokální optimum). Až nám tato potravina dojde, budeme pokračovat druhou nejchutnější věcí, a tak dále. Na konci algoritmu budeme dobře najedení a spokojení.

Obecně hladové algoritmy nemusí poskytovat správné výsledky: Je třeba si uvědomit je fakt, že je nutné je provést nad všemi vyhodnocovanými objekty. Mohlo by totiž dojít ke stavu v následujícím příkladu hledání maxima, kdy volbou lokálního maxima přehlédneme maximum globální.

Je zřejmé, že pro obrovská množství dat není možné provést v konečném čase výpočet nad každým vrcholem a proto se v praxi využívá “hladovosti” nad velkými daty pouze jako jednoduchého heuristického nástroje. Pro komplexní hledání globálních extrémů je možné využít například algoritmus SOMA (Self-Organizing Migrating Algorithm) či některý z dalších biologicky inspirovaných algoritmů probíraných ve stejnojmenném kurzu.

Implementace

Je provedena v objektovém prostředí jazyka C# včetně všech vhodných nativních knihoven. Projekt je pro snadné ovládání doplněn o grafické uživatelské rozhraní v češtině. Použito bylo prostředí .NET framework verze 3.5, která je výchozí verzí v operačním systému Windows 7.

 Zde se hodí poznamenat, že realizované řešení nekopíruje přesně dané zadání. Vlivem chyby paralaxu došlo k podstatnému zjednodušení, takže namísto:
V ohodnocených grafech určete všechny nejlevnější kostry grafu pomocí Kruskalova algoritmu. 
se mi podařilo najít jen
V ohodnocených grafech určete první nejlevnější kostry grafů pomocí Kruskalova algoritmu. 
Jak opravit projekt tak, aby splňoval původní zadání jsem doplnil do prezentace. Nejúčinnější bude pravděpodobně použití systémového volání fork na vytvoření "kopie" procesu se svou vlastní pamětí, která dokáže vytvářet variace na původní graf za podmínek existence grafu.

Download

Projekt se zdrojovými kódy ve Visual Studiu 2015 je možné si stáhnout z tohoto odkazu včetně testovacích dat. Prezentaci zde. CC-BY 2015 Ivo Kostecký

Struktura vstupních dat

Vrchol 1 hrany 1 (int); Vrchol 2 hrany 1 (int); nezáporná metrika hrany (decimal)
Vzhledem k vágnímu zadání potencionálních vstupů není v projektu implementována vyšší než nutná ochrana proti nevyžádánemu vstupu.


Upozornění pro výstupní data

Výstup kruskalova algoritmu, tedy kostry grafů jsou poskytovány opět ve formátu CSV kompatibilním se vstupem programu. Tato struktura neumožňuje odlišení jednotlivých koster a proto jsou kostry / komponenty řazeny za sebou BEZ viditelného oddělení. Pokud potřebujete kopomenty rozlišit, využijte prvky uživatelského rozhraní, kde jsou náležitě dokumentovány výsledky.

Výsledky

Na grafu o 7000 vrcholech a 18 373 348 hranách

Otevírám z: <<cesta>>\7000.csv
Uložím do: <<cesta>>\vysledky.csv
Nyní prosím vyčkejte na výsledky úlohy.
--------------------------------------------------------
Uloha dokoncena! Čas běhu 760,0453156s.
--------------------------------------------------------
Graf má 1 koster.
Kostra "0" má vrcholů "7000" a hran "6999".
--------------------------------------------------------
Celkový počet vrcholů: 7000.
Celkový počet hran: 6999.

Na grafu o 1500 vrcholech a 843 051 hranách

Otevírám z: <<cesta>>\1500.csv
Uložím do: <<cesta>>\vysledky.csv
Nyní prosím vyčkejte na výsledky úlohy.
--------------------------------------------------------
Uloha dokoncena! Čas běhu 8,9579028s.
--------------------------------------------------------
Graf má 1 koster.
Kostra "0" má vrcholů "1500" a hran "1499".
--------------------------------------------------------
Celkový počet vrcholů: 1500.
Celkový počet hran: 1499.

Na grafu o 6301 vrcholech a 20 777 hranách

Otevírám z: <<cesta>>\OrientOhodG2.csv
Uložím do: <<cesta>> \vysledky.csv
--------------------------------------------------------
Uloha dokoncena! Čas běhu 0,0890054s.
--------------------------------------------------------
Graf má 2 koster.
Kostra "0" má vrcholů "6299" a hran "6298".
Kostra "1" má vrcholů "2" a hran "1".
--------------------------------------------------------
Celkový počet vrcholů: 6301.
Celkový počet hran: 6299.

Zdroje informací


 Pro další doplnění nebo opravu můžete použít komentáře pod tímto textem.

Autor
Štítky: ,

Žádné komentáře :

Okomentovat

Dotaz, připomínka, oprava?
(pokud máte problém s vložením příspěvku, vyzkoušejte to v prohlížeči Chrome)