====== 10 - Dynamické programování II ====== /* Toto cvičení prochází úpravou, zatím využijte následující zdroje. {{:courses:a4b33alg:cvi11.pdf| pdf}} plus {{:courses:a4b33alg:protosli11.docx| protoslidy}}, {{:courses:a4b33alg:cviceni11.pdf| pdf}} {{:courses:a4b33alg:main.java| DP pro LCS}} */ ==== Připomenutí teorie ==== Přednášky 10 a 11 v oddíle [[courses:b4b33alg:prednasky|Přednášky]]. === Nejdelší rostoucí podposloupnost === V této úloze nás zajímá sekvence (ne nutně sousedících) prvků v poli, taková, že každý prvek nalevo je menší než každý prvek napravo. Uvážíme úlohu jako hledání nejdelší podposloupnosti ke které můžeme připojit poslední prvek pole a tak vytvořit kandidáta na nejdelší posloupnost celkově. Když známe rostoucí podposloupnosti všech délek pro zkrácené pole (pole bez posledního prvku) můžeme z nich vybrat nejdelší posloupnost, která končí menším číslem. Připojením našeho prvku vznikne posloupnost o 1 delší, kterou si zapamatujeme, pokud končí nižším číslem než posloupnost stejné délky, pokud takovou už máme uloženou. Toto využití řešení menšího problému je ta "optimal substructure". Nalezené podposloupnosti budou využity i pro přidávání dalšího prvku, tedy máme "overlapping subproblems". Stačí si zapamatovat tyto výsledky a dočasné podposloupnosti a jsme schopni vyřešit úlohu v $\mathrm{O}(n \log n)$, jelikož procházíme $n$ prvků a vždy hledáme nejdelší posloupnost končící menším číslem, což můžeme dělat půlením intervalu. === Nejvýhodnější závorkování součinu matic === V této úloze máme několik matic rozdílných rozměrů v daném pořadí které chceme pronásobit. Záleží nám na pořadí provedení jednotlivých násobení - na uzávorkování součinu, které povede k minimu operací. Pro $A \in \mathbb{R}^{r \times m}$ a $B \in \mathbb{R}^{m \times c}$ bude složitost násobení $A B$ rovna $r \cdot m \cdot c$. Jedno velké násobení $n$ matic si představíme jako $n-1$ možných násobení 2 matic podle toho jak rozdělíme $n$ matic na 2 části jejichž složitost násobení umíme snadno spočítat. Ty 2 části jsou naše "optimal substructure" a to, že mnoho z onich rozdělení využijeme vícekrát ukazuje na "overlapping subproblems". Složitost najití optimálního uzávorkování bude $\Theta(n^3)$. Odvození viz přednáška, ale odhad lze udělat z toho, že vyplňujeme polovinu tabulky $n \times n$ a každé číslo dosazujeme hledáním maxima z až $n$ výpočtů. === Optimální vyhledávací strom === Toto je úloha kde máme sestrojit BVS, pro který známe pravděpodobnosti dotazů na jednotlivé klíče. Chceme minimalizovat očekávaný počet operací, kdy nalezení klíče $k$ v hloubce $h_k$ vyžaduje $h_k+1$ operací. Pokud je pravděpodobnost dotazu na klíč $k$ rovna $p_k$, celková cena umístění klíče $k$ do hloubky $h_k$ bude $p_k(h_k + 1)$. Minimalizujeme součet přes všech $n$ klíčů. Podobně jako při závorkování, optimální strom o $n$ uzlech lze vidět jako kořen a 2 optimální podstromy v levé a pravé větvi. Toto je naše "optimal substructure". Když budeme hledat optimální strom o $n$ uzlech tak, že budeme zkoušet každý z $n$ uzlů jako kořen, budeme využívat stejné podstromy vícekrát - "overlapping subproblems". Cenu stromu vypočteme vždy jako součet pravděpodobností výskytu všech uzlů + ceny obou podstromů. Složitost bude také $\Theta(n^3)$, výpočet je podobný výpočtu závorkování. === Nejdelší společná podposloupnost === V této úloze máme 2 řetězce $A,B$ délek $m$ a $n$, a hledáme nejdelší podposloupnost (opět ne nutně navazující) která se vyskytuje zároveň v obou řetězcích. Když známe nejdelší společnou podposloupnost pro kratší řetězce, můžeme toho využít pro optimální řešení pro řetězce se znakem navíc. Celé se to provádí tak, že vyplňujeme 2D pole $m \times n$, kde na doplňujeme čísla podle předpisu: $l[i, j] = \begin{cases} 0 & \mathrm{pokud} \; i = 0 \lor j = 0 \\\\ l[i-1, j-1] + 1 & \mathrm{pokud} \; i > 0 \land j > 0 \land A[i] = B[j] \\\\ \max(l[i-1, j], l[i, j-1])& \mathrm{pokud} \; i > 0 \land j > 0 \land A[i] \ne B[j] \\\\ \end{cases}$ Toto je pak problém s tabelací, podobný těm, co jsme řešili na minulých cvičeních. Podobný proces je používaný pro výpočet [[https://en.wikipedia.org/wiki/Hamming_distance | Hammingovy]], či [[https://en.wikipedia.org/wiki/Levenshtein_distance | Levenshteinovy]] vzdálenosti dvou řetězců. Složitost bude $\Theta(m \cdot n)$, protože vyplňujeme tabulku o dimenzích $m \times n$. === Úloha batohu (Knapsack) === Problém batohy (knapsack problem) je klasický NP-těžký problém. Máme batoh s kapacitou $C$ a $n$ předmětů, kde každý předmět $i$ má váhu/velikost $c_i$ a cenu/hodnotu (value) $v_i$. Chceme maximalizovat hodnotu předmětů tak, aby předměty které zvolíme nepřeplnily batoh, tedy součet jejich vah byl menší než kapacita $C$. Uvažují se 2 varianty, 0/1 knapsack znamená, že každý předmět máme jen jeden a rozhodujeme zda ho vzít, či nevzít (0/1). Neomezená varianta pak znamená, že každý předmět můžeme vzít kolikrát chceme. Obě varianty řešíme tak, že uvažujeme optimální řešení pro batoh s menší kapacitou a do nich zkoušíme přidat další předměty. {{ :courses:b4b33alg:cviceni:10_knapsack_illustr.png?400|}} Pro neomezený knapsack si toto lze představit převodem na hledání nejdelší cesty v DAGu s $C$ uzly a hranami s cenou předmětů mezi každými uzly které reprezentují odpovídající změnu ve zbývající kapacitě. Na obrázku vpravo je sestrojen DAG pro $C = 10, n = 4, v = (9, 14, 16, 30), c = (2, 3, 4, 6)$. Pro 0/1 knapsack pak vyplňujeme tabulku kde řádky znamenají přidání konkrétního předmětu a sloupce jsou změny v kapacitě. Do tabulky pak zapisujeme maximální hodnotu kterou můžeme dostat s batohem dané kapacity a s danými předměty. $h(i, j) = \begin{cases} 0 & \mathrm{pokud} \; i = 0 \lor j = 0 \\\\ \max(h(i-1, j), h(i-1, j-c_i) + v_i) & \mathrm{jinak} \end{cases}$ Knapsack je tedy převoditelný na problém nejdelší cesty v DAGu či tabelaci, což jsme již řešili na minulých cvičeních. Řešení neomezeného i 0/1 knapsacku má složitost $\Theta(C \cdot n)$, protože vyplňujeme tabulku o dimenzích $C \times n$, či procházíme DAG s $\Theta(C \cdot n)$ hranami. ==== Řešené úlohy ==== === Rostoucí podposloupnost === **Řešená úloha 1:** Najděte nejdelší rostoucí podposloupnost dané posloupnosti. Použijte metodu dynamického programování, napište tabulku průběžných délek částečných výsledků a tabulku předchůdců | 5 | 8 | 11 | 13 | 9 | 4 | 1 | 2 | 0 | 3 | 7 | 10 | 12 | 6 | ++++ Řešení | | index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | | hodnota | 5 | 8 | 11 | 13 | 9 | 4 | 1 | 2 | 0 | 3 | 7 | 10 | 12 | 6 | | předek | - | 0 | 1 | 2 | 1 | - | - | 6 | - | 7 | 9 | 10 | 11 | 9 | | délky podposloupnosti | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ... | | index posledního prvku | 8 | 7 | 9 | 13 | 11 | 12 | - | | | poslední prvek | 0 | 2 | 3 | 6 | 10 | 12 | - | | Délka výsledné sekvence je 6 a sekvence (dle vektoru předků) je 1, 2, 3, 7, 10, 12. ++++ ----- === Závorkování Matic === **Řešená úloha 2:** Rozměry matic $A, B, C, D, E$ jsou po řadě: $2\times 5$, $5 \times 3$, $3 \times 6$, $6 \times 2$, $2 \times 4$. Určete pomocí dynamického programování, jak uzávorkovat součin $A \times B \times C \times D \times E$, aby počet operací násobení dvou čísel během výpočtu celého součinu byl co nejmenší. Kolik to bude operací? ++++ Řešení | Postupujeme vyplňováním počtu operací do tabulky jako je níže, dolní index jsou rozměry matice která je výsledkem násobení. Vyplňujeme od diagonály směrem doprava nahoru. | | A | B | C | D | E | | A | $0_{2\times5}$ | $30_{2\times3}$ | $66 _{2\times 6}$ | $78 _{2\times 2}$ | $94 _{2\times 4}$ | | B | - | $0_{5\times3}$ | $90 _{5\times 6}$ | $66 _{5\times 2}$ | $106 _{5\times 4}$ | | C | - | - | $0_{3\times6}$ | $36 _{3\times 2}$ | $60 _{3\times 4}$ | | D | - | - | - | $0_{6\times2}$ | $48 _{6\times 4}$ | | E | - | - | - | - | $0_{2\times4}$ | Výsledek lze rekonstruovat, když si pamatujeme informaci o tom které pozice jsme využili pro výpočet minima v každé buňce: | | 1 | 2 | 3 | 4 | 5 | | | A | B | C | D | E | | A | 0 | 1 | 2 | 2 | 4 | | B | - | 0 | 2 | 2 | 4 | | C | - | - | 0 | 3 | 4 | | D | - | - | - | 0 | 4 | | E | - | - | - | - | 0 | Každý uložený index lze interpretovat jako index poslední matice která bude uzávorkovaná v levé závorce, zbytek bude napravo. $((A \times B) \times (C \times D) \times E)$ ++++ ----- === Optimální vyhledávací strom === **Řešená úloha 3:** Určete, jak bude vypadat optimální BVS, když jej vybudujeme pro 7 klíčů s frekvencemi: * **A**: 0.10 * **B**: 0.10 * **C**: 0.25 * **D**: 0.35 * **E**: 0.10 * **F**: 0.05 * **G**: 0.05 ++++ Řešení | Vyplňujeme od diagonály směrem doprava nahoru. Pro každou buňku projdeme páry existujících hodnot od buňky v řádku zleva a ve sloupci shora, a najdeme minimální hodnotu vypočtenou dle předpisu výpočtu výše. | | - | A | B | C | D | E | F | G | | A | 0 | 0.10 | 0.30 | 0.75 | 1.45 | 1.75 | 1.90 | 2.10 | | B | - | 0 | 0.10 | 0.45 | 1.15 | 1.35 | 1.50 | 1.70 | | C | - | - | 0 | 0.25 | 0.85 | 1.05 | 1.20 | 1.40 | | D | - | - | - | 0 | 0.35 | 0.55 | 0.70 | 0.90 | | E | - | - | - | - | 0 | 0.10 | 0.20 | 0.35 | | F | - | - | - | - | - | 0 | 0.05 | 0.15 | | G | - | - | - | - | - | - | 0 | 0.05 | | - | - | - | - | - | - | - | - | 0 | Diagonála obsahuje nuly, které reprezentují prázdné stromy. Strom lze rekonstruovat, pokud si zapamatujeme např. který index v řádku jsme využili pro výpočet minimální hodnoty v buňce. To nám zároveň přesně určí i pozici ve sloupci. Když pak konstruujeme (pod)strom, kořen bude vždy klíč na pozici $i+1$ kde $i$ je index zapsaný v buňce. {{ :courses:b4b33alg:cviceni:10_03_tree.svg|600}} | i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | | - | A | B | C | D | E | F | G | | A | 0 | 1 | 1 | 3 | 3 | 3 | 4 | 4 | | B | - | 0 | 2 | 3 | 4 | 4 | 4 | 4 | | C | - | - | 0 | 3 | 4 | 4 | 4 | 4 | | D | - | - | - | 0 | 4 | 4 | 4 | 4 | | E | - | - | - | - | 0 | 5 | 5 | 6 | | F | - | - | - | - | - | 0 | 6 | 7 | | G | - | - | - | - | - | - | 0 | 7 | | - | - | - | - | - | - | - | - | 0 | ++++ ----- === Nejdelší společná podposloupnost === **Řešená úloha 4:** Najděte nejdelší společnou podposloupnost dvojice řetězců: * 11101001000 * 00010010111 ++++ Řešení | Doplněním tabulky dle předpisu výše: | | **-** | **1** | **1** | **1** | **0** | **1** | **0** | **0** | **1** | **0** | **0** | **0** | | **-** | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | | **0** | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | **0** | 0 | 0 | 0 | 0 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | | **0** | 0 | 0 | 0 | 0 | 1 | 1 | 2 | 3 | 3 | 3 | 3 | 3 | | **1** | 0 | 1 | 1 | 1 | 1 | 2 | 2 | 3 | 4 | 4 | 4 | 4 | | **0** | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 5 | 5 | 5 | | **0** | 0 | 1 | 1 | 1 | 2 | 2 | 3 | 4 | 4 | 5 | 6 | 6 | | **1** | 0 | 1 | 2 | 2 | 2 | 3 | 3 | 4 | 5 | 5 | 6 | 6 | | **0** | 0 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 6 | 6 | 7 | | **1** | 0 | 1 | 2 | 3 | 3 | 4 | 4 | 4 | 5 | 6 | 6 | 7 | | **1** | 0 | 1 | 2 | 3 | 3 | 4 | 4 | 4 | 5 | 6 | 6 | 7 | | **1** | 0 | 1 | 2 | 3 | 3 | 4 | 4 | 4 | 5 | 6 | 6 | 7 | Jde o podposloupnost 0001000, což lze vyčíst zpětně z diagonálních přechodů v tabulce výše. (Viz modrá "trasa") ++++ ----- === Úloha batohu (Knapsack) === **Řešená úloha 5:** Řešte //neomezenou// variantu úlohy batohu pro kapacitu 10 a tři předměty, jejichž váhy jsou postupně 1, 3, 6 a ceny jsou ve stejném pořadí předmětů 11, 33, 65. Jaká bude maximální cena předmětů v batohu? ++++ Převodem na DAG | Nalezením nejdelší (dle ohodnocení hran) cesty v tomto DAGu. {{ :courses:b4b33alg:cviceni:10_5_knapsack_dag.png?600 |}} ++++ ++++ Tabulkou | Pro každou buňku se zkusím pro každý předmět podívat na hodnotu na indexu nižším o váhu předmětu. K té hodnotě přičtu cenu předmětu a z těchto čísel vyberu maximum a vložím do buňky. | Zaplněná kapacita | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | Nejlepší cena | 0 | 11 | 22 | 33 | 44 | 55 | 66 | 77 | 88 | 99 | 110 | | Index právě přidaného předmětu | 0 | 1 | 1 | 2 | 1 | 1 | 2 | 1 | 1 | 2 | 1 | Indexujeme předměty od 1. ++++ Jaké bude řešení pro 0/1 knapsack pro stejné předměty a kapacitu 7? ++++ Řešení | Za každou řádku přidávám jeden předmět. Přičítám k předchozí řádce, s posunem dle váhy předmětu. | Zaplněná kapacita | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | | Žádný předmět | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | Předmět 1 | 0 | 11 | 11 | 11 | 11 | 11 | 11 | 11 | | Předměty 1-2 | 0 | 11 | 11 | 33 | 44 | 44 | 44 | 44 | | Předměty 1-3 | 0 | 11 | 11 | 33 | 44 | 44 | 65 | 76 | Obsah batohu lze rekonstruovat z tabulky takto: - začneme vpravo dole, - posuneme se doleva dokud bychom nesnížili cenu batohu (hodnotu v buňce) - toto je "volná" kapacita - pokud je v buňce o 1 výš stejné číslo: * předmět z řádky nepřidáme a posuneme se o řádek výš do stejného sloupce * pokud ne, předmět přidáme a posuneme se o řádek výš, s posunem dle váhy přidaného předmětu - opakujeme proces od bodu 2 ++++ ----- ==== Další úlohy ==== === Nejdelší rostoucí podposloupnost === 💻**Úloha 6:** Naimplementujte řešení hledání nejdelší rostoucí podposloupnosti. Template kód {{:courses:a4b33alg:main.java | zde}}. ---- **Úloha 7:** Najděte nejdelší rostoucí podposloupnost dané posloupnosti. Použijte metodu dynamického programování, napište tabulku průběžných délek částečných výsledků a tabulku předchůdců. | 6 | 7 | 5 | 15 | 10 | 9 | 11 | 18 | 19 | 8 | 12 | 1 | 3 | 4 | 13 | 14 | 0 | 17 | 2 | 16 | ---- **Úloha 8:** Určete, jak lze využít nebo přizpůsobit metodu hledání nejdelší rostoucí podposloupnosti pro hledání: \\ a) nejdelší klesající podposloupnosti, \\ b) nejdelší neklesající podposloupnosti, \\ c) nejdelší konstantní podposloupnosti, \\ d) nejdelší alternující posloupnosti. (V alternující posloupnosti $a_1, a_2, \ldots a_n$ platí $(a_k - a_{k-1}) \cdot (a_{k+1} - a_k) < 0$, pro $k = 2, 3, \ldots n-1$) ---- === Závorkování matic === **Úloha 9:** Kolika různými způsoby lze uzávorkovat součin matic? (Různé způsoby závorkování odpovídají různému průběhu výpočtu a obecně různým mezivýsledkům. Závorkování $(X)$ a $((X))$ pokládáme za totožné.) * $A \times B \times C \times D$ * $A \times B \times C \times D \times E$ Co v obecném případě $n$ matic? Zkuste formulujte algoritmus DP který to spočítá pro dané $n$. ++++ Výsledek | Mělo by to být $\binom{2n}{n+1} = \frac{n}{n+1}\binom{2n}{n}$ ++++ ---- **Úloha 10:** Určete, pro které hodnoty $n$ je výhodnější vypočítat součin $(A \times B) \times C$ než vypočítat součin $A \times (B \times C)$. * $A \in R^{n \times 2} , B \in R^{2 \times 3} , C \in R^{3 \times 4}$ * $A \in R^{5 \times n} , B \in R^{n \times 4} , C \in R^{4 \times n}$ * $A \in R^{n \times n} , B \in R^{n \times 100} , C \in R^{100 \times n}$ ---- **Úloha 11:** Rozměry matic $A, B, C, D, E$ jsou stejné jako v úloze 2 (popořadě $2\times 5$, $5 \times 3$, $3 \times 6$, $6 \times 2$, $2 \times 4$). Z důvodů např. testování HW/SW si přejeme součin uzávorkovat tak, aby počet operací násobení dvou čísel byl co **největší**. Rozhodněte, zda lze metodu hledání co nejvýhodnějšího uzávorkování přizpůsobit pro řešení této modifikované úlohy. Jaký bude algoritmus řešení? ---- === Optimální vyhledávací strom === **Úloha 12:** Pravděpodobnost dotazu na jednotlivé klíče v obou daných BVS je tato: A: 0.10 B: 0.20 C: 0.25 D: 0.05 E: 0.10 F: 0.25 G: 0.05 Vypočtěte, který strom je výhodnější pro operaci FIND. ---- **Úloha 13:** Určete, jak bude vypadat optimální BVS, když jej vybudujeme pro 7 klíčů s frekvencemi: E: 0.04 F: 0.05 G: 0.22 H: 0.04 I: 0.06 J: 0.05 K: 0.15 ---- === Nejdelší společná podposloupnost === **Úloha 14:** Najděte nejdelší společnou podposloupnost dvojice řetězců * 1100110011001100 * 1010101010101010 ---- **Úloha 15:** Najděte nejdelší společnou podposloupnost dvojice řetězců * 110100100010000100001000001 * 001011011101111011110111110 = doplněk ---- === Úloha batohu (Knapsack) === **Úloha 16:** Řešte 0/1 variantu úlohy batohu pro kapacitu 130 a pět předmětů, jejichž váhy jsou postupně 20, 30, 40, 50, 60 a ceny jsou ve stejném pořadí předmětů 11, 33, 45, 58, 65. Jaká bude maximální cena předmětů v batohu? Uvažte, jak se vyhnout tabulce se cca 130 sloupci a upravte postup řešení tak, aby stačilo řádově méně sloupců. ---- === Ostatní úlohy === **Úloha 17:** V dané matici začneme kdekoli v prvním sloupci a dále vždy postupujeme jen ve směru SV, V, JV až kamkoli do posledního sloupce. Cena cesty je součet hodnot navštívených polí. Jaká může být nejmenší? | 29 | 10 | 11 | 23 | 22 | 23 | | 27 | 25 | 29 | 12 | 29 | 24 | | 18 | 21 | 11 | 27 | 14 | 24 | | 30 | 17 | 26 | 29 | 23 | 22 | | 12 | 25 | 23 | 13 | 28 | 16 | | 20 | 24 | 10 | 14 | 30 | 15 | Co když cena za cestu bude součet absolutních hodnot rozdílů cen sousedních navštívených polí? ---- **Úloha 18:** Každá zásilka ve skladu má určenou váhu a je nutno všechy zásilky naložit na dvě přistavené dodávky tak, aby se váhy nákladů na obou dodávkách lišily co nejméně. Zdůvodněte, zda lze či nelze metodu DP pro řešení úlohy batohu využít i v této situaci. ---- **Úloha 19:** Kryštof staví malé sportovní lodě. Vyrábí jich několik typů a vždy se věnuje stavbě jen jedné lodě, dokud není hotová. Pro každý typ lodě zná počet dní potřebný ke stavbě lodě a zná svůj zisk z jejího prodeje. Ví, kolik dní bude letos v sezóně věnovat své práci. Navrhněte metodu dynamického programování, která bude maximalizovat Kryštofův výdělek za letošní sezónu. ----