Operacijske raziskave

« nazaj

Operacijske raziskave - vaje 10.5.2021

---

Iskanje v globino

class Graf:
    ...

    def DFS(G, koreni=None, previsit=None, postvisit=None):
        def nothing(u, v):
            pass
        if koreni is None:
            koreni = G.vozlisca()
        if previsit is None:
            previsit = nothing
        if postvisit is None:
            postvisit = nothing
        globina = {}
        stars = {}
        def obisci(u, v=None):
            if u in globina:
                return
            globina[u] = 0 if v is None else globina[v] + 1
            stars[u] = v
            previsit(u, v)
            for w in G.sosedi(u):
                obisci(w, u)
            postvisit(u, v)
        for w in koreni:
            obisci(w)
        for u in G.vozlisca():
            if u not in globina:
                globina[u] = float('inf')
                stars[u] = None
        return (globina, stars)

Časovna zahtevnost: $O(m) + O(n)$ klicev funkcij previsit in postvisit

---

Naloga 1

Na sledečem grafu izvedi iskanje v globino. V primerih, ko imaš več enakovrednih izbir, upoštevaj abecedni vrstni red. Za vsako povezavo določi, ali se nahaja v drevesu iskanja v globino.

---

---

Bellman-Fordov algoritem

class UtezenDigraf(Digraf):
    ...
    
    def bellmanFord(G, koren):
        razdalja = {v: 0 if v == koren else float('inf')
                    for v in G.vozlisca()}
        stars = {koren: None}
        naslednji = {koren}
        for i in range(len(G)):
            if len(naslednji) == 0:
                break
            trenutni, naslednji = naslednji, set()
            for v in trenutni:
                d = razdalja[v]
                for w, r in G.utezeniSosedi(v).items():
                    r += d
                    if r < razdalja[w]:
                        razdalja[w] = r
                        stars[w] = v
                        naslednji.add(w)
        else: # če se for zanka ne konča z break
            if len(naslednji) > 0:
                raise ValueError("graf ima negativen cikel")
        return (razdalja, stars)

Časovna zahtevnost: $O(mn)$

---

Naloga 2

S pomočjo Bellman-Fordovega algoritma določi razdalje od vozlišča $A$ do ostalih vozlišč.

---

vozlišče	A	B	C	D	E	F	G	H
korak 0	0
korak 1		3/A				6/A
korak 2			10/B		12/B		14/F
korak 3				3/C			13/E
korak 4								7/D
korak 5							2/H
korak 6						1/G
korak 7
razdalja	0	3/A	10/B	3/C	12/B	1/G	2/H	7/D

---

Topološko urejanje

Topološko urejanje vozlišč digrafa ${u_1}, {u_2}, \dots, {u_n}$: za vsako povezavo ${u_i} {u_j}$ velja $i < j$.

class Digraf(Graf):
    ...
    
    def topoloskoUrejanje(G):
        stopnje = {u: len(G.vhodniSosedi(u)) for u in G.vozlisca()}
        vrsta = {u for u, s in stopnje.items() if s == 0}
        urejanje = []
        while len(vrsta) != 0:
            u = vrsta.pop()
            urejanje.append(u)
            for v in G.izhodniSosedi(u):
                stopnje[v] -= 1
                if stopnje[v] == 0:
                    vrsta.append(v)
        if len(urejanje) < len(G):
            raise ValueError("graf ima usmerjen cikel")
        return urejanje

Časovna zahtevnost: $O(m)$

---

Naloga 3

Dan je sledeči usmerjen acikličen graf.

1. Poišči topološko ureditev vozlišč zgornjega grafa.
2. Poišči najkrajšo pot od vozlišča $G$ do vozlišča $E$.
3. Poišči najdaljšo pot od vozlišča $G$ do vozlišča $E$.

---

1. Topološka ureditev: $G, A, H, B, C, D, F, E$

2. vozlišče	G	A	H	B	C	D	F	E
   razdalja	0	-1	-1	1	-3	-1	3	-1
   starš		G	A	A	A	C	C	B

   Časovna zahtevnost: $O(m)$

---

Naloga 4

Oviratlon je tekalna preizkušnja na 8 do 10 kilometrov dolgi poti z različnimi ovirami. Zanima nas, na koliko različnih načinov lahko pridemo od štarta do cilja. Dan je utežen usmerjen acikličen graf $G$ ter vozlišči $s$ in $t$, ki predstavljata štart oziroma cilj. Uteži na povezavah nam predstavljajo, na koliko načinov jih lahko prečkamo.

1. Reši nalogo za sledeči graf.

   

2. Zapiši algoritem, ki reši dani problem. Kakšna je njegova časovna zahtevnost?

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.