Algoritmy a datové struktury II

Obsah

Složitost
Fibonacciho halda
Union-Find
Divide and Conquer
Dynamické programování
Hladové (greedy) algoritmy
Toky
- Ford-Fulkersonova metoda (augmenting path method)
- Goldbergova metoda (push-relabel method)

Slidy

Složitost

Complexity of Problems and Algorithms

Complexity of Problems
Complexity of Recursive Algorithms
Complexity of Iterative Algorithms

Amortized Complexity

Introduction
Aggregate Method
Cashier Method
Method of Potential Function
Dynamic Tables

Složitost problému

Je zdola ohraničená dokazovaním a zhora ohraničená složitostí konkrétního algoritmu, který problém řeší.

Amortizovaná složitost

Nejhorší složitost posloupnosti operací na dané datové struktuře.

Aggregační metoda

Hrubou silou sečti složitosti jednotlivých operací v posloupnosti.

Kreditová (accounting / banker’s) metoda

$c_{i}$ je opravdová složitost $i$ -té operace.
$\overset{c_{i}}{^}$ je počet "kreditů", které $i$ -tá operace stojí.
Pokud $\overset{c_{i}}{^} > c_{i}$ , pak ukládáme kredity "do zásoby".
Pokud $\overset{c_{i}}{^} < c_{i}$ , musíme doplatit rozdíl kredity, které jsme si dali do zásoby dříve.
Před první operací je v zásobě 0 kreditů: $D_{0} = 0$ .
Kreditový invariant: V kreditové zásobě $D_{i}$ musí být vždy nezáporný počet kreditů: $\sum_{i = 1} \overset{c_{i}}{^} - \sum_{i = 1} c_{i} \geq 0$ .
Amortizovaná složitost libovolné posloupnosti operací je nejvýše součet kreditové hodnoty každé z operací.

Potenciálová metoda

Vymysli potenciálovou funkci $Φ (D_{i})$ , která každé datové struktuře, jenž může vzniknout některou z operací, přiřadí reálné číslo.
Musí platit $Φ (D_{0}) = 0$ a $Φ (D_{i}) \geq 0$ .
$c_{i}$ je opravdová složitost $i$ -té operace.
$\overset{c_{i}}{^} = c_{i} + Φ (D_{i}) - Φ (D_{i - 1})$ je amortizovaná složitost $i$ -té operace.
Složitost libovolné posloupnosti operací je nejvýše součet amortizovaných složitostí jednotlivých operací.

Fibonacciho halda

Fibonacci Heap

Introduction
Insert and Extract Min
Decrease Key
Rank
Meld and Delete

Halda s vícero stromy. Kořeny stromů jsou uloženy jako cyklický spojovaný seznam.

Každá posloupnost $m$ operací Insert, Extract-Min a Decrease-Key, která zahrnuje $n$ Insertů, má složitost $O (m + n lo g n)$ .

— Fredman-Tarjan

Původně vznikla, aby vylepšila časovou složitost Dijkstrova algoritgmu z $O (m lo g n)$ na $O (m + n lo g n)$ .

Union-Find

Union Find

Union
Find
Analysis

Struktura pro vzájemně disjunktní množiny. Podporuje 3 operace:

Make-Set(x) — vytvoř novou množinu obsahující jen x.
Find(x) — vrať kanonický element z množiny obsahující x.
Union(x, y) — nahraď množiny obsahující x a y jejich sjednocením.

Divide and Conquer

Divide-and-Conquer

MinMax
Peaks
Closest Pairs

Rozděl problém na nezávislé podproblémy, vyřeš každý podproblém a zkombinuj jejich řešení.

Dynamické programování

Dynamic Programming

Interval Scheduling
Parenthesization
Knapsack
CYK
Sequence Alignment
Bellman-Ford
Conclusion

Rozděl problém na (překrývající se) podproblémy.
Napiš rekurzivní algoritmus.
Urči správné pořadí počítání podproblémů tak, aby se každý počítal právě jednou (bottom-up přístup).
Pokud je to nutné, sestav z optimální hodnoty její realizaci (třeba cestu nebo něco).
Sepiš pseudokód.
Dokaž korektnost rekurentního vztahu, bottom-up pořadí a rekonstrukce (zejména terminace).
Okomentuj složitost.

Problémy

Interval Scheduling (plánování přednášek)
Parenthesization (uzávorkování)
Knapsack (batoh)
Cocke-Younger-Kasami (CYK) (analýza bezkontextových jazyků)
Sequence alignment (rozdíl dvou řetězců)
Bellman-Forde-Moore (nejkratší cesta v orientovaném grafu)

Hladové (greedy) algoritmy

Greedy Algorithms

Coins
Interval Scheduling
Interval Partitioning
Lateness
Spanning trees
Dijkstra

Inkrementálně řeší problém aplikací nějakého lokálního kritéria.

Problémy

Coins
Interval Scheduling
Interval Partitioning
Lateness
Spanning trees
Dijkstra

Toky

Max Flow

Ford-Fulkerson
Capacity Scaling
Shortest Augmenting Path
Push Relabel
Applications

Flow network

Pětice $G = (V, E, s, t, c)$ , kde

$(V, E)$ je orientovaný graf,
$s \in V$ je source (zdroj),
$t \in V$ je sink (odtok),
$c (e) : E \to X$ , kde $X$ jsou obvykle $N_{0}$ nebo $R_{0}^{+}$ , je kapacita hrany $e$ .

$s t$ -řezy

Je rozklad vrcholů na $(A, B)$ takový, že $s \in A$ a $t \in B$ .

Kapacita $s t$ -řezu

Součet kapacit hran na rozhraní $A$ a $B$ :

cap (A, B) = e ven z A \sum c (e)

$s t$ -toky

Funkce $f$ taková, že:

platí kapacitní podmínka: $(\forall e \in E) (0 \leq f (e) \leq c (e))$ ,
platí zachování toku: $(\forall v \in V - {s, t}) (\sum_{e do v} f (e) = \sum_{e ven z v} f (e))$ .

Hodnota toku

val (f) = e ven z s \sum f (e) - e do s \sum f (e)

Residual network

Síť, která vzniká, když je už část kapacity hrany využívána tokem $f$ . Umožnuje algoritmům změnit přechozí rozhodnutí a získat využitou kapacitu zpět.

Je to pětice $G_{f} = (V, E_{f}, s, t, c_{f})$ , kde

$E_{f} = {e \in E : f (e) < c (e)} \cup {e^{reverse} : f (e) > 0}$ ,
pokud $e = (u, v) \in E$ , $e^{reverse} = (v, u)$ ,
$c_{f} = {c (e) - f (e) f (e) e \in E e^{reverse} \in E$

Augmenting path $P$

Jednoduchá $s ⇝ t$ cesta v residuální síti $G_{f}$ .

Note	T.j. cesta která může jít i proti směru toku $f$ .

Bottleneck kapacita je nejmenší kapacita hran v augmenting path $P$ .

To krásné na augmenting cestách je, že pro flow $f$ a augmenting path $P$ v grafu $G_{f}$ , existuje tok $f^{'}$ takový, že $val (f^{'}) = val (f) + bottleneck (G_{f}, P)$ . Nový tok $f^{'}$ lze získat takto:

Augment(f, c, P)
{
    delta = bottleneck(P)
    foreach(e in P)
    {
        if(e in E)
        {
            f[e] = f[e] + delta
        }
        else
        {
            f[reverse(e)] = f[reverse(e)] - delta
        }
    }
    return f
}

Max-flow min-cut theorem

Hodnota maximálního toku je rovna kapacitě minimálního řezu.

Ford-Fulkerson vs Goldberg

Ford-Fulkerson	Goldberg
global character	local character
update flow along an augmenting path	update flow on edges
flow conservation	preflow

Ford-Fulkerson

Goldberg

global character

local character

update flow along an augmenting path

update flow on edges

flow conservation

preflow

Ford-Fulkersonova metoda (augmenting path method)

$f (e) = 0$ pro každou $e \in E$ .
Najdi $s ⇝ t$ cestu $P$ v reziduální síti $G_{f}$ .
Augmentuj tok podél $P$ .
Opakuj dokud se nezasekneš.

Ford–Fulkerson(G)
{
    foreach (e in E)
    {
        f(e) = 0
    }

    G_f = reziduální síť vzniklá z G vzhledem k toku f
    while (existuje s ~> t cesta v G_f)
    {
        f = Augment(f, c, P)
        Updatuj G_f
    }
    return f
}

Goldbergova metoda (push-relabel method)

Pre-flow

Funkce $f$ taková, že

platí kapacitní podmínka: $(\forall e \in E) (0 \leq f (e) \leq c (e))$ ,
platí relexováné zachování toku: $(\forall v \in V - {s, t}) (\sum_{e do v} f (e) \geq \sum_{e ven z v} f (e))$ .

Overflowing vertex

Takový vertex $v \in V - {s, t}$ , do kterého více přitéká než odtéká.

e do v \sum f (e) > e ven z v \sum f (e)

Excess flow

To, co je v overflowing vertexu navíc.

e_{f} (v) = e do v \sum f (e) - e ven z v \sum f (e)

Height function

Funkce $h : V \to N_{0}$ . Řekneme, že $h$ je kompatibilní s preflow $f$ , právě když

source: $h (s) = ∣ V ∣ = n$ ,
sink: $h (t) = 0$ ,
height difference: $(\forall (v, w) \in E_{G_{f}}) (h (v) \leq h (w) + 1)$ .

Note
Pokud mezi dvěma vrcholy $(v, w)$ v reziduální síti vede hrana, pak je $v$ nejvýše o jednu úroveň výš než $w$ .

Tip

Lemma: Pokud je $f$ preflow a $h$ je height function kompatibilní s $f$ , pak neexistuje $s ⇝ t$ cesta v $G_{f}$ .
Důkaz: Nejdelší jednoduchá $s ⇝ t$ cesta má $n$ vrcholů a $n - 1$ hran. Z definice $h$ plyne (kombinací nerovností) $h (s) \leq h (t) + n - 1$ . Protože $h (t)$ je z definice 0, pak $h (s) < n$ , což je spor, protože $h (s) = n$ .

Tip	Lemma Pokud je $f$ flow (tedy zejména preflow) a $h$ je height function kompatibilní s $f$ , pak je $f$ maximální tok.

Push operace

Pro (reziduálně-grafovou) hranu $(v, w)$ se pokusí přesunout excess flow z $v$ do $w$ , aniž by porušil (reziduální) kapacitu $(v, w)$ .

// Assumptions: e_f[v] > 0, c_f( (v, w) > 0) > 0, h[v] > h[w]
Push(f, h, v, w)
{
    delta_f = min(e_f[v], c_f(v, w))
    if( (v, w) in E)
        f[(v, w)] += delta_f
    else
        f[(w, v)] -= delta_f
    e_f[v] -= delta_f
    e_f[w] += delta_f
}

Relabel operace

Zvýší výšku $h (v)$ natolik, aby neporušil kompatibilitu $h$ s $f$ .

// Assumptions:
//   - v is overflowing: e_f[v] > 0
//   - all residual neighbors of v the same height or higher: forall (v, w) in E_f: h[v] <= h[w]
Relabel(f, h, v)
{
    h[v] = 1 + min(h[w] | (v, w) in E_f)
}

Generic Push-Relabel

Generic-Push-Relabel(V, E, s, t, c)
{
    // initialize preflow — default values
    for(v in V)
    {
        h[v] = 0    // height function
        e_f[v] = 0  // excess flow
    }
    n = |V|
    h[s] = n

    for(e in E)
    {
        f[e] = 0    // (pre)flow
    }

    // initialize preflow — saturate connections from s
    for( (s, v) in E)
    {
        f[(s, v)] = c(s, v) // preflow maxes out all capacity
        e_f[v] = c(s, v)    // presume all of it excess
        e_f[s] -= c(s, v)   // yes, it will be negative
    }

    // the juicy part
    while(any vertex is overflowing)
    {
        v = an overflowing vertex (has e_f[v] > 0)
        if(v has a neighbor w in G_f such that h(v) > h(w))
        {
            Push(f, h, v, w)
        }
        else
        {
            Relabel(f, h, v)
        }
    }
    return f
}

Amortizovaná složitost Push-Relabel

$O (V^{2} E)$ operací Push nebo Relabel.