Dynamické programování

Princip dynamického programování

• Začneme s rekurzivním pomalým algoritmem
• Analyzujeme ho pro opakované výpočty
• Pořídíme si tabulku a budeme si v ní pamatovat, které podproblémy jsme již vyřešili. Tedy počítáme si cache.
• Odstraníme rekurzi a zvolíme vhodné pořadí podproblémů. Cache a odstranění rekurze zrychlí běh algoritmu.

---

Nejdelší rostoucí podposloupnost

Dostaneme $x_1,\dots ,x_n$ posloupnost celých čísel a chceme vymazat co nejméně prvků, aby nám zbyla jen a pouze rostoucí podposloupnost. Hladový algoritmus můžeme postavit na algoritmu NRP, který má ale složitost $2^n$.

$$\begin{array}{rl}& \text{NRP(i)}\\ & \text{Vstup: Posloupnost }{x}_i,\dots ,x_n\\ & \text{Vyˊstup: Deˊlka nejdelsˇıˊ podposloupnosti }d\\ & \text{1. }d\leftarrow 1\\ & \text{2. Pro }j=i+1,\dots ,n:\\ & \text{3. }\text{Je-li }{x}_j>x_i:\\ & \text{4. }d\leftarrow \max (d,1+\text{NRP}(j))\end{array}$$

Můžeme si ale pomocí návodu udělat lepší algoritmus, budeme počítat tabulku a postupně vyplňovat od největšího indexu k nejmenšímu. Chceme $T[i]$, což bude délka té nejdelší podposloupnosti začínající $x_i$.

$$\begin{array}{rl}& \text{NRP2}\\ & \text{Vstup: Posloupnost }{x}_1,\dots ,x_n\\ & \text{Vyˊstup: Deˊlka nejdelsˇıˊ podposloupnosti }T[0]\\ & \text{1. }{x}_0\leftarrow -\infty \\ & \text{2. Pro }i=n,n-1,\dots ,0:\\ & \text{3. }T[i]\leftarrow 1\\ & \text{4. }P[i]\leftarrow 0\\ & \text{5. }\text{Pro }j=i+1,\dots ,n:\\ & \text{6. }\text{Pokud }{x}_i<x_j\text{ a }T[i]<1+T[j]:\\ & \text{7. }T[i]\leftarrow 1+T[j]\\ & \text{8. }P[i]\leftarrow j\end{array}$$

Algoritmus běží v $O(n^2)$ a jeho korektnost je dokazatelná induktivně dle $i$. Stačí si povšimnout, že začíná-li optimální řešení pro vstup $x_i,\dots ,x_n$ dvojicí $x_i,x_j$, pak z něj odebráním $x_i$ vznikne optimální řešení pro $x_j,\dots ,x_n$, tedy máme optimální substrukturu, protože existujíc lepší řešení pro kratší vstup tak bychom narazili na rozpor, protože by to bylo lepší řešení i pro vstup větší.

Zároveň díky $P$ můžeme vytrasovat jaké prvky jsou součástí podposloupnosti a sice, první je $P[0]$, druhý $P[P[0]]$ atd.

---

Editační vzdálenost

Editační operací na řetězci nazveme vložení, smazání nebo změnu jednoho znaku. Editační vzdálenost řetězců $x=x_1\dots x_n$ a $y=y_1\dots y_m$ udává, kolik nejméně editačních operací je potřeba, abychom z prvního řetězce vytvořili druhý. Značeno $L(x,y)$.

• Pokud $x_1=y_1$, můžeme první znak ponechat beze změny. Tehdy $L(x,y)=L(x_2\dots x_n,y_2\dots y_m).$
• Znak $x_1$ změníme na $y_1$. Pak $L(x,y)=1+L(x_2\dots x_n,y_2\dots y_m)$.
• Znak $x$ smažeme. Tehdy $L(x,y)=1+L(x_2\dots x_n,y_1\dots y_m)$.
• Na začátek vložíme $y_1$. Tehdy $L(x,y)=1+L(x_1\dots x_n,y_2\dots y_m)$ Pokaždé $L(x,y)$ závisí na vzdálenostech nějakých suffixů $x,y$.

$$\begin{array}{rl}& \text{Edit}\\ & \text{Vstup: Rˇeteˇzce }{x}_i\dots x_n\text{ a }{y}_j\dots y_m\\ & \text{Vyˊstup: Editacˇnıˊ vzdaˊlenost }L(x_i\dots x_n,y_j\dots y_m)\\ & \text{// prˇekontrolujeme zda neˇjakyˊ rˇeteˇzec jizˇ skoncˇıˊl}\\ & 1.\text{Pokud }i>n:\text{vraˊtıˊme }m-j+1\\ & 2.\text{Pokud }j>m:\text{vraˊtıˊme }n-i+1\\ & \text{// ponechaˊme znak nebo ho zmeˇnıˊme}\\ & 3.z\leftarrow \text{Edit}(i+1,j+1)\\ & 4.\text{Pokud }{x}_i\ne y_j:z\leftarrow z+1\\ & \text{// smazˇeme znak}\\ & 5.s\leftarrow \text{Edit}(i+1,j)\\ & \text{// vlozˇıˊme znak}\\ & 6.v\leftarrow \text{Edit}(i,j+1)\\ & 7.\text{Vraˊtıˊme }\min (z,s,v)\end{array}$$

Použitím principu dynamického programování spočteme tabulku $T$ odzadu, kde se tabulka bude chovat jako matice a každý prvek záleží na prvku vpravo dole od něj samotného.

$$\begin{array}{rl}& \text{Edit2}\\ & \text{Vstup: Rˇeteˇzce }{x}_i\dots x_n\text{ a }{y}_j\dots y_m\\ & \text{Vyˊstup: Editacˇnıˊ vzdaˊlenost }L(x_i\dots x_n,y_j\dots y_m)=T[1,1]\\ & 1.\text{Pro }i=1,\dots ,n+1\text{ polozˇıˊme }T[i,m+1]\leftarrow n-i+1\\ & 2.\text{Pro }j=1,\dots ,m+1\text{ polozˇıˊme }T[n+1,j]\leftarrow m-j+1\\ & 3.\text{Pro }i=n,\dots ,1:\\ & 4.\text{Pro }j=m,\dots ,1\\ & 5.\text{Je-li }{x}_i=x_j:\delta \leftarrow 0,\text{ jinak }\delta \leftarrow 1\\ & 6.T[i,j]\leftarrow \min (\delta +T[i+1,j+1],1+T[i+1,j],1+T[i,j+1])\end{array}$$

Algoritmus $\text{Edit2}$ běží v čase $\Theta (mn)$ a správnost je dokazatelná indukcí na délkách řetězců a pozorování o změnách editační vzdálenosti.