Dynamisk programmering

Dynamisk programmering (DP) er en designmetode for optimeringsproblemer der den rekursive løsningen løser de samme delinstansene om og om igjen. I stedet for å regne dem ut på nytt løser vi hver delinstans én gang og slår opp svaret senere. Naiv rekursjon kan være eksponentiell; DP gjør den polynomisk ved å bytte gjentatt regning mot litt minne.

To forutsetninger: delstruktur og overlapp

DP er riktig verktøy nøyaktig når problemet har to egenskaper samtidig.

Det er nyttig å se dette som en delinstansgraf: én node per distinkt delinstans, med en kant fra en delinstans til hver delinstans den avhenger av. Overlapp betyr at flere veier ender i samme node. Optimal delstruktur betyr at en nodes verdi kan regnes ut fra verdiene til etterfølgerne. Kjøretiden til DP-en er da ganske enkelt: antall noder $\times$ arbeidet per node.

Memoisering vs. iterasjon

Det finnes to måter å fylle inn delinstansgrafen på — de regner ut nøyaktig de samme verdiene, men i motsatt rekkefølge.

Begge gir samme asymptotiske kjøretid. Verdien vi lagrer er som regel bare den optimale tallverdien; for å få selve løsningen lagrer vi i tillegg hvilket valg som var optimalt i hver celle, og rekonstruerer ved å følge valgene bakover fra det ferdige svaret.

Oppskrift: slik setter du opp en DP

1. Karakteriser strukturen

   Vis at en optimal løsning er bygd av optimale delløsninger — finn det første valget som splitter problemet i mindre, uavhengige delinstanser.

2. Definer verdien rekursivt

   Skriv $\text{OPT}(\text{delinstans})$ som et maksimum/minimum over de mulige første valgene, uttrykt ved $\text{OPT}$ av mindre delinstanser. Husk grunntilfellene.

3. Regn ut nedenfra (eller memoiser)

   Fyll en tabell over alle distinkte delinstanser i en rekkefølge som respekterer avhengighetene — bottom-up med løkker, eller top-down med memoisering.

4. Rekonstruer løsningen

   Lagre hvilket valg som ga optimum i hver celle, og følg valgene bakover fra svaret for å sette sammen den faktiske løsningen.

Stavkapping

I stavkapping har vi en stav av lengde $n$ og en prisliste $p[1..n]$, og skal kappe den i biter som maksimerer total pris. Det første valget er lengden $i$ på den første biten; resten er en stav av lengde $n-i$, som vi løser optimalt på samme måte. Det gir rekurrensen

$r(n) = \max_{1 \le i \le n}\big(\, p[i] + r(n-i) \,\big), \qquad r(0) = 0.$

Det er bare $n+1$ distinkte delinstanser $r(0), \dots, r(n)$, og hver tar $O(n)$ arbeid, så bottom-up-DP-en er $\Theta(n^2)$ — mot eksponentiell naiv rekursjon. Med prislisten $p = [1, 5, 8, 9]$ fyller vi tabellen nedenfra:

Lengste felles delsekvens (LCS)

LCS finner den lengste sekvensen som forekommer (ikke nødvendigvis sammenhengende) i begge to strenger $X$ og $Y$. Sammenlign de siste tegnene: er de like, hører tegnet med i LCS-en, og vi går videre på begge prefiksene. Er de ulike, er svaret det beste av å droppe det siste tegnet i $X$ eller i $Y$:

$c[i,j] = \begin{cases} 0 & i=0 \text{ eller } j=0 \\ c[i-1,j-1] + 1 & x_i = y_j \\ \max(c[i-1,j],\, c[i,j-1]) & x_i \ne y_j. \end{cases}$

Tabellen $c$ har $(m+1)(n+1)$ celler og hver fylles i $O(1)$, så LCS er $\Theta(mn)$. Lagrer vi hvilken av de tre reglene som ga hver celle, kan vi rekonstruere selve delsekvensen ved å følge pilene fra $c[m,n]$ tilbake til hjørnet.

Binært ryggsekkproblem

Det binære ryggsekkproblemet (appendiks E) gir $n$ gjenstander med vekt $w_i$ og verdi $v_i$ og en sekk med kapasitet $W$. Hver gjenstand tas helt eller ikke i det hele tatt (derav «binært»). Vi maksimerer verdien innenfor kapasiteten. Det første valget er om gjenstand $i$ er med:

$K[i, c] = \max\big(\, K[i-1, c],\ \ v_i + K[i-1, c - w_i] \,\big),$

der den andre grenen bare gjelder når $w_i \le c$. Tabellen har $n \cdot W$ celler, hver fylt i $O(1)$, så DP-en er $\Theta(nW)$.

Sjekk deg selv