Skip to content

2021-03-29.md

Latest commit

 

History

History
163 lines (128 loc) · 5.55 KB

2021-03-29.md

File metadata and controls

163 lines (128 loc) · 5.55 KB
tags vaje, or, dinamicno programiranje
hackmd https://hackmd.io/6sImSnqTSwiw_UnVJ2ls6A
plugins mathjax, mermaid

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
    Loading

  • 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
    Loading

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?
    • ${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
    • ${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)$.
    • ${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!
    • ${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)$