IN16 Třídění a Grafové algoritmy

Zadání

(základní algoritmy, algoritmy řazení haldou, slučováním, rozdělováním)
(procházení grafu do hloubky a do šířky, složitost procházení grafu, komponenty souvislosti, hledání nejkratších cest, toky v sítích, kostra grafu)

Algoritmy vnitřního třídění

Vnitřní třídění je takové třídění, kdy předem známe tříděné prvky a máme k dispozici dostatek volné paměti, abychom je uvnitř této paměti mohli setřídit. Opakem je pak třídění vnější, kdy jednotlivé prvky předem neznáme a musíme je ze vstupu postupně načítat v pořadí, v jakém přicházejí. Toto třídění se provádí typicky v situacích, kdy máme operační paměti málo a nejsme schopni v ní všechny prvky uložit. Ve vnějším třídění proto využijeme vnější paměti - pracujeme s jednotlivými soubory na disku. Teoreticky tak můžeme setřídit daleko větší množství dat, operace s vnější pamětí jsou však také podstatně pomalejší. Práce se soubory rychlé algoritmy podstatně degraduje.

Úlohu vnitřního třídění založeného na porovnávání dvou prvků lze vždy řešit algoritmem se složitostí ve třídě O(n log n) (takové výborné složitosti dosahuje Heap Sort). Některé jiné algoritmy (Quick Sort, nejrychlejší algoritmus v průměrném případě) mohou v ideálním případě dosahovat i lineární složitosti (O(n)), jiné zase často dosahují složitostí vyšších (O(n²)).

Select Sort

Uspořádávání přímým výběrem
Přímý výběr je přímočarý a jednoduchý algoritmus, který je vhodné použít u krátkých polí. Algoritmus projde celé pole a najde nejmenší prvek, který prohodí s prvním prvkem pole. Takto získané pole má nejmenší prvek na začátku. Algoritmus pokračuje hledáním nejmenšího čísla, které umístí na pozici o jednu větší, než při předchozím průchodu.

Složitost algoritmu Select Sort je O(n²).
Max Sort - algoritmus téměř totožný s Select Sortem, jen probíhá obráceně (od největšího k nejmenšímu).

Bubble Sort

Bublinkové třídění
Tento algoritmus je velmi pomalý v neuspořádaných polích, ale zato velmi efektivní v polích částečně uspořádaných. Postupně se systematicky porovnávají dvojice sousedních prvků a vyměňují se spolu vždy, když menší číslo následuje po větším. Po prvním průchodu FOR cyklem je zajištěno, že největší číslo je na konci pole. Druhý průchod už můžeme provádět jen ve zbytku pole. Po ukončení druhého průchodu jsou největší dvě čísla správně umístěna. Celý postup opakujeme až do uspořádání celého pole.
Průměrná i nejhorší asymptotická složitost je O(n²).
Shake Sort - Třídění přetřásáním - vychází z bublinkového třídění, které zlepšuje tak, že probublávají střídavě malá čísla na levý okraj a velká čísla na pravý okraj.

Insert Sort

Třídění vkládáním
Třídění vkládáním je rychlejší než Select Sort, ale pomalé vzhledem ke Quick Sortu. Třídící metoda spočívá ve vkládání čísla před nejmenší větší číslo. Vkládání probíhá do neustále se zvětšující části pole (seřazené).
Pozn. Prvky se vybírají jen z nesetříděné části pole.

Merge Sort

Třídění slučováním
Tento algoritmus rozdělí pole na dvě přibližně stejně velké části. Poté s každou z těchto částí učiní totéž – rozdělí na dvě, dokud nedostaneme jednoprvkové úseky. Jednopoložkové úseky jsou vždy utříděné, takže teď bereme utříděné úseky a slučujeme tak, aby byly zase utříděné(2 úseky se musí znovu setřídit, ne jen spojit). Končíme, až když uspořádáme celé pole. Složitost Merge Sortu je O(n log n).

Příklad

Máme posloupnost 2 1 3 4 7 6 8 5. Posloupnost dělíme na půlky a tvoříme strom. Až
dorazíme na jednoprvkové listy, sléváme vždy dvojice.

Výhody a nevýhody: Velkou nevýhodou oproti algoritmům stejné rychlostní třídy (např. Heapsort) je, že Mergesort pro svou práci potřebuje navíc pole o velikosti N. Existuje sice i modifikace Mergesortu, která toto pole nepotřebuje, ale její implementace je velmi složitá a díky vysokému overheadu i pomalá. Kromě toho se Mergesort také ukazuje být pomalejší než Quicksort nebo Heapsort. Na druhou stranu je Mergesort stabilní řadící algoritmus, lépe se paralelizuje a má vyšší výkon na sekvenčních médiích s nižší přístupovou dobou. V mnoha implementacích programovacích jazyků je Mergesort implicitním řadícím algoritmem (v Perlu 5.8, v Javě nebo v GNU C Library). ¹⁾

SUPER programek pro pochopeni MergeSortu

Heap Sort

Třídění pomocí „haldy“

V Heap Sortu se nejdříve vytvoří (binární) haldy. Binární halda je binární strom, pro který platí:

Délky všech větví se liší nejvýše o 1: mají délku k, případně k − 1. Číslu k pak říkáme hloubka haldy.
Pokud nejhlubší úroveň haldy není kompletně zaplněna, uzly na této úrovni jsou zaplňovány zleva.
Hodnoty uzlů na každé větvi jsou vzestupně (sestupně) uspořádány.

Jsou-li hodnoty uzlů na každé větvi seřazeny vzestupně (čím dále od kořene, tím větší hodnoty), je v kořenu haldy nejmenší prvek. Hovoříme pak o minimové haldě (min-heap).
Jsou-li hodnoty uzlů na každé větvi seřazeny sestupně (čím dále od kořene, tím menší hodnoty), je v kořenu haldy největší prvek. Hovoříme pak o maximové haldě (max-heap).²⁾

Věta: Neprázdná binární halda na n uzlech má hloubku $\lfloor log_2n\rfloor$ .³⁾

Z výše uvedeného vyplývá, že každé patro haldy musí být kompletně zaplněno, pouze poslední patro nemusí mít plný počet prvků. Při přidání dalšího prvku se musí pole znovu „uhaldovat“ – prvek se přidá jako syn a pokud je menší (v případě min-heapu)/větší (v případě max-heapu) než otec, potom se s ním vymění. Pokud je i pak jeho otec menší/větší než přidaný prvek, opět se prohodí atd.

Věta: Algoritmus řazení haldou má složitost Θ(n log n). ⁴⁾

Práci s haldou je možné si interaktivně vyzkoušet.

Ve funkcionální implementaci algoritmu řazení haldou, kde se pracuje s explicitní haldou (datovou strukturou binární strom), použijeme minimovou haldu. Naopak v imperativní implementaci, kde se pracuje s implicitní haldou (reprezentovanou polem), je výhodnější použít maximovou haldu.⁵⁾

Quick Sort

Řazení rozdělováním
Jedná se o rekurzivní třídění

Quick Sort je znatelně nejrychlejší ze zde zmíněných algoritmů. Princip Quick Sortu je velmi jednoduchý – pouze rozdělí čísla na menší a větší. Při opětovném zavolání se rozdělí menší zase na menší-menší a menší-větší a toto se provede i u větších (rozdělí se na větší-menší a větší-menší). Pří dalším zavolání se zase rozdělí každá část na menší a větší, až zbude v každé části pouze jedno číslo, nebo bude daná část uspořádaná.

Jiná definice

Základní myšlenkou Quick Sortu je rozdělení řazené posloupnosti čísel na dvě přibližně stejné části (Quick Sort patří mezi algoritmy typu „rozděl a panuj“). V jedné části jsou čísla větší a ve druhé menší, než nějaká zvolená hodnota (nazývaná pivot). Pokud je tato hodnota zvolena dobře, jsou obě části přibližně stejně velké. Pokud budou obě části samostatně seřazeny, je seřazené i celé pole. Obě části se pak rekurzivně řadí stejným postupem.

Příklad:

Máme posloupnost 5 1 3 4 7 6 8 2. Z posloupnosti vybereme nějaké číslo (a právě výběr tohoto čísla působí na složitost). Následně posloupnost rozdělíme na dvě části. V první části budou všechna čísla menší než zvolené číslo, v druhé části pak čísla větší nebo rovná vybranému číslu.

QuickSort ve funkcionálním zápisu

quickSort :: [Int] -> [Int] 
 quickSort [] = [] 
 quickSort (p:t) = quickSort lt ++ [p] ++ quickSort ge 
                   where lt = [ x | x <- t, x < p ] 
                         ge = [ x | x <- t, x ≥ p ]

Funkce algoritmu je dostatečně zřejmá z komentářů, takže stručně o co jde: Quick Sort vychází z rekurzivního přístupu – pokud máme třídit elementární pole o dvou prvcích, prvky jednoduše přehodíme na tu stranu, kam patří (porovnat je můžeme s pomyslnou hodnotou mezi nimi – pivotním prvkem). Pokud máme třídit pole větší, roztřídíme takto podle zvoleného pivota i dva velké úseky pole, které potom dále necháme třídit rekurzivně stejnou procedurou, až budou nakonec uspořádány všechny části pole. Tento algoritmus je typickým příkladem použití metody „rozděl a panuj“ (Divide & Impera), kdy programátor daný problém rozdělí na více jednoduchých elementárních problémů, které lze snadno vyřešit (třeba rekurzí). Pokud si vzpomenete na tento princip a vybavíte si postup, určitě pak budete schopni jednotlivé detaily algoritmu snadno doprogramovat.

Průměrná složitost Quick Sortu je O(n log n), přesněji O(n log₂n). Stejně tak nejlepší případ, ve kterém je vždy vybrán pivot jako prvek s prostřední hodnotou, má časovou složitost O(n log n), nejhorší případ O(n²) nastává, pokud je pivot vždy nešikovně vybrán jako hodnota maximální nebo minimální. Výše uvedená procedura vybírá pivotní prvek jako střed pole, záleží ale na rozložení vstupních dat, každý z prvků pole je pro určitou kombinaci ideální, výběr se proto někdy provádí náhodně (pomocí generátoru náhodných čísel), což zaručuje, že při různém výběru pivotů nebude volba pro vstupní data vyloženě nevhodná a složitost se tak více přiblíží k očekávané složitosti O(n log n). V průměrném případě se v pravé a levé části pole zaměňuje vždy polovina prvků – pro jednotlivé zmenšující se úseky tedy $n\over 2$ , $n\over 4$ , $n\over 8$ , $n\over 16$ … – a vzhledem k tomu, že po záměně prvků se každé pole rozdvojuje na dvě poloviny (políčka si můžeme nakreslit do vyváženého binárního stromu), je složitost násobena dvojkovým logaritmem (zhruba zapisujeme jen logaritmus desítkový). Výsledná průměrná složitost je tedy intuitivně:

log n ( $n\over 2$ + $n\over 4$ + $n\over 8$ + $n\over 16$ + …) = n log n

Procházení grafu do hloubky a do šířky

Prohledávání do hloubky

Prohledávání do hloubky (v angličtině označované jako depth-first search nebo zkratkou DFS) je grafový algoritmus pro procházení grafů metodou backtrackingu. Pracuje tak, že vždy expanduje prvního následníka každého vrcholu, pokud jej ještě nenavštívil. Pokud narazí na vrchol, z nějž už nelze dále pokračovat (nemá žádné následníky nebo byly všichni navštíveni), vrací se zpět backtrackingem.

Backtracking (česky zpětné vyhledávání) je způsob řešení algoritmických problémů založený na metodě pokus – omyl. Jedná se o vylepšení hledání řešení hrubou silou v tom, že velké množství potenciálních řešení může být vyloučeno bez přímého vyzkoušení. Algoritmus je založen na procházení do hloubky možných řešení.

Algoritmus je úplný (vždy najde řešení, tzn. určitý cílový vrchol, pokud existuje), ale není optimální (pokud graf není strom, nemusí najít nejkratší možnou cestu k cíli). Jeho asymptotická složitost je O(|V| + |E|), kde V je množina vrcholů a E množina hran daného grafu.

Podle pořadí, ve kterém se prochází uzly uspořádaného stromu, se rozlišují tři metody.

Výsledky způsobů procházení v binárním vyhledávacím stromu:

N = navštívený uzel, L = levý, R = pravý

Preorder (NLR): F, B, A, D, C, E, G, I, H
Inorder (LNR): A, B, C, D, E, F, G, H, I
Postorder (LRN): A, C, E, D, B, H, I, G, F
(Procházení do šířky (po vrstvách) Level-order: F, B, G, A, D, I, C, E, H)

Algoritmus prohledávání do hloubky s omezením na maximální délku větve.

CLOSED = $\emptyset$ , OPEN = {S₀}, kde S₀ je počáteční stav. Je-li S₀ současně i cílový stav, pak ukonči prohledávání.
Je-li OPEN prázdný, řešení neexistuje → ukonči prohledávání!
Vyber a současně vymaž první stav ze seznamu OPEN, označ jej i a zapiš jej do seznamu CLOSED.
Pokud se hloubka uzlu i rovná maximální přípustné hloubce MAX, pokračuj krokem č. 2.
Expanduj stav i. Pokud stav i nemá následovníky, nebo všichni následovníci byli již expandováni (tj. jsou v seznamu CLOSED), jdi na krok č. 2.
Zapiš všechny následovníky stavu i, kteří nejsou v seznamu CLOSED na začátek seznamu OPEN.
Pokud některý z následovníků stavu je cílovým stavem, tj. řešení bylo právě nalezeno, ukonči prohledávání, jinak pokračuj krokem č. 2.

animace prohledávání do hloubky

Algoritmus a příklad z FI MUNI

Prohledávat graf do hloubky od uzlu x znamená, že do zásobníku na počátku dáme prvek x.
Následně s každým výběrem prvku ze zásobníku do něj dáme jeho následovníky.

Algoritmus podle skript

Algoritmus dfs (depth-first search)
$G = (V,E)$ , $V = \{1, \dots , n\}$ , $W \subseteq V$ Budeme označovat všechny navštívené uzly pomocí procedury mark.
Na začátku jsou všechny uzly nenavštívené (marked(u) = False).
Pro každý uzel u je Successors(u) seznam uzlů-následníků uzlu u.
Vycházíme z uzlů z množiny W a postupujeme stále dál po hranách do dosud nenavštívených uzlů.
Cesty z označených do nově navštívených uzlů tvoří les s kořeny ve W.

Chceme-li projít do hloubky všechny uzly grafu G = (V,E), položíme W = V.
Věta: Algoritmus dfs navštíví všechny uzly grafu dosažitelné z uzlů z množiny W.
Důkaz je zřejmý a plyne z toho, že se opakovaně označují všechny uzly, které dosud označeny nebyly. Množina neoznačených uzlů se zmenšuje, takže algoritmus konverguje.
Poznámka: Algoritmus funguje stejně pro orientované i neorientované grafy.

Prohledávání do šířky

Prohledávání do šířky (anglicky Breadth-first search, zkráceně BFS) je grafový algoritmus, který postupně prochází všechny vrcholy v dané komponentě souvislosti. Algoritmus nejprve projde všechny sousedy startovního vrcholu, poté sousedy sousedů atd. až projde celou komponentu souvislosti.

Jak to funguje?

Prohledávání do šířky je algoritmus či metoda, která postupuje systematickým prohledáváním grafu přes všechny uzly. Nepoužívá při svém prohledávání žádnou heuristickou analýzu, pouze prochází všechny uzly a pro každý projde všechny jeho následovníky. Přitom si poznamenává předchůdce jednotlivých uzlů a tím je poté vytvořen strom nejkratších cest k jednotlivým uzlům z kořene (uzlu, ve kterém jsme začínali) v hranovo neohodnotenom grafe.

Z hlediska algoritmu, veškeré následovníky uzlu získané expanzí uzlu vkládáme do FIFO fronty. FIFO fronta znamená, že první uzel, který do fronty vstoupil, ji také první opustí. V typických implementacích jsou dosud neobjevené označeny jako FRESH. Uzly, které se dostávají do fronty a jsou v této chvíli právě vyšetřovány na jejich následníky, jsou označeny jako OPEN a naposled uzly, které už byly z fronty vybrány a dále se s nimi nebudeme pracovat, jsou označeny jako CLOSE. CLOSE uzly již nikdy v tomto běhu algoritmu nebudou prozkoumávány, mají vyplněné všechny informace. To znamená vzdálenost od kořenového (počátečního) uzlu, stav uzlu (CLOSE) a předchůdce.

Algoritmus prohledávání do šířky

CLOSED = $\emptyset$ , OPEN = {S₀}, kde S₀ je počáteční stav. Je-li S₀ současně i cílový stav, pak ukonči prohledávání.
Je-li OPEN prázdný, řešení neexistuje → ukonči prohledávání!
Vyber a současně vymaž první stav ze seznamu OPEN, označ jej i a zapiš jej do seznamu CLOSED.
Expanduj stav i. Pokud stav i nemá následovníky, nebo všichni následovníci byli již expandováni (tj. jsou v seznamu CLOSED), jdi na krok č. 2.
Zapiš všechny následovníky stavu i, kteří nejsou v seznamu CLOSED na začátek seznamu OPEN.
Pokud některý z následovníků stavu je cílovým stavem, tj. řešení bylo právě nalezeno, ukonči prohledávání, jinak pokračuj krokem č. 2.

animace procházení do šířky

Algoritmus z FIMUNI

Prohledávat graf do šířky od nějakého uzlu x, znamená, že na začátku dáme do fronty FIFO uzel x. Následně vždy z fronty vybereme prvek, zapíšeme jej, a do fronty přidáme jeho následovníky.

Algoritmus podle skript

Řešíme problém Projít systematicky všechny uzly grafu G = (V,E) dosažitelné (orientovanou) cestou z některého z počátečních uzlů zadaných množinou $W \subseteq V$ .

Algoritmus bfs (breadth-first search) prochází uzly v jiném pořadí než při prohledávání do hloubky: uzly, které leží blíže počátečním uzlům (uzlům, v nichž procházení začíná), jsou navštíveny dříve než uzly ležící dále od počátečních uzlů.

Pomocné datové struktury: fronta Q uzlů, les nejkratších cest (uložený v poli P)
Navštívené uzly se opět označují pomocí procedury mark, uzel u bude označen, právě když marked(u) = True.

Věta: Nechť $G = (V,E)$ , $s, u, v \in V$ a nechť vzdálenost z s do u je menší než vzdálenost z s do v. Pak uzel u bude při výpočtu bfs(G,{s}) označen dříve než uzel v.

Důkaz: Stačí ukázat, že do fronty Q jsou vždy přidávány uzly s aspoň tak velkou vzdáleností od s, než jakou měl poslední přidaný uzel. To však lehce plyne indukcí podle vzdálenosti od uzlu s.

Věta: Nechť $G = (V,E), s \in V$ . Pak po provedení výpočtu bfs(G,{s}) jsou navštíveny právě všechny uzly, do nichž vede z uzlu s (orientovaná) cesta.
Důkaz: Indukcí podle vzdálenosti od uzlu s.

Složitost procházení grafu do šířky Věta: Nechť G = (V,E) je graf a $W \in V$ je množina počátečních uzlů (vstupního stupně 0). Pak délka výpočtu bfs(G,W) v nejhorším případě je v O(|W| + |E|).

Složitost procházení grafu

Složitost procházení do hloubky

Celková složitost algoritmu : O(|V| + |E|), kde V je počet vrcholů a E počet hran daného grafu.

Složitost procházení do šířky

Asymptotická časová složitost algoritmu je O(|V| + |E|), kde V je množina vrcholů a E je množina hran grafu.

Prostorová složitost je O(|V| + |E|). Řečeno jinak, prostorová složitost je O(B^M), kde B je nejvyšší stupeň větvení stromu a M je nejvyšší délka cesty ve stromě. Tento velký nárok na prostor ve srovnání s nárokem prohledávání do hloubky je důvod, proč je prohledávání do šířky nepraktické pro rozsáhlejší problémy.

Borůvkův-Kruskalův algoritmus

Asymptotická složitost: Řazení hran má asymptotickou složitost O(|H| · log |H|), množinový rozklad pak O(|H| · log* |U|), kde log* je velmi pomalu rostoucí inverzní Ackermannova funkce s jedním parametrem. Celková asymptotická složitost Borůvkova-Kruskalova algoritmu je tedy O(|H| · log |H|).

Jarníkův-Primův algoritmus

Asymptotická složitost: Počáteční nastavení má asymptotickou složitost O(|U|), získání minimálního prvku z fronty zabere čas O(|U| · log |U|). For cyklus přes všechny sousedy uzlu se provede O(|H|)-krát a zjištění, zda je prvek ve frontě (ke kterému dochází uvnitř tohoto cyklu) trvá O(log |U|). Celková asymptotická složitost Jarníkova-Primova algoritmu je tedy O(|U|) + O(|U| · log |U|) + O(|H| · log |U|) = O(|H| · log |U|).

Dijkstrův algoritmus

složitost O(|U|²), při implementaci haldou O(|H|·log|U|)

Bellmanův - Fordův algoritmus

složitost obecně O(|U|·|H|), pro acyklické grafy lze upravit na O(|U|+|H|) (topologické uspořádání uzlů)

Floyd - Warshall

operační složitost O(|U|3), paměťová O(|U|2)

Komponenty súvislosti

Nech G=(V,E), komponenta súvislosti je maximálna podmnožina $K \subset V$ , pre ktorú platí, že medzi každými 2 vrcholmi vedie neorientovaná cesta. Ak v celom grafe medzi každými 2 vrcholmi vedie cesta, graf je súvislý (komponenta súvislosti je v tom prípade celý graf).
Všetky komponenty súvislosti môžeme nájsť pomocou prehľadávania do šírky.

Hľadanie najkratších ciest

Daný je orientovaný graf G=(V,E) spolu s ohodnotením hrán $w: H \rightarrow R$ . Sled $p = <v_0,v_1,...,v_k>$ má dĺžku, ktorá je súčtom jeho hrán:
$w(p) = \sum_{i=1}^{k} w(v_{i-1},v_i)$ Cyklus $c = <v_0,v_1,...,v_k>, v_0 = v_k$ nazývame záporný cyklus práve keď jeho dĺžka $w(c) < 0$ .
Definujeme dĺžku najkratšej cesty z u do v:

$\delta(u,v) = \infty$ ak neexistuje cesta z u do v
$\delta(u,v) = - \infty$ ak nejaká cesta z u do v obsahuje vrchol patriaci zápornému cyklu
$min\{w(p)|p=<u,...,v>\}$ inak (p je sled medzi u a v)

Hlavné problémy spojené s najkratšími cestami a algoritmy, ktoré sa používajú k ch riešeniu:

Najkratšie cesty z daného vrcholu s do ostatných vrcholov grafu. Algoritmy: Bellman-Fordov alg., Alg. pre acyklické grafy, Dijkstrov alg. pre grafy s nezápornými dĺžkami hrán
Najkratšie cesty medzi všetkými dvojicami vrcholov grafu. Algoritmy: alg. založený na násobení matíc, Floyd-Warshallow alg., Johnsonov alg. pre riedke grafy

Dijkstrov algoritmus

Graf musí mať nezáporné ohodnotenie hrán, aby na ňom Dijkstrov algoritmus korektne fungoval. Algoritmus udržuje množinu S vrcholov, pre ktoré sa už vypočítala dĺžka najkratšej cesty. Algoritmus opakovane vyberá vrchol $u \in V\setminus S$ s najkratšou cestou a relaxuje hrany vychádzajúce z u

DIJKSTRA(G,w,s) 
1  INICIALIZACIA(G,s) 
2  S ← Ø; Q ← V 
3  while Q ≠ Ø do 
4    u ← (u ∈ Q ∧ d[u] = min{d[x] | x ∈ Q} 
5    S ← S ∪ {u} 
6    Q ← Q \ {u} 
7    for kazdy vrchol v taky, ze (u,v) ∈ H do 
8       RELAXACIA(u,v,w) 
9    od 
10 od

RELAXACIA a INICIALIZACIA sú tie isté procedúry ako v prípade Bellman-Fordovho algoritmu. Zložitosť závisí od spôsobu reprezentácie množiny Q, efektivity výberu prvku u s minimálnou hodnotou d[u] a aktualizácie hodnôt d[v] pre vrcholy susediace s u. Pre pole: $O(|V|^2 + |H|) = O(|V|^2)$ , pre Fibonacciho haldu: $O(|V|log|V| + |H|)$

Floyd-Warshallov algoritmus

Daný je orientovaný graf $G=(V,H), V = \{1,2,..,\}$ s ohodnotením hrán $w:\ H \rightarrow R$ bez záporných cyklov. Predpokladajme, že graf je zadaný maticou susednosti rozmerov $n \times n, W = (w_{ij})$ . Nech $p = <v_1,v_2,...,v_l>, l \geq 2$ je cesta v grafe. Vnútorné vrcholy cesty p sú vrcholy $v_2,...,v_{l-1}$ .

Pre ľubovoľnú dvojicu vrcholov $i,j \in V$ uvažujeme všetky cesty z i do j, ktorých vnútorné vrcholy sú množiny $\{1,2,...,k\}$ , nech p je z nich najkratšia. Floydov-Warshallow algoritmus využíva vzťah medzi touto množinou ciest z i do j a množinou ciest z i do j, ktorých vnútorné vrcholy sú z množiny $\{1,2,...,k-1\}$ (dynamické programovanie).

ak k nie je vnútorným vrcholom cesty p, tak najkratšia cesta z i do j s vnútornými vrcholmi z $\{1,2,...,k-1\}$ je zároveň najkratšou cestou z i do j s vnútornými vrcholmi z $\{1,2,...,k\}$
ak k je vnútorným vrcholom cesty p, tak cestu p môžeme rozdeliť na i→k→j, pričom cesta z i do k, aj cesta z k do j sú najkratšími cestami s vnútornými vrcholmi z $\{1,2,...,k-1\}$

Označme $d_{ij}^{k}$ dĺžku najkratšej cesty z i do j s vnútornými vrcholmi z množiny $\{1,2,...,k\}$ . Platí:

$d_{ij}^{k} = w_{ij}$ ak k=0
$d_{ij}^{k} = min(d_{ij}^{k-1},d_{ik}^{k-1} + d_{kj}^{k-1})$ ak k ≥ 1

Algoritmus (D je matica najkratších ciest):
(riadok 5 je $d_{ij}^{k} \leftarrow min(d_{ij}^{k-1},d_{ik}^{k-1} + d_{kj}^{k-1})$ , nefunguje math v code :( )

FLOYD-WARSHALL(W) 
1 D(0) ← W 
2 for k=1 to n do 
3    for i=1 to n do 
4       for j=1 to n do 
5         uvedene vyssie 
6       od 
7    od 
8 od 
9 return D(n)

Časová zložitosť algoritmu je $O(n^3)$ .

Toky v sietiach

Sieť G=(V,H) je orientovaný graf, ktorého každá hrana $(u,v) \in H$ má nezápornú kapacitu (priepustnosť) $c(u,v) \geq 0$ . Ak $(u,v) \not\in H$ , kladieme $c(u,v) = 0$ . Predpokladáme, že v sieti sú vyznačené dva vrcholy - zdroj s a cieľ t a že všetky vrcholy grafu ležia na nejakej ceste z s do t.

Tok v sieti G je funkcia $f: V \times V \rightarrow R$ spĺňajúca:

kapacitné ohraničenia $\forall u,v \in V:\ f(u,v) \leq c(u,v)$
podmienky symetrie $\forall u,v \in V:\ f(u,v) = -f(v,u)$
podmienky kontinuity $\forall u,v \in V\setminus\{s,t\}$ platí $\sum_{u\in V} f(u,v) = 0$ (čo do vrcholu priteká, to z neho aj odteká)

Hodnota $f(u,v)$ sa nazýva tok z u do v. Hodnota toku f je $|f| = \sum_{v\in V} f(s,v)$ (súčet hodnôt vytekajúcich z s). Problém maximálneho toku v sieti je nájsť tok maximálnej hodnoty - používa sa Ford-Fulkersonova metóda.

Ford-Fulkersonova metóda a algoritmus

Ford Fulkersonova metoda 
1 inicializuj tok f na 0 
2 while existuje zlepsujuca cesta p do 
3    zlepsi hodnotu toku na ceste p od 
4 return f

Jedná sa o iteratívny algoritmus. Začína s tokom nulovej hodnoty a postupne zvyšuje hodnotu toku. V každej iterácii hľadá tzv. zlepšujúcu cestu z s do t, po ktorej môže zvýšiť hodnotu toku. Existujú rôzne varianty algoritmu podľa spôsobu hľadania zlepšujúcej cesty, jeden z nich je Ford-Fulkersonov algoritmus. Na jeho pochopenie potrebujeme zaviesť pomocné pojmy:

reziduálna kapacita hrany (u,v) je $c_f(u,v) = c(u,v) - f(u,v)$ (rezerva na danej hrane)
reziduálna kapacita cesty p je $c_f(p) = min\{c_f(u,v)| (u,v)\ lezi\ na\ p \}$

Ford Fulkersonov algoritmus 
1 for kazdu hranu (u, v) ∈ H do 
2    f[u, v] ← 0; f[v, u] ← 0 
3 od 
4 while existuje zlepsujuca cesta p do 
5     c_f (p) ← min{c_f (u, v) | (u, v) lezı na p} 
6     for kazdu hranu (u, v) na p do 
7        f[u, v] ← f[u, v] + c_f (p) 
8        f[v, u] ← −f[u, v] 
9     od 
10 od 
11 return f

Obrázok, ktorý by to mal všetko objasniť (reziduálna sieť je graf s reziduálnymi kapacitami väčšími ako 0):
Ak v sieti G s celočíselnými kapacitami je |f*| hodnota maximálneho toku, cyklus 4-10 sa vykoná nanajvýš |f*| krát. Zložitosť jednej iterácie je rovná zložitosti nájdenia cesty z s do t a je O(|H|), celková zložitosť je O(|f*|.|H|).

Kostra grafu

Je daný súvislý neorientovaný graf $G = (V,H)$ spolu s ohodnotením hrán (váhovou funkciou) $w: H \rightarrow R^{+}$ . Množinu $K \subset H$ nazveme kostrou grafu G, ak je graf $G' = (V,K)$ súvislý a acyklický.
Definujeme váhu kostry K predpisom:
$w(K) = \sum_{h\in K}w(h)$ Minimálna kostra je potom kostra s minimálnou váhou.

Na nájdenie minimálnej kostry sa používajú 2 známe algoritmy: Kruskalov a Primov algoritmus.

Kruskalov algoritmus

Kruskalov algoritmus je príkladom hladového algoritmu. Množina K tvorí les. V každom kroku vyberáme hranu h s minimálnou váhou zo všetkých hrán spájajúcich rôzne komponenty z K.
Implementácia algoritmu využíva štruktúry UNION-FIND. V jednotlivých množinách sú práve vrcholy z rovnakej komponenty vzhľadom ku K.

Kruskal((V,H),w) 
1 K ← ∅ 
2 foreach v ∈ V do 
3     MAKE-SET(v) od //kazdy prvok dame do samostatnej mnoziny 
4 Zotried hrany podla w do neklesajucej postupnosti 
 
5 foreach (u, v) ∈ H v tomto poradı do 
6     if Find-Set(u) ≠ Find-Set(v) //su z roznych komponent 
7     then K ← K ∪ {u, v} //pridaj ich do kostry 
8        UNION(u, v) fi od //zjednot mnoziny 
9 return K

Inicializácia (riadky 1-4) má zložitost Θ(|V|) + (|H| log |H|). Cyklus 5-8 prebehne |H| krát, celkovo sa teda prevedie Θ(|H|) operácıí Find-Set, Union, čo má zložitosť O(|H|α(|V|)). Celková zložitosť Kruskalovho algoritmu je $O(|H|log|H|)$ .

Primov algoritmus

Primov algoritmus je opäť príkladom hladového algoritmu. MnožinaK vždy tvorí jediný strom. Na začiatku zvolíme ľubovoľný vrchol r za koreň a postupne pridávame ďalšie vrcholy, resp. hrany. Tomuto koreňu priradíme ohodnotenie 0, zvyšným ∞. Efektívna implementácia Primovho algoritmu využíva štruktúru Q s operáciami EXTRACT-MIN a DECREASE-KEY.
Primov algoritmus postupne ohodnocuje vrcholy podľa hrán, ktoré do nich vedú,zo štruktúry Q odstráni vrchol, do ktorého vedie minimálna hrana. Uchovávame si pole predchodcov π - rodičov vo vytváranom strome, z ktorého na konci algoritmu vytvoríme kostru.

Celková zložitosť algoritmu je O(|V| log |V| + |H|) ak štruktúru Q implementujeme ako Fibonnaciho haldu.

Zdroje

http://ui.fpf.slu.cz http://zorro.fme.vutbr.cz skriptá z Návrhu algoritmov II
http://www.beranr.webzdarma.cz/algoritmy/trideni.html http://www.sweb.cz/HonzaRug/Delphi/alg.htm http://users.informatik.uni-halle.de

Užitečné odkazy

http://links.math.rpi.edu/applets/appindex/graphtheory.html -užitečný applet, který dokáže simulovat různé algoritmy jako je dijkstra, Bellman-Ford, Kruskal … Grafická ukázka řazení použitím algoritmů – http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html applety mj animuje operace nad haldou Heap, Merge a Quick Sort -- pekne zpracovane

Vypracoval

Petr Kott
petr.kott@post.cz
Dusan Katona, ICQ: <426 081 873>

Zkrátil, sjednotil ze 2 otázek a upravil pro tisk(aby byla rozumně vytisknutelná, tj. do 12ti stránek): Marek Babák (50%, ještě budu upravovat)

¹⁾

převzato z http://cs.wikipedia.org/wiki/Merge_sort

²⁾

Slidy z přednášek FI:IB002 Návrh algoritmů I (jaro 2007), strana 62

³⁾

Slidy z přednášek FI:IB002 Návrh algoritmů I (jaro 2007), strana 67

⁴⁾

Slidy z přednášek FI:IB002 Návrh algoritmů I (jaro 2007), strana 70

⁵⁾

Slidy z přednášek FI:IB002 Návrh algoritmů I (jaro 2007), strana 62-1

home/inf/in16.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru

Obsah