Till KTH:s startsida Till KTH:s startsida

Visa version

Version skapad av Viggo Kann 2016-09-15 22:13

Visa < föregående | nästa >
Jämför < föregående | nästa >

Dynamisk programmering 2.2

  • Frågan var:
    Vad är lämpliga dellösningar för en dynamiskprogrammeringsalgoritm för triangelstigsproblemet?

    a) V[i,j]=värdet på bästa stigen från toppen ner till elementet aij
    Dessa dellösningar fungerar för dynamisk programmering, men rekursionen blir ganska krånglig, eftersom den kommer att se olika ut för element inuti triangeln, på vänsterkanten och på högerkanten.
    b) V[i,j]=värdet på bästa stigen från toppen till botten som passerar elementet aij
    Detta fungerar inte som dellösningar eftersom det inte går att bygga en rekursion på dom.
    c
    ) V[i,j]=värdet på bästa stigen från elementet aij ner till botten
    Dessa dellösningar fungerar och ger en enkel rekursion, så c) är att föredra.
  • Nästa fråga gäller steg 2 för samma problem, där dellösningarna väljs som i c) ovan.
    Basfallen för rekursionen är V[n,j]=anj
    Rekursionssteget är V[i,j]=aij+ ???
    Vad är ???
    a) max(V[i-1,j], V[i-1,j+1])
    b) max(V[i,j-1], V[i,j+1])
    c) max(V[i+1,j], V[i+1,j+1])
  • Svaret visas i andra videon.