Dynamisk programmering

Å løse det samme problemet igjen og igjen

Splitt-og-hersk er elegant når delproblemene er ferske og uavhengige hver gang, som i Mergesort. Men noen problemer har en lei egenskap: den naive rekursjonen løser de samme delproblemene om og om igjen. dynamisk programmering er metoden for nettopp disse — regn ut hvert deltilfelle én gang, lagre svaret, og slå det opp neste gang du trenger det.

Ta stavkapping som førsteeksempel. Du har en stav av lengde $n$ og en prisliste som sier hva en bit av hver lengde er verdt. Du kan kappe staven i biter på de måtene du vil; målet er å maksimere total salgsverdi. Det første kuttet kan ha en hvilken som helst lengde $i$ fra 1 til $n$, og etter det kuttet sitter du igjen med en kortere stav av lengde $n-i$ som du løser på akkurat samme måte. ƒstavkapping fanger dette: den beste inntekten $r_n$ er det beste over alle førstekutt, $r_n={\max }_{1\le i\le n}(p_i+r_{n-i})$.

Skriver du dette rett ut som rekursjon, eksploderer arbeidet. For å regne $r_4$ trenger du $r_3,r_2,r_1,r_0$; men $r_3$ trenger igjen $r_2,r_1,r_0$, og $r_2$ trenger $r_1,r_0$. De små delinstansene dukker opp om og om igjen.

Delinstansgrafen og overlappet

La oss tegne avhengighetene. Hver delinstans er en node, og en pil fra $r_4$ til $r_2$ betyr «for å løse $r_4$ trenger jeg $r_2$».

Dette er det som gir DP sin slagkraft. Et naivt rekursjonstre ville hatt et eksponentielt antall noder, fordi $r_2$ tegnes på nytt hver gang den trengs. Men overlappende delinstanser delinstanser betyr at det egentlig bare finnes noen få distinkte delinstanser — her $r_0$ til $r_4$, altså $n+1$ stykker. Tegner vi dem som en graf i stedet for et tre, kollapser alle kopiene av $r_2$ til én node. Det er forskjellen mellom eksponentielt og polynomielt arbeid.

For at metoden skal gi riktig svar trengs en egenskap til: optimal delstruktur, formelt $\mathrm{OPT}(n)=\text{kombinasjon av }\mathrm{OPT}(\text{delinstanser})$ — se ƒoptimal delstruktur. En optimal løsning på hele problemet må være bygd av optimale løsninger på delene. For stavkapping holder dette: hvis det beste første kuttet er $i$, må resten av staven kappes optimalt — ellers kunne vi byttet ut resten med noe bedre og fått en bedre helhet. Mangler et problem denne egenskapen, virker verken DP eller grådighet.

Akkurat hvor mange distinkte delinstanser tabellen har, avgjør hvor rask DP-en blir. ƒantall delinstanser sier det rett ut: når antallet celler er polynomielt — her $O(n\cdot m)$ — og hver celle fylles i konstant eller polynomiell tid, blir hele algoritmen polynomiell. Hele kunsten i å bruke DP ligger i å finne en god måte å beskrive en delinstans på, slik at antallet holder seg lavt og hver av dem kan bygges fra noen få mindre.

To veier til svaret: memoisering og iterasjon

Når begge egenskapene er på plass, kan vi løse problemet på to måter som gir samme svar og samme kjøretid.

memoisering er top-down. Vi beholder den naturlige rekursjonen, men legger til et minne (et oppslagsverk eller et array): før vi regner ut en delinstans, sjekker vi om svaret allerede ligger der. Gjør det det, returnerer vi det med en gang; ellers regner vi det ut og lagrer det før vi returnerer.

Memo-Stavkapp(p, n, r):          # r starter som «uberegnet» for alle
    hvis r[n] er beregnet:
        returner r[n]
    hvis n == 0:
        beste = 0
    ellers:
        beste = -uendelig
        for i fra 1 til n:
            beste = max(beste, p[i] + Memo-Stavkapp(p, n-i, r))
    r[n] = beste
    returner beste

iterativ dp (bottom-up) er bottom-up. Her dropper vi rekursjonen og fyller en tabell i en rekkefølge der alt vi trenger allerede er regnet ut — for stavkapping fra $r_0$ og oppover:

Iter-Stavkapp(p, n):
    r[0] = 0
    for j fra 1 til n:
        beste = -uendelig
        for i fra 1 til j:
            beste = max(beste, p[i] + r[j-i])
        r[j] = beste
    returner r[n]

Valget er mest et spørsmål om smak og om problemet. Memoisering slipper å regne ut delinstanser som aldri trengs, og holder seg nær den rekursive intuisjonen. Iterasjon unngår funksjonskall-overhead og gjør det lett å resonnere om plassbruk. Begge gir her $\Theta (n^2)$ for stavkapping: $n$ delinstanser, hver med en løkke over opptil $n$ kutt.

LCS: dynamisk programmering i to dimensjoner

Stavkapping har én akse. Det neste klassiske eksempelet har to. lengste felles delsekvens (lcs) spør: gitt to strenger, hva er den lengste sekvensen av tegn som forekommer i begge, i samme rekkefølge, men ikke nødvendigvis sammenhengende? For ABCB og BDCB er svaret BCB med lengde 3. LCS brukes blant annet i diff-verktøy og i bioinformatikk for å sammenligne DNA.

Vi bygger en tabell $c[i,j]$ = lengden på LCS-en til de første $i$ tegnene av den ene strengen og de første $j$ av den andre. Tankegangen følger ƒlengste felles delsekvens: ser vi på tegn $x_i$ og $y_j$ og de er like, må de inngå i en lengste felles delsekvens, og vi øker diagonalen $c[i-1,j-1]$ med 1. Er de ulike, dropper vi ett tegn fra én av strengene og tar det beste av $c[i-1,j]$ og $c[i,j-1]$.

En tom prefiks gir LCS 0, så hele rad 0 og kolonne 0 er nuller — det er grunntilfellet vi fyller fra. Deretter fylles tabellen rad for rad. Svaret, lengden på hele LCS-en, står i cellen nederst til høyre.

Vil du ha selve sekvensen og ikke bare lengden, gjør du en rekonstruksjon: start nederst til høyre og spor tilbake. Kom verdien fra en diagonal økning, var tegnene like — ta med det tegnet og gå diagonalt opp-venstre. Ellers gå dit verdien kom fra (opp eller til venstre). Pilene i figuren viser nettopp denne stien. Tabellen har $\Theta (mn)$ celler, hver fylt i konstant tid, så LCS løses i $\Theta (mn)$ — nettopp den polynomielle celletellingen vi så over.

0/1-ryggsekk: når valget er ta eller la stå

Det siste eksempelet er ryggsekkproblemet (0/1). Du har en ryggsekk som tåler en vektgrense $W$, og en samling gjenstander med hver sin vekt og verdi. Du vil pakke maksimal total verdi. I 0/1-varianten tar du hver gjenstand helt eller ikke i det hele tatt — ingen halve.

Igjen bygger vi en tabell. La $K[i,w]$ være den beste verdien du kan oppnå med de $i$ første gjenstandene og en kapasitet på $w$. For hver gjenstand står du overfor ett valg, og ƒ0/1-ryggsekkproblemet skriver det ut: enten dropper du gjenstand $i$ (og sitter igjen med $K[i-1,w]$), eller du tar den hvis den får plass (og legger verdien $v_i$ til den beste pakkingen av kapasiteten som blir igjen, $K[i-1,w-w_i]$). Du velger det største av de to.

I eksempelet har vi tre gjenstander med (vekt, verdi) lik $(2,3)$, $(3,4)$ og $(4,5)$, og en sekk som tåler 5. Tabellen fylles rad for rad: hver rad legger til én gjenstand som et nytt valg. Den optimale verdien, 7, dukker opp nederst til høyre — den svarer til å ta gjenstand 1 og 2, som veier $2+3=5$ og er verdt $3+4=7$. Vil du vite hvilke gjenstander som ble valgt, sporer du tilbake: endret verdien seg da gjenstand $i$ kom inn, ble den tatt; ellers ble den droppet.

Kjøretiden er $\Theta (nW)$ — antall gjenstander ganger kapasiteten. Det ser polynomielt ut, og er det i $n$ og $W$, men $W$ er et tall, ikke en mengde data. Skriver vi $W$ med binærtall, vokser tabellen eksponentielt med antall siffer. Derfor kaller vi $\Theta (nW)$ pseudopolynomiell: rask for moderate vektgrenser, men ikke en virkelig effektiv løsning på det generelle problemet. Det er et fint sluttpoeng — dynamisk programmering er kraftig, men kjøretiden henger på hvor mange distinkte delinstanser tabellen faktisk har.