Operacijske raziskave

Operacijske raziskave - vaje 8.4.2021

Dinamično programiranje

Naloga 1

Dan je niz $S = {a_1} {a_2} \dots {a_n}$, kjer so ${a_i}$ ($1 \le i \le n$) elementi neke končne abecede. Nizu ${a_j} {a_{j+1}} \dots {a_k}$, kjer je $1 \le j \le k \le n$, pravimo strnjen podniz niza $S$. S pomočjo dinamičnega programiranja napiši algoritem, ki določi najdaljši palindromski strnjen podniz v $S$.

${p_{jk}}$ … ali je strnjen podniz ${a_j} {a_{j+1}} \dots {a_k}$ palindrom
${p_{j,j-1}} = 1$ ($1 \le j \le n+1$)
${p_{jj}} = 1$ ($1 \le j \le n$)
${p_{jk}} = {p_{j+1,k-1}} \land {a_j} = {a_k}$ ($1 \le j < k \le n$)
računamo v leksikografskem vrstnem redu po $(k-j, j)$
dolžina najdaljšega strnjenega podniza $p^* = \max \lbrace k-j+1 \mid 1 \le j \le k \le n, {p_{jk}} = 1 \rbrace$
časovna zahtevnost: $O(n^2)$
obstaja tudi algoritem, ki teče v času $O(n)$

Naloga 2

Dana je matrika $A = (a_{ij})_{i,j=1}^{m,n}$. Poiskati želimo strnjeno podmatriko matrike $A$ z največjo vsoto komponent.

Reši problem za matriko
\[A = \begin{pmatrix} 1 & -1 & 2 & 4 \\ -3 & -2 & 8 & 2 \\ -3 & 2 & -2 & 4 \\ 1 & -5 & -1 & -2 \end{pmatrix} .\]
Napiši rekurzivne enačbe za opisani problem.
Napiši algoritem, ki reši opisani problem. Oceni tudi njegovo časovno zahtevnost v odvisnosti od $m$ in $n$.

${p_{hij}}$ … največja vsota komponent podmatrike z vrsticami od $h+1$ do $i$ in zadnjim stolpcem $j$
${v_{ij}}$ … vsota komponent do $i$-te vrstice v $j$-tem stolpcu
${v_{0j}} = 0$ ($1 \le j \le n$)
${v_{ij}} = {v_{i-1,j}} + {a_{ij}}$ ($1 \le i \le m$, $1 \le j \le n$)
${p_{hi0}} = 0$ ($0 \le h < i \le m$)
${p_{hij}} = {v_{ij}} - {v_{hj}} + \max \lbrace {p_{h,i,j-1}}, 0 \rbrace$ ($0 \le h < i \le m$, $1 \le j \le n$)
najprej izračunamo vrednosti ${v_{ij}}$ v leksikografskem vrstnem redu glede na $(i, j)$
nato izračunamo vrednosti ${p_{hij}}$ v leksikografskem vrstnem redu glede na $(h, i, j)$
največjo vsoto strnjene podmatrike dobimo kot $p^* = \max \lbrace {p_{hij}} \mid 0 \le h < i \le m, 0 \le j \le n \rbrace$

Naloga 3

Na ulici je $n$ vrstnih hiš, pri čemer je v $i$-ti hiši ${c_i}$ denarja. Tat se odloča, katere izmed hiš naj oropa. Vsak oropan stanovalec to sporoči svojim sosedom, zato tat ne sme oropati dveh sosednjih hiš. Ker je tat poslušal predmet Operacijske raziskave, pozna dinamično programiranje. Pokaži, kako naj tat določi, katere hiše naj oropa.

${p_i}$ … največja količina, ki jo lahko naropa v prvih $i$ hišah
${p_0} = 0$
${p_1} = \max \lbrace {c_1}, 0 \rbrace$
${p_i} = \max \lbrace {p_{i-1}}, {c_i} + {p_{i-2}} \rbrace$ ($2 \le i \le n$)
računamo naraščajoče po indeksu $i$
maksimalna količina $p^* = {p_n}$

Naloga 4

Imamo hlod dolžine $\ell$, ki bi ga radi razžagali na $n$ označenih mestih $0 < {x_1} < {x_2} < \dots < {x_n} < \ell$. Eno rezanje stane toliko, kolikor je dolžina hloda, ki ga režemo. Ko hlod prerežemo, dobimo dva manjša hloda, ki ju režemo naprej. Poiskati želimo zaporedje rezanj z najmanjšo ceno.

Reši problem pri podatkih $\ell = 10$ in $(x_i)_{i=1}^4 = (3, 5, 7, 8)$.
S pomočjo dinamičnega programiranja reši problem v splošnem. Oceni tudi njegovo časovno zahtevnost.

${p_{ij}}$ … najmanjša cena rezanja hloda od ${x_i}$ do ${x_{j+1}}$
${x_0} = 0$, ${x_{n+1}} = \ell$
${p_{ii}} = 0$ ($0 \le i \le n$)
${p_{ij}} = {x_{j+1}} - {x_i} + \min \lbrace {p_{i,h-1}} + {p_{hj}} \mid i+1 \le h \le j \rbrace$ ($0 \le i < j \le n$)
računamo leksikografsko po $(j-i, i)$
najmanjša skupna cena rezanja $p^* = {p_{0n}}$
časovna zahtevnost: $O(n^3)$

\[\begin{aligned} p_{01} &= 5-0 &&= 5 \\ p_{12} &= 7-3 &&= 4 \\ p_{23} &= 8-5 &&= 3 \\ p_{34} &= 10-7 &&= 3 \\[1ex] p_{02} &= 7-0 + \min\{0+4, 5+0\} &&= 11 & \text{režemo na $x_1 = 3$} \\ p_{13} &= 8-3 + \min\{0+3, 4+0\} &&= 8 & \text{režemo na $x_2 = 5$} \\ p_{24} &= 10-5 + \min\{0+3, 3+0\} &&= 8 \\[1ex] p_{03} &= 8-0 + \min\{0+8, 5+3, 11+0\} &&= 16 & \text{režemo na $x_1 = 3$ ali $x_2 = 5$} \\ p_{14} &= 10-3 + \min\{0+8, 4+3, 8+0\} &&= 14 & \text{režemo na $x_3 = 7$} \\[1ex] p_{04} &= 10-0 + \min\{0+14, 5+8, 11+3, 16+0\} &&= 23 & \text{režemo na $x_2 = 5$} \end{aligned}\]

graph TD

04[0 - 10: 23] --- 01[0 - 5: 5]
04 --- 24[5 - 10: 8]
01 --- 00[0 - 3]
01 --- 11[3 - 5]
24 --- 23[5 - 8: 3]
24 --- 44[8 - 10]
23 --- 22[5 - 7]
23 --- 33[7 - 8]

Naloga 5

Na voljo imamo kovance z vrednostmi $1 = {v_1} < {v_2} < \cdots < {v_n}$ in vsoto $C$, ki jo želimo izplačati s kovanci. Predpostavljamo, da imamo dovolj velik nabor kovancev.

Poišči izplačilo z najmanjšim številom kovancev za $C = 25$, $n = 4$ in $(v_i)_{i=1}^n = (1, 2, 5, 7)$.
S pomočjo dinamičnega programiranja reši problem v splošnem.

Naloga 6

Imamo zaporedje $n$ polj, pri čemer je na $i$-tem polju zapisano število ${a_i}$. Na voljo imamo še $\lfloor n/2 \rfloor$ domin, z vsako od katerih lahko pokrijemo dve sosednji polji. Vsaka domina je sestavljena iz dveh delov: na enem je znak $+$, na drugem pa znak $-$. Posamezno polje lahko pokrijemo z le eno domino; če sta pokriti dve sosednji polji, morata biti pokriti z različnima znakoma (bodisi z iste, bodisi z druge domine). Iščemo tako postavitev domin, ki maksimizira vsoto pokritih števil, pomnoženih z znakom na delu domine, ki pokriva število. Pri tem ni potrebno, da uporabimo vse domine.

Primer dopustnega (ne nujno optimalnega) pokritja:

	[+	-]			[-	+]	[-	+]
6	3	-4	2	-3	5	9	1	2

Vsota tega pokritja je $3 - (-4) - 5 + 9 - 1 + 2 = 12$. Če bi eno od zadnjih dveh domin obrnili (zamenjala bi se znaka), dobljeno pokritje ne bi bilo dopustno, saj bi dve zaporedni polji bili pokriti z enakima znakoma.

Zapiši rekurzivne enačbe za reševanje danega problema. Razloži, kaj predstavljajo spremenljivke, v kakšnem vrstnem redu jih računamo, ter kako dobimo optimalno rešitev.

Namig: posebej obravnavaj dva primera glede na postavitev zadnje domine.
Oceni časovno zahtevnost algoritma, ki sledi iz zgoraj zapisanih enačb.
S svojim algoritmom poišči optimalno pokritje za zgornji primer.

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.