Algoritmy a datové struktury

Note	Pokročilé techniky návrhu algoritmů: dynamické programování, hladové strategie, backtracking. Amortizovaná analýza. IV003

Pokročilé techniky návrhu algoritmů

Dynamické programování

I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.

— Richard Bellman
Eye of the Hurricane: An Autobiography (1984

Intutivně je dynamické programování spojením dvou věcí: "rozbalené" rekurze (taky se tomu říká bottom-up přístup) a memoizace.

Je použitelné na problémy, které lze rozdělit na podproblémy.
Obzvlášť vhodné je pak v těch případech, kde se podproblémy překrývají — dochází k tomu, že se něco počítá víckrát.

Konkrétněji, dynamické programování je vhodnou technikou, pokud:

podproblémů je polynomiální počet,
(optimální) řešení původního problému lze jednoduše spočítat z (optimálních) řešení jeho podproblémů,
podproblémy jde přirozeně seřadit od nejmenšího po největší.

Tip	O tom, že problémů musí být polynomiální počet, přemýšlím intuitivně tak, že se musí dát vyřešit v nějakém vícenásobném `for`-cyklu a uložit do multi-dimenzionálního pole. Pokud mám $l$ zanořených cyklů, vyřeším nejvíc $n^{l}$ podproblémů.

Memoizace

Memoizace v zásadě není nic jiného než tabulka, pole, HashSet, nebo něco podobného, kam si algoritmus ukládá řešení jednotlivých podproblémů.

Tip	V pseudokódu se označuje jako $M$ (asi memory), $A$ (asi array), nebo $C$ (asi cache).

Bottom-up

Rekurze tradičně řeší problém zeshora — začně celým problémem, který si rozdělí na podproblémy, a ty na podpodproblémy, atd. Bottom-up approach jde na to obráceně. Začně těmi nejmenšími podproblémy a postupně se prokousává k rešení celku.

Jediným háček je v tom přijít na to, které podproblémy jsou ty nejmenší a v jakém pořádí je musíme spočítat, aby byly všechny připravené pro výpočet větších podproblémů. Bez tohohle algoritmus nebude fungovat korektně.

Note	Zjednodušeně jde o to přetransformovat rekurzi na cykly. Pěkný vedlejším efektem je, že je jednodušší určit složitost algoritmu.

Kuchařka

Rozděl problém na (překrývající se) podproblémy.
Napiš rekurzivní algoritmus nebo alespoň Bellmanův rekurentní vztah (značený $OPT$ protože dává optimální řešení).
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

Weighted interval scheduling

Z množiny $n$ intervalů (událostí, úkolů, atd.), které se mohou překrývat v čase, a mají určitou váhu $w_{i}$ , vyber takovou množinu intervalů $S$ , pro kterou je $\sum_{i \in S} w_{s}$ maximální.

Řešení: Řešení využívá toho, že čas plyne výhradně dopředu, takže se můžeme na podproblémy dívat chronologicky a nebudou se překrývat.

Nechť $p (j)$ je index takové události $i < j$ , že $i$ a $j$ jsou kompatibilní.

$OPT (j) = {0 max {OPT (j - 1), w_{j} + OPT (p (j))} pokud j = 0 pokud j > 0$

Parenthesization

Mějme hromadu matic, které chceme pronásobit. Víme, že maticové násobení je asociativní, takže můžeme zvolit různé pořadí násobení — různé odzávorkování. Nicméně, není komutativní, takže nesmíme matice prohazovat. Cena násobení matice o velikosti $i \times j$ a $j \times k$ je $i \cdot j \cdot k$ . Jaké pořadí zvolit, aby byl výsledný součin co nejlevnější?

Problém: Máme matice $A_{1}, A_{2}, ..., A_{n}$ , které chceme pronásobit.

Potřebujeme najít index $k$ takový, že $(A_{1} \cdot ... \cdot A_{k}) \cdot (A_{k + 1} \cdot ... \cdot A_{n})$ je nefektivnější. To nám problém rozděluje na dva podproblémy: červený a modrý.
Řešení: $OPT (i, j) = {0 min_{i \leq k < j} {OPT (i, k) + OPT (k + 1, j) + p_{i - 1} \cdot p_{k} \cdot p_{j}} pokud i = j pokud i < j$

Knapsack

Mějme batoh s nosností $W$ a $n$ věcí, které bychom do něj rádi naložili. Každá věc $i$ má hodnotu $v_{i}$ a váhu $w_{i}$ . Jaké věci vybrat, aby byla hodnota naložených věcí co největší, ale batoh je furt unesl?

Řešení: Vychází z myšlenky, že batoh, ve kterém už něco je, je jakoby batoh s nižší nosností.

Procházíme věci postupně přes index $i$ a pro každou řešíme, jestli ji chceme v batohu o nosnosti $w$ :

$OPT (i, w) = ⎩ ⎨ ⎧ 0 OPT (i - 1, w) max {OPT (i - 1, w), v_{i} + OPT (i - 1, w - w_{i})} pokud i = 0 pokud w_{i} > w pokud w_{i} \leq w$

Hladové (greedy) strategie

Přijde Honza na pracovní pohovor a budoucí šéf se ho ptá: "Co je vaše dobrá schopnost?" Honza odpoví: "Umím rychle počítat." "Kolik je 1024 na druhou?" "MILION STO TISÍC," vyhrkne ze sebe Honza. Šéf se chvíli zamyslí a povídá: "Ale to je špatně, výsledek je 1048576!" A Honza na to: "No sice špatně, ale sakra rychle!"

Greedy algoritmy nachází řešení globálního problému tak, že volí lokálně optimální řešení. Tahle taktika nemusí vést ke globálně optimálnímu řešení, ale alespoň ho spočítá rychle.

Ve výpočtu směřuje bottom-up.
Ideálně funguje na problémy, kde optimální řešení podproblému je součástí optimálního řešení celého problému.
Dobře se navrhuje, špatně dokazuje.

Problémy

Cashier’s algorithm (mince)

Jak zaplatit danou částku s co nejmenším počtem mincí různých hodnot?

Řešení: V každé iteraci vol minci s nejvyšší hodnotou, dokud není zaplacena celá částka.

Interval scheduling

Z množiny intervalů, které mají začátek a konec, ale mají stejnou hodnotu, vyber největší podmnožinu intervalů, které se nepřekrývají.

Řešení: Vybereme ty, které končí nejdřív.

Backtracking

Inteligentní brute-force nad prostorem řešení.

Technika hledání řešení problému postupným sestavováním kandidátního řešení. [5]

Částečný kandidát může být zavrhnut, pokud nemůže být dokončen.
Můžeme dokonce zavrhnout kompletní řešení, pokud je chceme najít všechna.
Pokud je kandidát zavrhnut, algoritmus se vrátí o kus zpět (backtrackuje), upraví parametry a zkusí to znovu.

Tabulka 1. Porovnání s dynamickým programováním
Dynamické programování	Backtracking
Hledá řešení překrývajících se podproblémů.	Hledá všechna řešení.
Hledá optimální řešení.	Hledá všechna, libovolná řešení, hrubou silou.
Má blíž k BFS — staví "vrstvy".	Má blíž k DFS — zanoří se do jednoho řešení a pak se vrátí.
Typicky zabírá víc paměti kvůli memoizaci.	Typicky trvá déle, protože hledá všechna řešení.
Mívá cykly.	Mívá rekurzi.

Problémy

Sudoku: Hledá řešení tak, že pro pole vybere možné řešení a zanoří se, pokud funguje tak hurá, pokud ne, tak backtrackuje a zkusí jinou možnou cifru.
Eight queens: Jak rozestavit osm šachových královen na šachovnic tak, aby se vzájemně neohrožovaly?

Amortizovaná analýza

amortize(v)

amortisen — "to alienate lands", "to deaden, destroy"

amortir (Old French) — "deaden, kill, destroy; give up by right"

*admortire (Vulgar Latin) — to extinquish

— Online Etymology Dictionary

Umožňuje přesnější analýzu časové a prostorové složitosti, protože uvažujeme kontext, ve které se analyzovaný algoritmus používá. Určujeme složitost operace v posloupnosti operací, ne samostatně.

Příklad 1. Připomenutí

Tip	Viz bakalářská otázka Korektnost a složitost algoritmu.

Základními pojmy analýzy složitosti jsou:

Časová složitost: Funkce velikosti vstupu $n$ algoritmu. Počítá počet kroků (nějaké výpočetní jednotky) potřebných k vyřešení problému.
Prostorová složitost: Funkce velikosti vstup $n$ algoritmu. Počítá počet polí (nějaké jednotky prostoru), která algoritmus potřebuje navštívit k vyřešení problému.
Asymptotická notace: Umožňuje zanedbat hardwarové rozdíly. Popisuje, že složitost roste alespoň tak, nejvýš tak nebo stejně jako jiná funkce.
Big O: Horní mez, složitost v nejhorším případě. Množina funkcí rostoucích stejně rychle jako $g$ , nebo pomaleji:

$O (g (n)) = {f : (\exists c, n_{0} \in N^{+}) (\forall n \geq n_{0}) (f (n) \leq c \cdot g (n))}$
Omega: Spodní mez, složitost v nejlepším případě. Množina funkcí rostoucích stejně rychle jako $g$ , nebo rychleji.

$Ω (g) = {f : (\exists c, n_{0} \in N^{+}) (\forall n \geq n_{0}) (f (n) \geq c \cdot g (n))}$
Theta: Horní i spodní mez. Množina funkcí rostoucích stejně rychle jako $g$ .

$Θ (g) = O (g) \cap Ω (g)$

Aggregate method (brute force)

Analyzujeme celou sekvenci operací najednou. Nepoužíváme žádné chytristiky ani fígle.

Příklad 2. Zásobník (brute force)

Věta

Pokud začneme s prázdným zásobníkem, pak libovolná posloupnost $n$ operací Push, Pop a Multi-Pop zabere $O (n)$ času.

Důkaz

Každý prvek je Popnut nejvýše jednou pro každý jeho Push.
V posloupnosti je $\leq n$ Pushů.
V posloupnosti je $\leq n$ Popů (včetně těch v Multi-Popu).
Celá posloupnost má tak nejvýše složitost $2 n$ .

Accounting method (banker’s method)

Používá fígl, kdy velké množství levných operací "předplatí" jednu drahou operaci. Využívá metaforu bankovního účtu.

Každé operaci přiřadíme fiktivní kreditovou cenu.
Při realizaci operace zaplatíme skutečnou cenu naspořenými kredity.
Počáteční stav je 0 kreditů.

Pro každou operaci v posloupnosti:

Pokud je skutečná cena nižší než kreditová, tak zaplatíme skutečnou cenu a přebývající kredity uspoříme na účtu.
Pokud je skutečná cena vyšší než kreditová, tak zaplatíme skutečnou cenu a případný nedostatek kreditů doplatíme z úspor na účtu.

Important

Pokud je po celou dobu provádění operací stav účtu nezáporný, pak je skutečná složitost celé posloupnosti operací menší nebo rovna součtu kreditových cen operací.

Warning

Pokud stav účtu kdykoliv během posloupnosti klesne pod nulu, pak jsou kreditové ceny nastaveny špatně!

Tip	Tato metoda se dá upravit tak, že kredity náleží individuálním objektům ve struktuře místo struktury jako celku. Cena operace se pak platí z kreditů objektů, nad kterým operace probíhá.

Příklad 3. Zásobník (kredity)

Operace	Skutečná cena	Kreditová cena
`Push`	1	2
`Pop`	1	0
`Multi-Pop`	$min (k, ∣ S ∣)$	0

Invariant

Počet kreditů na účtu je rovný počtu prvků na zásobníku.

Důkaz

Invariant platí pro prádný zásobník.
S Push operací se na účet připíše právě 1 kredit. (Čímž se předplatí Pop nebo Multi-Pop.)
Pop a Multi-Pop operace spotřebují právě 1 kredit z účtu.
Tedy stav účtu nikdy neklesne pod 0.
Tedy složitost posloupnosti je nejvýše součet kreditových cen, tedy $2 n$ .

Potential method (physicist’s method)

Hraje si s představou toho, že struktura je fyzikální systém s nějakou energetickou hladinou — potenciálem. Výhodou této metody je, že stačí zvolit jednu funkci, která splňuje dané podmínky. Nevýhodou je, že takovou funkci najít je těžké. Člověk zkrátka buď dostane nápad nebo ne.

Potenciálová funkce: Funkce $Φ$ , která přiřadí dané struktuře $S$ hodnotu. Platí, že:

$Φ (S_{0}) Φ (S_{i}) = 0, kde S_{0} je po \overset{c}{ˇ} \overset{a}{ˊ} te \overset{c}{ˇ} n \overset{ı}{ˊ} stav \geq 0 pro ka \overset{z}{ˇ} dou strukturu S_{i}$
Amortizovaná cena: Pokud $c_{i}$ je skutečná cena operace, pak pro amortizovanou cenu $\overset{c_{i}}{^}$ platí:

$\overset{c_{i}}{^} = c_{i} + Φ (S_{i}) - Φ (S_{i - 1})$
Potenciálová věta: Počínaje počátečním stavem $S_{0}$ , celková skutečná cena posloupnosti $n$ operací je nejvýše součet jejich amortizovaných cen.
Důkaz: $i = 1 \sum n \overset{c_{i}}{^} = i = 1 \sum n (c_{i} + Φ (S_{i}) - Φ (S_{i - 1})) = i = 1 \sum n c_{i} + Φ (S_{n}) - Φ (S_{0}) \geq i = 1 \sum n c_{i} ■$

Příklad 4. Zásobník (potenciálová věta)

$Φ (S) = ∣ S ∣$ (počet prvků na zásobníku)

Operace Skutečná cena Amortizovaná cena

Operace	Skutečná cena	Amortizovaná cena
`Push`	1	$\overset{c_{i}}{^} = 1 + (∣ S ∣ + 1) - ∣ S ∣ = 2$
`Pop`	1	$\overset{c_{i}}{^} = 1 + ∣ S ∣ - (∣ S ∣ + 1) = 0$
`Multi-Pop`	$min (k, ∣ S ∣)$	$\overset{c_{i}}{^} = {k + (∣ S ∣ - k) - ∣ S ∣ = 0 ∣ S ∣ + (∣ S ∣ - ∣ S ∣) - ∣ S ∣ = 0 pokud ∣ S ∣ > k pokud ∣ S ∣ \leq k$

Push

$\overset{c_{i}}{^} = 1 + (∣ S ∣ + 1) - ∣ S ∣ = 2$

Pop

$\overset{c_{i}}{^} = 1 + ∣ S ∣ - (∣ S ∣ + 1) = 0$

Multi-Pop

$min (k, ∣ S ∣)$

\overset{c_{i}}{^} = {k + (∣ S ∣ - k) - ∣ S ∣ = 0 ∣ S ∣ + (∣ S ∣ - ∣ S ∣) - ∣ S ∣ = 0 pokud ∣ S ∣ > k pokud ∣ S ∣ \leq k

Věta

Počínaje prázdným zásobníkem, libovolná sekvence operací zabere $O (n)$ času.

Důkaz (případ Push)

Skutečná cena je $c_{i} = 1$ .
Amortizovaná cena je $\overset{c_{i}}{^} = c_{i} + Φ (S_{i}) - Φ (S_{i - 1}) = 1 + (∣ S ∣ + 1) - ∣ S ∣ = 2$ .

Důkaz (případ Pop)

Skutečná cena je $c_{i} = 1$ .
Amortizovaná cena je $\overset{c_{i}}{^} = c_{i} + Φ (S_{i}) - Φ (S_{i - 1}) = 1 - 1 = 0$ .

Důkaz (případ Multi-Pop)

Skutečná cena je $c_{i} = k$ .
Amortizovaná cena je $\overset{c_{i}}{^} = c_{i} + Φ (S_{i}) - Φ (S_{i - 1}) = k - k = 0$ .

Důkaz (závěr)

Amortizovaná cena všech operací je $\overset{c_{i}}{^} \leq 2$ .
Součet amortizovaných cen posloupnosti $n$ operací je pak $\sum_{i = 1}^{n} \overset{c_{i}}{^} \leq 2 n$ .
Z potenciálnové věty plyne, že skutečná cena posloupnosti je $\leq 2 n$ .

⁂

Slavné potenciálové funkce

Fibonnacciho halda: $Φ (H) = 2 \cdot trees (H) - 2 \cdot marks (H)$
Splay trees: Binární vyhledávací stromy, kde poslední přídané prvky jsou přístupné rychleji. (zdroj)

$Φ (T) = x \in T \sum ⌊ lo g_{2} size (x)⌋$
Move-to-front: Transformace dat používaná při kompresi dat. (zdroj)

$Φ (L) = 2 \cdot inversions (L, L^{*})$
Preflow-push (push-relabel): $Φ (f) = v : excess (v) > 0 \sum height (v)$
Red-black trees: $Φ (T) = x \in T \sum w (x) w (x) = ⎩ ⎨ ⎧ 0102 pokud x je \overset{c}{ˇ} erven \overset{y}{ˊ} pokud x je \overset{c}{ˇ} ern \overset{y}{ˊ} a nem \overset{a}{ˊ} \overset{z}{ˇ} \overset{a}{ˊ} dn \overset{e}{ˊ} \overset{c}{ˇ} erven \overset{e}{ˊ} potomky pokud x je \overset{c}{ˇ} ern \overset{y}{ˊ} a m \overset{a}{ˊ} jednoho \overset{c}{ˇ} erven \overset{e}{ˊ} ho potomka pokud x je \overset{c}{ˇ} ern \overset{y}{ˊ} a m \overset{a}{ˊ} dva \overset{c}{ˇ} erven \overset{e}{ˊ} potomky$

Pokročilé techniky návrhu algoritmů

Dynamické programování

Memoizace

Bottom-up

Kuchařka

Problémy

Hladové (greedy) strategie

Problémy

Backtracking

Problémy

Amortizovaná analýza

Aggregate method (brute force)

Accounting method (banker’s method)

Potential method (physicist’s method)

Zdroje