Dinamično programiranje

Memoizacija

Denimo, da imamo funkcijo f, ki računa zelo počasi, zato želimo shranjevati rezultate za kasnejšo uporabo in si s tem prihraniti ponovno računanje.

Definicijo funkcije f lahko popravimo tako, da uporablja slovar. Denimo, da imamo:

def f(x):
    y = ⟨zamuden-računski-postopek>
    return y

Izboljšamo jo takole:

d = {} # slovar do sedaj izračunanih vrednosti x ↦ f(x)
def f(x):
    if x in d:
        # rezultat je že spravljen v slovarju
        return d[x]
    else:
        # rezulat moramo izračunati
        y = ⟨zamuden-računski-postopek>
        d[x] = y # spravimo v slovar za nadaljno uporabo
        return y

Postopku, ki funkcijo f predela v enakovredno funkcijo, ki hrani do sedaj izračunane rezultate, pravimo memoizacija.

Memoizacije nam ni treba vsakič implementirati na roko, v ta namen lahko definiramo funkcijo memo, ki sprejme funkcijo f in vrne njeno memoizirano inačico.

def memo(f):
    """memo(f) sprejme funkcijo f in vrne njeno memoizirano inačico."""
    cache = {}

    # Pomožna funkcija, ki deluje tako kot f, le da pogleda v cache, preden
    # izračuna rezultat. V Pythonu *args pomeni "vsi argumenti, kolikor jih pač je".
    # Na ta način lahko memoiziramo funkcije, ki sprejmejo poljubno število argumentov.
    def g(*args):
        if args in cache:
            return cache[args]
        else:
            y = f(*args)
            cache[args] = y
            return y

    return g

Funkcijo f sedaj memoiziramo tako, da pokličemo memo(f). Primere najdete v memo_primeri.py.

Funkcija memo ne deluje dobro na rekurzivni funkcijah, ker ne prestreže rekurzivnih klicev, glej primer fib v memo_primeri.py.

Če želimo, da memoizacija pravilno deluje na rekurzivni funkciji f, to naredimo takole:

def f(x):
  ....

f = memo(f)

To isto lahko dosežemo z dekoratorjem.

Dekoratorji

Prava rešitev so Pythonovi dekoratorji. Ti omogočajo, da definicijo funkcije f “dekoriramo” s funkcijo memo in takoj dobimo memoiziran f. Splošna oblika je

@dekorator
def f(...):
   ...

Fibonaccijeva števila z dekoratorjem definiramo takole:

@memo
def fibo(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

Poleg teba bodo rekurzivni klici poklicali memoizirano funkcijo, kar smo želeli.

V memo_primeri.py je še primer memoizacije funkcije dveh argumentov, ki računa binomske koeficiente.

Dinamično programiranje

Spoznali smo že me algoritme tipa deli & vladaj, pri katerih problem delimo na manjše dele, ki jih rešimo rekurzivno z istim postopkom in njihove rešitve sestavimo skupaj.

Lahko se zogdi, da se podprobeli pri deli & vladaj ponavljajo. V tem primeru jih je nesmiselno znova in znova reštevati, raje njihove rešitve memoiziramo.

Z dinamičnim programiranjem lahko rešujemo optimizacijske probleme, ki imajo naslednje lastnosti:

Imamo problem P, ki ga lahko rešimo na več načinov. Na primer: “poišči pot od Ljubljane do Maribora”.
Izmed vseh rešitev nas zanima optimalna glede na dano cenilko. Na primer: “najkrajša pot od Ljubljane do Maribora”.
Problem znamo razstaviti na podprobleme istega tipa in njihove rešitve setaviti po načelu deli & vladaj. Na primer" “pošiči pot od Ljubljane do Celja in pot od Celja do Maribora”.
Podproblemi se ponavljajo (če se ne, imamo običajno “deli & vladaj”).
Velja načelo optimalnosti: optimalna rešitev problema je sestavljna iz optimalnih rešitev podproblemov. Na primer: “najkrajša pot od Ljubljane do Maribora, ki vodi skozi Celje, je sestavljena iz najkraše poti od Ljubljane do Celja in najkrajše poti od Celja do Marbora.”

Kadar je zadoščeno zgornjim pogojem, lahko uporabimo metodo, ki se zaradi zgodvonskih razlogov imenuje dinamično programiranje:

Optimalno rešitev osnovnega problema najdemo neposredno (zaustavljalni pogoj).
Večje probleme razstavimo na podprobleme, ki jih rešimo rekurzivno. Pri tem uporabimo memoizacijo, da ne rešujemo istih podproblemov večkrat.
Z uporabo načela optimalnosti sestavimo optimalne rešitve podproblemov v optimalno rešitev.

Kako to deluje, se najbolje vidi na primerih.

Primer: 0-1 nahrbtnik

Tat krade izdelke iz trgovine. S seboj je prinesel nahrbtnik, v katetega daje nakradene izdelke. Vsak izdelek ima vrednost in velikost. Katere izdelke naj ukrade tat, da bodo imeli čim večjo skupno vrednost in ne bodo presegali kapacitete nahrbtnika?

Izdelke označimo 0, 1, 2, …, n-1. Vrednost i-tega naj bo vrednostᵢ in velikost velikostᵢ. Ali imamo opravka z dinamičnim programiranjem? Da, vendar moramo premisliti, kaj so podproblemi.

Naj bo V(i,k) problem: Poišči izbor izdelkov i, i+1, …, n-1 ki ne presega skupne velikosti k in ima največjo možno skupno vrednost.

Naj bo v(i,k) vrednost optimalne rešitve problema V(i,k).

Preverimo, da veljajo pogoji za dinamično programiranje:

Problem V(i, k) je osnovni primer je je i ≥ n (ni več izdelkov na vojo) ali k = 0 (ni več prostora).
Za i < n in k > 0 lahko V(i, k) razbijemo na podprobleme:
- če je velkostᵢ > k je V(i, k) = V(i+1, k) ker je i-ti izdelek prevelik in ga ne vzamemo
- sicer V(i, k) razbijemo na podproblema V(i+1, k) (izdelka i ne vzamemo) in V(i+1, k-velikostᵢ) (izdelek i damo v nahrbtnik).

Načelo optimalnosti velja:

 v(i, k) = 0 če je i ≥ n ali k = 0
 v(i, k) = v(i+1, k) če je velikostᵢ > k
 v(i, k) = max (v(i+1,k), vrednostᵢ + v(i+1, k - velikostᵢ)

Rešitev najdemo v nahrbtnik.py.

Primer: najkrajša pot v grafu

Dan je aciklični graf G = (V, E):

V je množica vozlišč
E je množica usmerjenih povezav

Za vsako povezavo (u,v) ∈ E je dana razdalja d(u,v) > 0 med njima.

Naloga: poisči najkrajšo pot po grafu med dvema danima vozliščema.

Naj bo P(x,y) najkrajša pot od vozlišča x do vozlišča y in ℓ(x,y) njena dolžina. Preverimo pogoje dinamičnega programiranja:

P(x,y) je osnovni problem, če je x = y. Velja ℓ(x,x) = 0.
P(x,y) razbijemo na podprobleme: za vsako povezavo x → z rešimo podproblem P(z,x). Če poznamo najkrajše poti od sosedov vozlišča x do y, potem lahko iz njih izračunamo najkrajšo pod od x do y.
Načelo optimalnosti: če najkrajša pot od x do y vodi preko soseda z, potem je najkrajša tudi od z do y. Velja rekurzivna zveza:
```
 ℓ(x,x) = 0
 ℓ(x,y) = min { d(x,z) + ℓ(z,y) | (x,z) ∈ E }
```

Rešitev najdemo v najkrajsa_pot.py.

Vprašanja

Ali se podproblemi pri 0-1 nahrbtniku ponavljajo?
Ali se podproblemi pri iskanju najkrajše poti ponavljajo?
Kako poiščemo najkrajšo pot v grafu, ki ima cikle?