Dynamisk programmering

Dynamisk programmering löser problem som har två egenskaper:

1. Optimal delstruktur — den bästa lösningen byggs av bästa lösningar på delproblem.
2. Överlappande delproblem — samma delproblem dyker upp om och om igen.

Naiv rekursion räknar om samma sak exponentiellt många gånger. DP sparar delresultaten och går från $O(2^n)$ till $O(n^2)$ eller bättre.

Två sätt att göra det:

• Memoisering (top-down): vanlig rekursion plus en cache. Enklast — ofta räcker @functools.cache.
• Tabulering (bottom-up): fyll en tabell i rätt ordning. Snabbare och utan rekursionsdjup.

from functools import cache
import numpy as np

# 1. Editavstånd (Levenshtein) — används för stavningsrättning och eval-mått
def editavstand(a: str, b: str) -> int:
    m, n = len(a), len(b)
    d = np.zeros((m + 1, n + 1), dtype=int)
    d[:, 0] = np.arange(m + 1); d[0, :] = np.arange(n + 1)
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            kostnad = 0 if a[i-1] == b[j-1] else 1
            d[i, j] = min(d[i-1, j] + 1,        # ta bort
                          d[i, j-1] + 1,        # lägg till
                          d[i-1, j-1] + kostnad)  # byt ut
    return int(d[m, n])

print(editavstand("kitten", "sitting"))     # 3

# 2. Viterbi — mest sannolika dolda sekvensen (POS-taggning, taligenkänning)
def viterbi(obs, tillstand, start_p, trans_p, emit_p):
    V = [{s: start_p[s] * emit_p[s][obs[0]] for s in tillstand}]
    vag = {s: [s] for s in tillstand}
    for t in range(1, len(obs)):
        V.append({}); ny_vag = {}
        for s in tillstand:
            p, fore = max((V[t-1][f] * trans_p[f][s] * emit_p[s][obs[t]], f) for f in tillstand)
            V[t][s] = p; ny_vag[s] = vag[fore] + [s]
        vag = ny_vag
    p, sista = max((V[-1][s], s) for s in tillstand)
    return vag[sista], p

# 3. Memoisering räcker ofta
@cache
def fib(n):
    return n if n < 2 else fib(n-1) + fib(n-2)
print(fib(100))    # omedelbart; utan cache: astronomiskt

Var du möter DP i ML: editavstånd i utvärderingsmått (WER för taligenkänning), Viterbi i sekvensmärkning och HMM, beam search som approximativ DP, och CTC-förlusten i taligenkänning.