Operacijske raziskave

« nazaj

Operacijske raziskave - vaje 30.3.2020


Dinamično programiranje

graph TD 

A --- B
A --- C
B --- D
B --- E
C --- F
C --- G
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}\]
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)$