tdt4120

Forelesning 24. september - Dynamisk programmering

Læringsmål

• Forstå delproblemgrafer
• Forstå dynamisk programmering
• Forstå løsning ved memoisering (top-down)
• Forstå løsning ved iterasjon (bottom-up)
• Forstå hvordan man rekonstruerer en løsning fra lagrede beslutninger
• Forstå hva optimal delstruktur er
• Forstå hva overlappende delproblemer er
• FOrstå stavkutting og LCS
• Forstå løsningen på 0-1-ryggsekkproblemet (se appendisk D i pensumheftet)

1:5 Dekomponering

Dele problemet opp i mange delproblemer, løser vi delproblemene, kan vi løse hovedproblemet våres

function(A)
 S = divide(A)
 n = S.length
 let R[1...n] be a new array
  for i = 1 to n
   R[i] = function(S[i])
 return combine(R)

Optimal delstruktur

Det finnes en optimal løsning bestående av optimale delløsninger

Velfunderthet

Enhver avhengighetskjede ender med et grunntilfelle Unngå uendelig rekursjon Kan godt gå ‘oppover’ i det uendelige, men vi må ha et slags startpunkt for at det skal fungere Det samme holder for syklisk avhengighet.

• Dette beskriver velfunderte relasjoner
• Disse kan brukes til induksjon
• Eksemplene vi har brukt så langt:
• Naturlig induksjon: “er én mindre enn”
• Sterk induksjon: “er strengt mindre enn”
• Strukutrell induksjon, trær: “er barn av”

2:5 Dynamisk programmering -> Hva er det?

Oppskrift, Cormen et al.

1. Characterize the structure of an optimal solution
2. Recursively define the value of an optimal solution
3. Compute the value of an optimal solution
4. Construct an optimal solution from computed information

Oppskrift, Sniedovich

1. Embed your problem in a family of related problems
2. Derive a relationship between the solutions to these problems
3. Solve this relationship
4. Recover a solution to your problems from this relationship

Men er det ikke det vi har gjort til nå?

“Time-memory” tradeoff

Regner bare ut løsningen for et delproblem en gang.

Nyttig når vi har overlappende delproblemer Korrekt når vi har optimal substruktur

Memoisering

Gi funksjonen hukommelse: “Har jeg regnt ut dette problemet før?” Hvis ja: Returnér svaret du lagret sist!

function(A)
 if F[A] == nothing
   S = divide(A)
   n = S.length
   let R[1...n] be a new array
    for i = 1 to n
     R[i] = function(S[i])
   F[A] = combine(R)
 return F[A]

3:5 Eksempel: Stavkutting

Rod-cutting problem

Input: En lengde $n$ og priser $p$ for lengder $i = 1 … n$ Output: Lengder $l_1, ⋯ , l_k$ der summen av lengder $l_1 + ⋯ + l_k$ er $n$ og $r_n = p_l_1 + ⋯ + p_l_k$ totalprisen er maksimal

Sjekk ut LCS

5:5 Eksempel: Ryggsekk

Input: Verdier $v_1 ⋯ v_n$ vekter $w_1 ⋯ w_n$ og en kapasitet $W$. Output: Indekser $i_1 ⋯ i_k$ slik at $w_i_1 + ⋯ + w_i_k \leqslant W$

Dekomponeringen er så enkel at vi enten tar med objektet, eller ikke. Objekt $n$ bidrar med verdi $v_n$ Ser nå bare på objekter $1 \cdots n-1$ Objekt $n$ bruker opp $w_n$ av $W$

Lagrer alle delløsningene i en tabell på samme måte som før.

function knapsack(n, W)
 let k[0...n,0..W] be a new array
 for j = 0 to W
  k[o,j] = 0
 for i = 1 to n
   for j = 0 to W
    x = k[i - 1,j]
    if j w_i
     k[i,j] = x
    else
     y = k[i - 1, j - w_i] + v_i
     k[i,j] = max(x,y)