Dynamisk programmering

Splitt og hersk deler en instans i delinstanser uten noe felles og løser hver av dem én gang. I mange problemer trengs den samme delinstansen av flere større instanser, og en rekursiv prosedyre løser den på nytt hver gang. Dynamisk programmering dekomponerer på samme måte som den rekursive prosedyren, men lagrer hvert delsvar første gang det regnes ut. Da er kjøretiden som regel lineær i antall forskjellige delinstanser og avhengighetene mellom dem, ikke i antall kall, og det kan være forskjellen på polynomisk og eksponentiell tid.

Stavkapping

En stav med lengde $n$ skal kappes i biter med heltallige lengder og selges. En bit med lengde $i$ gir prisen $p_i$, og målet er størst mulig totalpris $r_n$. Prisene i eksemplene er $p_1, \ldots, p_8 = 1, 5, 8, 9, 10, 17, 17, 20$. Staven kan kappes eller ikke i hvert av de $n - 1$ heltallige punktene, så det finnes $2^{n-1}$ kappinger. For $n = 4$ er to biter med lengde 2 best, til $5 + 5 = 10$ kr.

Dekomponer ved å velge det første kuttet. Gir det en bit med lengde $i$, får du $p_i$ for den, og resten er en stav med lengde $n - i$, en mindre instans av samme problem. Totalprisen er $p_i$ pluss prisen for resten, så den blir størst når resten kappes optimalt: var resten kappet dårligere, kunne du byttet ut den kappingen og fått en bedre kapping av hele staven. Det beste med første bit $i$ er altså $p_i + r_{n-i}$. En av de $n$ lengdene er den første biten i en optimal kapping, så du prøver alle og tar den beste:

Cut-Rod er denne rekurrensen skrevet som rekursiv prosedyre. Den er riktig, men treg. Kallet på lengde $n$ kaller seg selv på alle lengder fra $n - 1$ ned til 0, og hvert av dem gjør det samme. Antall kall $T(n)$ er ett for rota pluss alle kallene under de $n$ barna:

Trekk fra den samme ligningen for $n - 1$. Da faller 1 og leddene $T(0), \ldots, T(n-2)$ bort, og bare $T(n-1)$ står igjen:

Det siste steget bruker $T(0) = 1$, for kallet på lengde 0 kaller ingenting. Cut-Rod gjør altså like mye arbeid som å prøve alle kappingene.

Overlappende delinstanser og memoisering

Cut-Rod løser de samme delinstansene om og om igjen. Kallet på lengde 4 kaller lengde 2 direkte, og kallet på lengde 3 kaller lengde 2 én gang til. I hele kalltreet for $n = 4$ kalles lengde 1 fire ganger og lengde 0 åtte ganger. Det finnes bare $n + 1$ forskjellige delinstanser, lengdene 0 til $n$, men $2^n$ kall.

Delinstansene er overlappende når flere instanser bygger på den samme delinstansen, direkte eller indirekte. Skjer det på mange nivåer, blir den rekursive løsningen eksponentiell. I splitt og hersk skjer det ikke. Merge-Sort deler tabellen i to halvdeler uten felles elementer, og hver delinstans trengs av bare én større instans.

Delinstansgrafen har én node per forskjellig delinstans, og en kant fra $u$ til $v$ når svaret for $v$ bygger på svaret for $u$. For stavkapping er nodene lengdene 0 til $n$, med en kant fra $j$ til $k$ for hver $j < k$. Læreboka tegner kantene motsatt vei, og retningen spiller ingen rolle så lenge det er klart hva som bygger på hva. Grafen må være asyklisk, og hver kjede av avhengigheter må ende i et grunntilfelle. Ellers bygger en instans til slutt på seg selv, og rekursjonen stopper aldri. Kalltreet har én node for hver sti i grafen som ender i instansen, så en delinstans med mange stier til instansen står mange steder i treet.

Memoisering gir prosedyren hukommelse. Første gang den kalles med et argument, regner den ut svaret og lagrer det. Senere kall med samme argument slår opp svaret og returnerer med en gang. For stavkapping holder en tabell $r[0 .. n]$ der $-\infty$ betyr at delinstansen ikke er løst. Uten de tre linjene som leser og skriver $r$, er aux under nøyaktig Cut-Rod.

from math import inf

def memoized_cut_rod(p, n):  # p[0] er ubrukt, p[i] er prisen for lengde i
  r = [-inf] * (n + 1)
  return aux(p, n, r)

def aux(p, n, r):
  if r[n] >= 0:
      return r[n]
  if n == 0:
      q = 0
  else:
      q = -inf
      for i in range(1, n + 1):
          q = max(q, p[i] + aux(p, n - i, r))
  r[n] = q
  return q

Med memo beregnes hver lengde $k$ én gang, og den beregningen har $k$ runder i løkka. Til sammen er det $1 + 2 + \cdots + n = \Theta(n^2)$ kall utover det første, ett per kant i delinstansgrafen.

Nedenfra og opp

Rekursjonen i den memoiserte versjonen sørger bare for at en delinstans er løst før noen bygger på den. Du kan like gjerne sørge for det direkte, ved å løse delinstansene i en rekkefølge der hver av dem kommer etter alle den bygger på. En slik rekkefølge er en topologisk sortering av delinstansgrafen, og for stavkapping er det bare $0, 1, \ldots, n$. Denne formen kalles iterasjon nedenfra og opp, bottom-up, og memoisering kalles tilsvarende ovenfra og ned, top-down. Bottom-Up-Cut-Rod fyller $r$ fra venstre, og når den kommer til $r[j]$, er $r[0 .. j - 1]$ ferdige.

Tabellen $r$ gir bare den beste prisen. For å finne kappingen lagrer du også valget: $s[j]$ er lengden på den første biten i en optimal kapping av lengde $j$. Kappingen leses av bakfra. Skriv ut $s[n]$, trekk den fra $n$, og gjenta til $n = 0$. For $n = 7$ er $s[7] = 1$ og $s[6] = 6$, altså én bit med lengde 1 og én med lengde 6, til $1 + 17 = 18$ kr.

from math import inf

def bottom_up_cut_rod(p, n):
  r = [0] * (n + 1)
  s = [0] * (n + 1)
  for j in range(1, n + 1):
      q = -inf
      for i in range(1, j + 1):
          if p[i] + r[j - i] > q:
              q = p[i] + r[j - i]
              s[j] = i
      r[j] = q
  return r, s

def print_cut_rod_solution(p, n):
  r, s = bottom_up_cut_rod(p, n)
  while n > 0:
      print(s[n])
      n = n - s[n]

De to løkkene gir $\Theta(n^2)$, som den memoiserte versjonen. Bottom-up slipper kallene og er som regel raskere med en konstant faktor. Memoisering løser bare delinstansene som faktisk trengs, og de kan være færre enn alle.

Generelt er kjøretiden summen av arbeidet med hver delinstans. Koster hver kant i delinstansgrafen konstant tid, er kjøretiden lineær i antall noder og kanter. Stavkapping har $n + 1$ noder og $n(n + 1)/2$ kanter, altså $\Theta(n^2)$.

Optimal delstruktur

I en optimal kapping er resten etter den første biten selv kappet optimalt, ellers kunne du byttet den ut og fått en bedre kapping av hele staven. En optimal løsning består altså av optimale løsninger på delinstansene. Den egenskapen kalles optimal delstruktur, og den gjør rekurrensen for $r_n$ riktig. I beviset bytter du som regel ut en del av en optimal løsning med en bedre løsning på delinstansen. Da blir hele løsningen bedre, men den var optimal.

Korteste vei har optimal delstruktur. Går en korteste vei fra 1 til 4 innom 2, er delen fra 1 til 2 en korteste vei, ellers kunne den byttes ut med en kortere. Lengste enkle vei har ikke optimal delstruktur. Ta en firkant med kantene 1–2, 2–4, 4–3 og 3–1. En lengste enkel vei fra 1 til 4 er 1, 2, 4, men delen fra 1 til 2 er ingen lengste enkel vei, for 1, 3, 4, 2 er lengre. De lengste enkle veiene fra 1 til 2 og fra 2 til 4 er 1, 3, 4, 2 og 2, 1, 3, 4, og satt sammen besøker de 1, 3 og 4 to ganger. De to delene konkurrerer om de samme nodene, og en node den ene bruker, kan ikke den andre bruke. Ingen kjenner en effektiv algoritme for lengste enkle vei.

Dynamisk programmering trenger begge egenskapene: optimal delstruktur for at dekomponeringen skal gi riktig svar, og overlappende delinstanser for at det skal lønne seg å lagre delsvarene.

Læreboka gir en oppskrift i fire trinn, og stavkapping gikk gjennom alle fire.

1. Struktur

   Beskriv hvordan en optimal løsning er bygd opp, og hvilket valg som deler den i delinstanser som selv må løses optimalt. For stavkapping er valget lengden $i$ på den første biten, og resten er en stav med lengde $n - i$.

2. Rekurrens

   Definer verdien av en optimal løsning rekursivt, med grunntilfeller. For stavkapping er rekurrensen $r_0 = 0$ og $r_n = \max_{1 \le i \le n} (p_i + r_{n-i})$.

3. Verdi

   Regn ut verdien, med memoisering eller nedenfra og opp. Memoized-Cut-Rod og Bottom-Up-Cut-Rod fyller begge $r$ i $\Theta(n^2)$.

4. Løsning

   Lagre valgene underveis, og les løsningen av bakfra. Bottom-Up-Cut-Rod lagrer den første biten i $s[j]$, og kappingen leses av fra $s[n]$.

Lengste felles delsekvens

En delsekvens får du ved å stryke null eller flere elementer fra en sekvens og beholde rekkefølgen på resten. «baker» er en delsekvens av både «bakverk» og «basker», og ingen lengre felles delsekvens finnes. Problemet LCS er å finne en lengste felles delsekvens av $X = \langle x_1, \ldots, x_m \rangle$ og $Y = \langle y_1, \ldots, y_n \rangle$. LCS er grunnlaget for blant annet diff og for sammenligning av DNA-sekvenser. $X$ har $2^m$ delsekvenser, så å prøve alle er uaktuelt.

Delinstansene er prefikser, $X_i = \langle x_1, \ldots, x_i \rangle$ og $Y_j$, og du dekomponerer ved å se på de siste elementene. La $Z$ være en LCS av $X_i$ og $Y_j$. Er $x_i = y_j$, må $Z$ slutte på dette elementet, for ellers kunne du lagt det til bakerst og fått en lengre felles delsekvens. Resten av $Z$ er da en felles delsekvens av $X_{i-1}$ og $Y_{j-1}$, og den er en lengste, for ellers kunne du byttet den ut og fått en lengre $Z$. Er $x_i \ne y_j$, kan ikke det siste elementet i $Z$ være lik begge, så $Z$ er en felles delsekvens av $X_{i-1}$ og $Y_j$ eller av $X_i$ og $Y_{j-1}$. Du løser begge delinstansene og tar den beste. Med $c[i, j]$ som lengden av en LCS av $X_i$ og $Y_j$:

Delinstansene overlapper, for både $c[i-1, j]$ og $c[i, j-1]$ bygger på $c[i-1, j-1]$. Delinstansgrafen er et rutenett med $(m+1)(n+1)$ noder, der hver celle bygger på cellen over, cellen til venstre og cellen diagonalt over til venstre. Rad for rad fra venstre er derfor en topologisk rekkefølge.

LCS-Length fyller tabellen $c$ i den rekkefølgen og lagrer valget i $b$ som en pil mot cellen svaret kom fra. Print-LCS følger pilene bakfra fra $b[m, n]$ og skriver ut $x_i$ for hver diagonal pil. Den skriver etter det rekursive kallet, så bokstavene kommer forfra selv om pilene følges bakfra.

def lcs_length(X, Y):
  m, n = len(X), len(Y)
  c = [[0] * (n + 1) for _ in range(m + 1)]
  b = [[""] * (n + 1) for _ in range(m + 1)]
  for i in range(1, m + 1):
      for j in range(1, n + 1):
          if X[i - 1] == Y[j - 1]:  # x_i og y_j
              c[i][j] = c[i - 1][j - 1] + 1
              b[i][j] = "↖"
          elif c[i - 1][j] >= c[i][j - 1]:
              c[i][j] = c[i - 1][j]
              b[i][j] = "↑"
          else:
              c[i][j] = c[i][j - 1]
              b[i][j] = "←"
  return c, b

def print_lcs(b, X, i, j):
  if i == 0 or j == 0:
      return
  if b[i][j] == "↖":
      print_lcs(b, X, i - 1, j - 1)
      print(X[i - 1], end="")
  elif b[i][j] == "↑":
      print_lcs(b, X, i - 1, j)
  else:
      print_lcs(b, X, i, j - 1)

LCS-Length bruker konstant tid per celle, altså $\Theta(mn)$. Print-LCS tar høyst $m + n$ steg, for hvert kall minsker $i$ eller $j$ eller begge.

Det binære ryggsekkproblemet

Du har $n$ gjenstander, der gjenstand $i$ har verdi $v_i$ og vekt $w_i$, og en ryggsekk med kapasitet $W$, alle positive heltall. Velg gjenstander med størst mulig totalverdi og totalvekt høyst $W$. Hver gjenstand er med eller ikke med, og det er derfor problemet kalles binært.

Dekomponer på spørsmålet om gjenstand $n$ skal være med. Nei gir det samme problemet med gjenstandene $1, \ldots, n - 1$ og hele kapasiteten. Ja gir verdien $v_n$ pluss det beste med gjenstandene $1, \ldots, n - 1$ og kapasitet $W - w_n$, og er bare mulig hvis $w_n \le W$. Delinstansene trenger derfor to parametre: hvor mange gjenstander som er med i betraktningen, og hvor mye kapasitet som er igjen. Med $K[i, j]$ som den største verdien med gjenstandene $1, \ldots, i$ og kapasitet $j$:

Rad $i$ bygger bare på rad $i - 1$, så tabellen fylles rad for rad. Cellen som gir verdien med gjenstand $i$, ligger $w_i$ kolonner lenger til venstre, så kantene i delinstansgrafen avhenger av vektene. Valgene trenger ikke lagres for seg. Er $K[i, j] \ne K[i-1, j]$, var gjenstand $i$ med, for uten den er det beste $K[i-1, j]$. Da fortsetter du fra $K[i-1, j - w_i]$. Ellers fortsetter du fra $K[i-1, j]$.

def knapsack(v, w, W):  # gjenstand i har verdi v[i - 1] og vekt w[i - 1]
  n = len(v)
  K = [[0] * (W + 1) for _ in range(n + 1)]
  for i in range(1, n + 1):
      for j in range(W + 1):
          x = K[i - 1][j]
          if j < w[i - 1]:
              K[i][j] = x
          else:
              y = K[i - 1][j - w[i - 1]] + v[i - 1]
              K[i][j] = max(x, y)
  return K

def chosen(K, w, W):
  items, j = [], W
  for i in range(len(K) - 1, 0, -1):
      if K[i][j] != K[i - 1][j]:
          items.append(i)
          j = j - w[i - 1]
  return items

Tabellen har $(n + 1)(W + 1)$ celler med konstant arbeid per celle, så kjøretiden er $\Theta(nW)$. Det ser polynomisk ut, men er det ikke som funksjon av inputstørrelsen, som måles i bits. Tallet $W$ tar bare $m = \lfloor \lg W \rfloor + 1$ bits å skrive, så $W$ vokser eksponentielt med plassen tallet tar:

Ett bit til i $W$ kan altså doble kjøretiden. En kjøretid som er polynomisk i et tall fra inputen, men ikke i antall bits, kalles pseudopolynomisk. Er $W$ begrenset av et polynom i $n$, er kjøretiden polynomisk. Med vilkårlig store heltall er ryggsekkproblemet NP-hardt, og ingen kjenner en algoritme som er polynomisk i antall bits.

Sjekk deg selv