Operacijske raziskave - vaje 30.3.2020

--- tags: vaje, or, dinamicno programiranje hackmd: https://hackmd.io/lg1h-7IvR6Gq_qxARZVQng plugins: mathjax, mermaid --- # Operacijske raziskave - vaje 30.3.2020 --- ## Dinamično programiranje * Deli in vladaj ```mermaid graph TD A --- B A --- C B --- D B --- E C --- F C --- G ``` * Dinamično programiranje ```mermaid graph TD A --- F B --- F B --- G C --- G C --- H D --- H D --- I E --- I F --- J G --- J G --- K H --- K H --- L I --- L J --- M K --- M K --- N L --- N N --- O M --- O ``` --- ### Naloga 1 Na avtocestni odsek dolžine $M$ kilometrov želimo postaviti oglasne plakate. Dovoljene lokacije plakatov določa urad za oglaševanje in so predstavljene s števili $x_1, x_2, \dots x_n$, kjer $x_i$ ($1 \le i \le n$) predstavlja oddaljenost od začetka odseka v kilometrih. Profitabilnost oglasa na lokaciji $x_i$ določa vrednost $v_i$ ($1 \le i \le n$). Urad za oglaševanje podaja tudi omejitev, da mora biti razdalja med oglasi vsaj $d$ kilometrov. Oglase želimo postaviti tako, da bodo čim bolj profitabilni. 1. Reši problem za parametre $M = 20$, $d = 5$, $n = 8$, $(x_i)_{i=1}^n = (1, 2, 8, 10, 12, 14, 17, 20)$ in $(v_i)_{i=1}^n = (8, 8, 12, 10, 7, 5, 6, 10)$. 2. Napiši rekurzivne enačbe za opisani problem. 3. Napiši algoritem, ki poišče najbolj profitabilno postavitev oglasov za dane parametre. Kakšna je njegova časovna zahtevnost? ---- | $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | | --- | - | - | - | - | - | - | - | - | | $x_i$ | 1 | 2 | 8 | 10 | 12 | 14 | 17 | 20 | | $v_i$ | 8 | 8 | 12 | 10 | 7 | 5 | 6 | 10 | | $p_i$ | 8 | 8 | 20 | 20 | 20 | 25 | 26 | 35 | | $y_i$ | 0 | | 2 | | | 3 | 5 | 6 | Kam postavimo plakate: $x_8 = 20, x_6 = 14, x_3 = 8, x_1 = 1$. $$ \begin{aligned} y_0 &= 0 \\ p_0 &= 0 \\ y_i &= \max\{j \mid y_{i-1} \le j \le i-1, x_j \le x_i - d\} & (i > 0) \\ p_i &= \max\{p_{i-1}, v_i + p_{y_i}\} & (i > 0) \\ p^* &= p_n \end{aligned} $$ ---- ```python def plakati(x, v, d): n = len(x) j = 0 s = [] for i, xi in enumerate(x): while xi - x[j] >= d: j += 1 if j == 0: p = 0 y = None else: y = j - 1 p = s[y][0] p += v[i] if i > 0 and p < s[i-1][0]: y = i - 1 p = s[y][0] b = False else: b = True s.append((p, y, b)) p, y, b = s[-1] pozicije = [] if b: pozicije.append(n - 1) while y is not None: z = y _, y, b = s[y] if b: pozicije.append(z) return (p, list(reversed(pozicije))) ``` Časovna zahtevnost: $O(n)$ --- ### Naloga 2 Imamo nahrbtnik nosilnosti $M$ kilogramov. Danih je $n$ objektov z vrednostmi $v_i$ in težami $t_i$ ($1 \le i \le n$). Problem nahrbtnika sprašuje po izbiri predmetov $I \subseteq \{1, 2, \dots, n\}$, ki maksimizira njihovo skupno vrednost pri omejitvi $\sum_{i \in I} t_i \le M$. 1. Napiši rekurzivne enačbe za opisani problem. 2. Z uporabo rekurzivnih enačb reši problem za parametre $M = 8$, $n = 8$, $(v_i)_{i=1}^n = (9, 9, 8, 11, 10, 15, 3, 12)$ in $(t_i)_{i=1}^n = (3, 5, 1, 4, 3, 8, 2, 7)$. ---- $$ \begin{aligned} (p_0, I_0) &= (0, \emptyset) \\ (p_j, I_j) &= \max(\{(p_{j-t_i} + v_i, I_{j-t_i} \cup \{i\}) \mid 1 \le i \le n, t_i \le j, i \not\in I_{j-t_i}\} \cup \{(p_{j-1}, I_{j-1})\}) & (j > 0) \\ (p^*, I^*) &= (p_M, I_M) \end{aligned} $$ | $j$ | $p_j$ | $I_j$ | | --- | ----- | ----- | | 0 | 0 | $\emptyset$ | | 1 | 8 | $\{3\}$ | | 2 | 8 | $\{3\}$ | | 3 | 11 | $\{3, 7\}$ | | 4 | 18 | $\{3, 5\}$ | | 5 | 19 | $\{3, 4\}$ | | 6 | 21 | $\{3, 5, 7\}$ | | 7 | 27 | $\{1, 3, 5\}$ | | 8 | 29 | $\{3, 4, 5\}$ | $p^* = 29$, $I^* = \{3, 4, 5\}$ Časovna zahtevnost: $O(Mn)$ - psevdopolinomska! --- ### Naloga 3 Dana je matrika $A = (a_{ij})_{i,j=1}^{m,n}$. Poiskati želimo pot minimalne vsote, ki se začne v levem zgornjem kotu (pri $a_{11}$) in konča v desnem spodnjem kotu (pri $a_{mn}$). Dovoljeni so zgolj premiki v desno in navzdol. 1. Reši problem za matriko $$ A = \begin{pmatrix} 131 & 673 & 234 & 103 & 18 \\ 201 & 96 & 342 & 965 & 150 \\ 630 & 803 & 746 & 422 & 111 \\ 537 & 699 & 497 & 121 & 956 \\ 805 & 732 & 524 & 37 & 332 \end{pmatrix} . $$ 2. Napiši rekurzivne enačbe za opisani problem. 3. Na osnovi rekurzivnih enačb napiši algoritem, ki reši opisani problem. Oceni tudi njegovo časovno zahtevnost v odvisnosti od $m$ in $n$. ---- $$ \begin{aligned} p_{11} &= a_{11} \\ p_{1j} &= a_{1j} + p_{1, j-1} & (j > 1) \\ p_{i1} &= a_{i1} + p_{i-1, 1} & (i > 1) \\ p_{ij} &= a_{ij} + \min\{p_{i-1, j}, p_{i, j-1}\} & (i, j > 1) \\ p^* &= p_{mn} \end{aligned} $$ $$ \newcommand{\l}{\leftarrow} \newcommand{\g}{\uparrow} P = \begin{pmatrix} 131 & \l 804 & \l 1038 & \l 1141 & \l 1159 \\ \g 332 & \l 428 & \l 770 & \l 1735 & \g 1309 \\ \g 962 & \g 1231 & \g 1516 & \l 1938 & \g 1420 \\ \g 1499 & \g 1930 & \g 2013 & \g 2059 & \g 2376 \\ \g 2304 & \g 2662 & \g 2537 & \g 2096 & \l 2428 \end{pmatrix} . $$ Časovna zahtevnost: $O(mn)$

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.