10 - Dynamické programování II

Přednášky 10 a 11 v oddíle Přednášky.

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.

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ů.

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í.

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 Hammingovy, či Levenshteinovy vzdálenosti dvou řetězců.

Složitost bude $\Theta(m \cdot n)$, protože vyplňujeme tabulku o dimenzích $m \times n$.

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.

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á ú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ů

Řešení

Ř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í

Ř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í

Řešená úloha 4: Najděte nejdelší společnou podposloupnost dvojice řetězců:

• 11101001000
• 00010010111

Řešení

Ř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

Tabulkou

Jaké bude řešení pro 0/1 knapsack pro stejné předměty a kapacitu 7?

Řešení

💻Úloha 6: Naimplementujte řešení hledání nejdelší rostoucí podposloupnosti. Template kód 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ů.

Ú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$)

Ú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

Ú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í?

Ú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

Ú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 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ů.

Ú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ší?

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.