Search
Přednáška 9 v oddíle Přednášky.
Dynamické programování (DP) je algoritmický přístup k problémům se specifickou strukturou. Stojí na principu rozdělení úlohy na podúlohy, jejich řešení a následné spojení. Obecně lze dynamické programování využít pro řešení problémů, které mají 2 vlastnosti:
Tabelace je metoda DP, kdy ukládáme výsledky podproblémů do tabulky (klidně vícedimenzionální). Počítáme standardně rekurzivně, ale před každým zavoláním rekurze se nejprve ujistíme, zda výsledek již není uložen. Před vracením pak uložíme návratovou hodnotu do tabulky.
Pro některé úlohy nad orientovaným acyklickým grafem (Directed Acyclic Graph - DAG) lze využít topologického uspořádání DAGu k vyřešení úlohy za jeden průchod grafem.
Počítáme-li úlohu kterou jsme schopni pro daný uzel vyřešit snadno pokud známe řešení ve všech předcích, stačí úlohu řešit postupně pro uzel za uzlem v topologickém uspořádání.
Topologické uspořádání je seřazení uzlů grafu tak, že pro každou hranu platí že vede z uzlu s nižším indexem do uzlu s indexem vyšším. Při vizualizaci lze ověřit tak, že všechny hrany vedou jedním směrem (zleva doprava, dle konvence).
Topologických uspořádání grafu může být mnoho, až $|V|!$ pro graf s množinou uzlů $V$ a bez hran ($E = \emptyset$). Pro graf níže jsou 3 možné topologické uspořádání napravo.
Topologických uspořádání je získáno iterativním odstraňováním uzlu do kterého nevede žádná hrana. Celý algoritmus lze provést v čase $\mathrm{O}(|V| + |E|)$.
Řešená úloha 1: Popište jak vypočítat hodnotu rekurzivní funkce $f(6, 7)$ pomocí dynamického programování, když je funkce $f$ rekurzivně definována takto:
a) $f(x, y) = \begin{cases} 0 & \mathrm{pokud} \; x = 0 \lor y = 0 \\ f(x-1, y-1)+ f(x-1, y) + f(x, y-1) + 1 & \mathrm{jinak} \end{cases}$
Řešení (a)
f = [[0]*8 for i in range(7)] for x in range(1,7): for y in range(1,8): f[x][y] = f[x-1][y-1] + f[x-1][y] + f[x][y-1] + 1 print(f[6][7])
b) $f(x, y) = \begin{cases} 0 & \mathrm{pokud} \; x = 0 \lor y = 0 \\ \max \{f(x-1, y-1), f(x-1, y)\} + f(x, y-1) + 1 & \mathrm{jinak} \end{cases}$
Řešení (b)
f = [[0]*8 for i in range(7)] for x in range(1,7): for y in range(1,8): f[x][y] = max(f[x-1][y-1], f[x-1][y]) + f[x][y-1] + 1 print(f[6][7])
Řešená úloha 2: Navrhněte způsob jak lze pomocí dynamického programování spočítat kombinační číslo $\binom{n}{k}$.
Řešení
Využijeme tzv. Pascalova trojúhelníku, tedy vztahu $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ (a vztahu $\binom{n}{0} = \binom{n}{n} = 1$).
S jakou asymptotickou složitostí vypočítá navržený algoritmus $\binom{n}{k}$? Napište v závislosti na $n$ a $k$.
Algoritmus poběží v čase $\mathrm{O}(n \cdot k)$
Řešená úloha 3: Seřaďte topologicky uzly následujícího grafu.
Možných řešení je více:
5, 0, 1, 4, 6, 7, 3, 2 5, 0, 1, 4, 6, 7, 2, 3 5, 0, 1, 4, 6, 2, 7, 3
5, 0, 4, 1, 6, 7, 3, 2 5, 0, 4, 1, 6, 7, 2, 3 5, 0, 4, 1, 6, 2, 7, 3
5, 0, 4, 6, 1, 7, 3, 2 5, 0, 4, 6, 1, 7, 2, 3 5, 0, 4, 6, 1, 2, 7, 3
Jak najdmeme takové topologické uspořádání, jehož vektor vypsaných uzlů bude lexikograficky nejmenší?
Pro vybírání dalšího uzlu ke zpracování využijeme min-haldu s indexy všech uzlů bez vstupních hran.
Řešená úloha 4: Popište, jak metodou DP určíte počet všech cest délky 3 v neváženém DAG, bez toho, že byste tyto cesty skutečně konstruovali nebo jednotlivě procházeli.
V každém uzlu si budeme pamatovat, kolik v něm končí cest délky 1, kolik cest délky 2 a kolik cest délky 3.
Pro další uzel v topologickém uspořádání pak budeme počítat jednotlivé údaje takto:
Celkový počet cest délky 3 je pak součet cest délky 3 končících v daném uzlu, kde sčítáme přes všchny uzly.
Úloha 5: Jak vypočtete hodnotu rekurzivní funkce f(5, 8,7) pomocí vyplňování hodnot v poli, když funkce j je rekurzivně definována takto
a) $f(x, y, z) = \begin{cases} 0 & \mathrm{pokud} \; x = 0 \lor y = 0 \lor z = 0 \\ f(x-1, y-1, z-1)+ f(x-1, y, z) + f(x, y-1, z) + f(x, y, z-1) + 1 & \mathrm{jinak} \end{cases}$
b) $f(x, y, z) = \begin{cases} 0 & \mathrm{pokud} \; x = 0 \lor y = 0 \lor z = 0 \\ 3 \cdot f(x-1, y-1, z) - f(x, y-1, z) - f(x-1, y, z-1) + 1 & \mathrm{jinak} \end{cases}$
Úloha 6: Snažíme se určit počet všech binárních vektorů délky N, které mají tu vlastnost, že v nich nikdy nestojí dvě (nebo více) jedničky těsně vedle sebe (vektor 0100100101 je přípustný, vektory 01100, 111 přípustné nejsou). Jak to uděláme pomocí DP?
Hint:
Pro danou délku N označme P(N, 0) počet všech hledaných vektorů délky N, které mají danou vlastnost a které končí číslicí 0. Analogicky definujme P(N, 1) pro vektory končící číslicí 1.
A. Napište rekurentní vztahy pro výpočet P(N, 0) a P(N, 1) pomocí hodnot P(N-1, 0) a P(N-1, 1). B. Pomocí metody DP určete hodnotu P(12, 0) + P(12, 1), využijte vztahy odvozené v A.
💻 Rozšíření: Doplňte funkci numberOfValidStringsDP v následujícím Java kódu. Soubor obsahuje také kód ke cvičení 2
numberOfValidStringsDP
Úloha 7: K dispozici jsou tři druhy nákladních vozů: Kontejnerový vůz, výsypný vůz a cisterna. Vozy mohou být za sebou řazeny ve vlaku libovolně s jedinou výjimkou, dvě cisterny nesmí následovat bezprostředně za sebou, musí být mezi nimi alespoň jeden vůz jiného druhu. Kolik různých vlaků s 10 vozy lze sestavit? Označme symboly P(N, C), resp. P(N, K), resp. P(N, V) po řadě počet vlaků s N vozy, jejichž poslední vůz je cisterna, resp. kontejnerový vůz, resp. výsypný vůz.
A. Napište rekurentní vztah pro výpočet P(N, C) pomocí hodnot P(N-1, K) a P(N-1, V). Dále napište rekurentní vztahy pro výpočet hodnot P(N, K) a P(N, V) pomocí hodnot P(N-1, K) , P(N-1, V) a P(N-1, C). B. Pomocí metody DP určete hodnoty P(10, C), P(10, K), P(10, V), využijte vztahy odvozené v A. C. Napište kód funkce která počítá P(10, C), P(10, K), P(10, V). D. Rozhodnětě, jestli pro výpočet P(N, C) je zapotřebí znát obě hodnoty P(N-1, K) a P(N-1, V).
Bonus: Cisterna smí být zařazena pouze za výsypným vozem, naopak výsypný vůz nesmí být zařazen za cisternou.
Úloha 8: Ackermannova funkce je definována pro dva celočíselné nezáporné parametry n, m, je tedy možné její hodnoty jednoduše zapisovat do tabulky. Popište, jak budete postupně vyplňovat tabulku, abyste se vyhnuli rekurzivnímu volání. Dokážete určit hodnotu A(4,4)?
$A(n, m) = \begin{cases} m+1 & \mathrm{pokud} \; n = 0 \\ A(n-1, 1) & \mathrm{pokud} \; n > 0 \land m = 0 \\ A(n-1, A(n, m-1)) & \mathrm{pokud} \; n > 0 \land m > 0 \end{cases}$
Úloha 9: Všech 16 navzájem různých binárních vektorů délky 4 tvoří uzly orientovaného grafu G. V grafu existuje hrana z uzlu A do uzlu B právě tehdy když A & B = A, kde operaci & chápeme jako běžný bitový součin, např. 0101 & 0110 = 0100. Určete, jestli G je acyklický a pokud ano, najděte jeho nějaké topologické uspořádání.
Úloha 10: Předpokládejme, že v souvislém DAG G je každá hrana ohodnocena reálným číslem. Efektivní algoritmus hledání nejdelší cesty v tomto G je založený na myšlence DP a jeho asymptotická složitost je úměrná počtu hran G. Popište, jak je nutno modifikovat tento algoritmus, aby našel nejdelší cestu v G za okolností specifikovaných níže.
A. Předpokládejte, že každý uzel G je ohodnocen kladným reálným číslem a hrany ohodnoceny nejsou. B. Předpokládejte, že každý uzel G je ohodnocen libovolným reálným číslem (kladným nebo záporným) a hrany ohodnoceny nejsou. C. Předpokládejte, že každý uzel G i každá hrana G jsou ohodnoceny libovolným reálným číslem (kladným nebo záporným).
Úloha 11: Popište, jak metodou DP určíte počet všech cest v DAG, tj. všech cest s každou možnou délkou.
Úloha 12: Každá hrana DAG G je obarvena buď modrou nebo zelenou barvou. Popište, jak metodou DP najdete co nejdelší cestu v G takovou, že se na ní pravidelně střídají barvy hran, to jest, barvy každých dvou bezprostředně navazujících hran na této cestě musí být různé.