Operacijske raziskave

« nazaj

Operacijske raziskave - vaje 29.3.2021

---

Dinamično programiranje

• Deli in vladaj

  graph TD
    
  A --- B
  A --- C
  B --- D
  B --- E
  C --- F
  C --- G
  

• Dinamično programiranje

  graph TD
    
  A --- E
  B --- E
  B --- F
  C --- F
  C --- G
  D --- G
  E --- H
  F --- H
  F --- I
  G --- I
  H --- J
  I --- J
  

---

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?

---

1. • ${p_i}$ … maksimalna profitabilnost, če uporabimo prvih $i$ plakatnih mest

   $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

   Rešitev:

   • ${p_8} > {p_7}$: postavimo na 8. mesto
   • ${p_6} > {p_5}$: postavimo na 6. mesto
   • ${p_3} > {p_2}$: postavimo na 3. mesto
   • ${p_2} = {p_1}$: ne postavimo na 2. mesto
   • ${p_1} > 0$: postavimo na 1. mesto
2. • ${p_0} = 0$, ${x_0} = -\infty$
   • ${p_i} = \max \lbrace {p_{i-1}, {p_j} + {v_i} \mid {x_j} \le {x_i} - d} \rbrace$ ($1 \le i \le n$)
   • vrednosti ${p_i}$ računamo naraščajoče po indeksu $i$
   • optimalna vrednost: $p^* = {p_n}$

3. def plakati(x, v, d): # predpostavimo, da je x urejen
       n = len(x)
       assert n == len(v) # preveri, da velja zapisani pogoj
       x = [-float('inf'), *x]
       v = [0, *v]
       p = [0]
       j = 0
       for i in range(1, n+1):
           while x[j+1] <= x[i] - d:
               j += 1
           p.append(max(p[i-1], p[j] + v[i]))
       m = []
       i = n
       while i > 0:
           if p[i] > p[i-1]:
               m.append(i)
               y = x[i]
               while x[i] > y - d:
                   i -= 1
           else:
               i -= 1
       return (p[n], list(reversed(m)))
   

   Č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)$.

---

1. • ${p_j}$ … največja vrednost pri nosilnosti $j$ kilogramov
   • ${I_j}$ … množica predmetov teže največ $j$ kilogramov, s katero dosežemo vrednost ${p_j}$
   • ${p_0} = 0$, ${I_0} = \emptyset$
   • $({p_j}, {I_j}) = \max \lbrace ({p_{j-1}}, {I_{j-1}}), ({p_{j-{t_i}}} + {v_i}, {I_{j-{t_i}}} \cup \lbrace i \rbrace) \mid 1 \le i \le n, j \ge {t_i}, i \notin {I_{j-{t_i}}} \rbrace$ ($1 \le i \le M$)
   • vrednosti ${p_j}$ in ${I_j}$ računamo naraščajoče po indeksu $j$
   • optimalna rešitev $I^* = {I_M}$ z vrednostjo $p^* = {p_M}$
   • časovna zahtevnost: $O(Mn)$ - psevdopolinomski algoritem!
2. • ${p_0} = 0$, ${I_0} = \emptyset$
   • ${p_1} = 8$, ${I_1} = \lbrace 3 \rbrace$
   • ${p_2} = 8$, ${I_2} = \lbrace 3 \rbrace$
   • ${p_3} = 11$, ${I_3} = \lbrace 3, 7 \rbrace$
   • ${p_4} = 18$, ${I_4} = \lbrace 3, 5 \rbrace$
   • ${p_5} = 19$, ${I_5} = \lbrace 3, 4 \rbrace$
   • ${p_6} = 21$, ${I_6} = \lbrace 3, 5, 7 \rbrace$
   • ${p_7} = 27$, ${I_7} = \lbrace 1, 3, 5 \rbrace$
   • ${p_8} = 29$, ${I_8} = \lbrace 3, 4, 5 \rbrace$

---

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

---

• ${p_{ij}}$ … najmanjša vsota elementov na poti od ${a_{11}}$ do ${a_{ij}}$
• ${p_{11}} = {a_{11}}$
• ${p_{1j}} = {a_{1j}} + {p_{1, j-1}}$ ($2 \le j \le n$)
• ${p_{i1}} = {a_{i1}} + {p_{i-1, 1}}$ ($2 \le i \le m$)
• ${p_{ij}} = {a_{ij}} + \min \lbrace {p_{i-1, j}}, {p_{i, j-1}} \rbrace$ ($2 \le i \le m$, $2 \le j \le n$)
• vrednosti ${p_{ij}}$ računamo leksikografsko po $(i, j)$
• optimalna vrednost $p^* = {p_{mn}}$
• časovna zahtevnost: $O(mn)$

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.