dynamic-programming Handledning
Komma igång med dynamisk programmering

Anmärkningar

Introduktion till dynamisk programmering

Dynamisk programmering löser problem genom att kombinera lösningarna till delproblem. Det kan vara analogt med uppdelnings- och erövringsmetoden, där problemet är uppdelat i osammanhängande delproblem, delproblem löses rekursivt och kombineras sedan för att hitta lösningen på det ursprungliga problemet. Däremot gäller dynamisk programmering när delproblemen överlappar varandra, det vill säga när delproblem delar delproblem. I detta sammanhang gör en splittring-och-erövringsalgoritm mer arbete än nödvändigt, och upprepade gånger löser de vanliga underproblemen. En dynamisk programmeringsalgoritm löser varje delproblem bara en gång och sparar sedan sitt svar i en tabell, varigenom man undviker arbetet med att beräkna svaret varje gång det löser varje delproblem.

Låt oss titta på ett exempel. Den italienska matematikern Leonardo Pisano Bigollo , som vi vanligtvis känner som Fibonacci, upptäckte en nummerserie genom att ta hänsyn till den idealiserade tillväxten av kaninpopulationen . Serien är:

1, 1, 2, 3, 5, 8, 13, 21, ......

Vi kan märka att varje nummer efter de två första är summan av de två föregående siffrorna. Låt oss nu formulera en funktion F (n) som kommer att returnera oss det nionde Fibonacci-talet, det betyder,

F(n) = nth Fibonacci Number

Hittills har vi vetat det,

F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3

Vi kan generalisera det genom att:

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)

Om vi nu vill skriva det som en rekursiv funktion, har vi F(1) och F(2) som vårt grundfall. Så vår Fibonacci-funktion skulle vara:

Procedure F(n):                //A function to return nth Fibonacci Number
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
end if
Return F(n-1) + F(n-2)

Om vi nu kallar F(6) kommer det att ringa F(5) och F(4) , vilket kommer att ringa lite mer. Låt oss representera detta grafiskt:

Från bilden kan vi se att F(6) kommer att ringa F(5) och F(4) . Nu ringer F(5) F(4) och F(3) . Efter beräkning av F(5) kan vi säkert säga att alla funktioner som kallades av F(5) redan har beräknats. Det betyder att vi redan har beräknat F(4) . Men vi beräknar igen F(4) som F(6) rätt barn indikerar. Behöver vi verkligen omberäkna? Vad vi kan göra är att när vi har beräknat värdet på F(4) lagrar vi det i en matris med namnet dp och kommer att återanvända det vid behov. Vi initierar vår dp- matris med -1 (eller något värde som inte kommer med i vår beräkning). Då ringer vi F (6) där vår modifierade F (n) kommer att se ut:

Procedure F(n):
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
else if dp[n] is not equal to -1            //That means we have already calculated dp[n]
    Return dp[n]
else
    dp[n] = F(n-1) + F(n-2)
    Return dp[n]
end if

Vi har gjort samma uppgift som tidigare, men med en enkel optimering. Det vill säga, vi har använt memoiseringsteknik . Först kommer alla värden för dp- array att vara -1 . När F(4) kallas kontrollerar vi om den är tom eller inte. Om det lagrar -1 beräknar vi dess värde och lagrar det i dp [4] . Om det lagrar allt annat än -1 betyder det att vi redan har beräknat dess värde. Så vi returnerar helt enkelt värdet.

Denna enkla optimering med memoisering kallas Dynamic Programming .

Ett problem kan lösas med dynamisk programmering om det har några egenskaper. Dessa är:

• delproblem:
  Ett DP-problem kan delas in i ett eller flera delproblem. Till exempel: F(4) kan delas upp i mindre delproblem F(3) och F(2) . Eftersom delproblemen liknar vårt huvudproblem kan dessa lösas med samma teknik.
• Överlappande delproblem:
  Ett DP-problem måste ha överlappande delproblem. Det betyder att det måste finnas någon gemensam del för vilken samma funktion kallas mer än en gång. Till exempel: F(5) och F(6) har F(3) och F(4) gemensamt. Detta är anledningen till att vi lagrade värdena i vår grupp.

• Optimal substruktur:
  Låt oss säga att du uppmanas att minimera funktionen g(x) . Du vet att värdet på g(x) beror på g(y) och g(z) . Om vi nu kan minimera g(x) genom att minimera både g(y) och g(z) , kan vi bara säga att problemet har optimal understruktur. Om g(x) minimeras genom att bara minimera g(y) och om minimering eller maximering av g(z) inte har någon effekt på g(x) , har detta problem inte optimal understruktur. Med enkla ord, om optimal lösning av ett problem kan hittas från den optimala lösningen av dess delproblem, kan vi säga att problemet har optimal understrukturegenskap.

Förstå tillstånd i dynamisk programmering

Låt oss diskutera med ett exempel. Från n artiklar, på hur många sätt kan du välja r- objekt? Du vet att det är betecknat med . Tänk nu på en enda artikel.

• Om du inte väljer objektet måste du ta r- poster från återstående n-1- objekt, vilket ges av .
• Om du väljer objektet måste du ta r-1- objekt från återstående n-1- objekt, vilket ges av .

Sammanfattningen av dessa två ger oss det totala antalet sätt. Det är:

Om vi tänker nCr(n,r) som en funktion som tar n och r som parameter och bestämmer , kan vi skriva förhållandet som nämns ovan som:

nCr(n,r) = nCr(n-1,r) + nCr(n-1,r-1)

Detta är en rekursiv relation. För att avsluta det måste vi fastställa basfall (er). Vi vet det, och . Använda dessa två som basfall, vår algoritm att bestämma kommer vara:

Procedure nCr(n, r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
end if
Return nCr(n-1,r) + nCr(n-1,r-1)

Om vi tittar på förfarandet grafiskt kan vi se att några rekursioner kallas mer än en gång. Till exempel: om vi tar n = 8 och r = 5 , får vi:

Vi kan undvika detta upprepade samtal genom att använda en matris, dp . Eftersom det finns två parametrar behöver vi en 2D-grupp. Vi initierar dp- arrayen med -1 , där -1 anger att värdet inte har beräknats än. Vår procedur kommer att vara:

Procedure nCr(n,r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
else if dp[n][r] is not equal to -1        //The value has been calculated
    Return dp[n][r]
end if
dp[n][r] := nCr(n-1,r) + nCr(n-1,r-1)
Return dp[n][r]

Att bestämma , vi behövde två parametrar n och r . Dessa parametrar kallas tillstånd . Vi kan helt enkelt dra slutsatsen att antalet tillstånd bestämmer antalet dimensioner för dp- arrayen. Storleken på matrisen kommer att ändras efter vårt behov. Våra dynamiska programmeringsalgoritmer kommer att bibehålla följande allmänna mönster:

Procedure DP-Function(state_1, state_2, ...., state_n)
Return if reached any base case
Check array and Return if the value is already calculated.
Calculate the value recursively for this state
Save the value in the table and Return

Att bestämma tillstånd är en av de viktigaste delarna av dynamisk programmering. Det består av antalet parametrar som definierar vårt problem och optimerar deras beräkning, vi kan optimera hela problemet.

Konstruera en DP-lösning

Oavsett hur många problem du löser med dynamisk programmering (DP), kan det fortfarande överraska dig. Men som allt annat i livet gör övningen dig bättre. Med dessa i åtanke tittar vi på processen för att konstruera en lösning för DP-problem. Andra exempel på detta ämne hjälper dig att förstå vad DP är och hur det fungerar. I det här exemplet försöker vi förstå hur man kommer fram till en DP-lösning från början.

Iterativ VS rekursiv:
Det finns två tekniker för att konstruera DP-lösning. Dom är:

• Iterativ (med hjälp av cykler)
• Rekursiv (med rekursion)

Till exempel skulle algoritm för beräkning av längden på den längsta gemensamma efterföljden av två strängar s1 och s2 se ut:

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

Detta är en iterativ lösning. Det finns några orsaker till att den kodas på detta sätt:

• Iteration är snabbare än rekursion.
• Det är lättare att bestämma tid och rymdkomplexitet.
• Källkoden är kort och ren

Om du tittar på källkoden kan du enkelt förstå hur och varför den fungerar, men det är svårt att förstå hur man kommer fram till denna lösning. Men de två metoderna som nämns ovan översätter till två olika pseudokoder. En använder iteration (bottom-up) och en annan använder rekursion (Top-Down). Den senare är också känd som memoiseringsteknik. De två lösningarna är emellertid mer eller mindre ekvivalenta och en kan enkelt omvandlas till en annan. I det här exemplet visar vi hur man kan komma på en rekursiv lösning för ett problem.

Exempel Problem:
Låt oss säga att ni har N ( 1, 2, 3, ...., N ) viner placerade bredvid varandra på en hylla. Priset på i: te vin är p [i]. Priset på vinerna ökar varje år. Anta att detta är år 1 , på år y kommer priset på det i vinet att vara: år * vinets pris = y * p [i] . Du vill sälja de viner du har, men du måste sälja exakt ett vin per år, från och med i år. Återigen, varje år får du sälja bara det vänstaste eller det högsta vinet och du kan inte ordna om vinerna, det betyder att de måste hålla sig i samma ordning som i början.

Till exempel: låt oss säga att du har fyra viner i hyllan och deras priser är (från vänster till höger):

+---+---+---+---+
| 1 | 4 | 2 | 3 |
+---+---+---+---+

Den optimala lösningen skulle vara att sälja vinerna i ordningen 1 -> 4 -> 3 -> 2 , vilket ger oss en total vinst på:

Girig tillvägagångssätt:
Efter brainstorming ett tag kan du komma på lösningen att sälja det dyra vinet så sent som möjligt. Så din giriga strategi kommer att vara:

Every year, sell the cheaper of the two (leftmost and rightmost) available wines.

Även om strategin inte nämner vad man ska göra när de två vinerna kostar samma, känns strategin på rätt sätt. Men tyvärr är det inte. Om priserna på vinerna är:

+---+---+---+---+---+
| 2 | 3 | 5 | 1 | 4 |
+---+---+---+---+---+

Den giriga strategin skulle sälja dem i ordningen 1 -> 2 -> 5 -> 4 -> 3 för en total vinst på:

Men vi kan göra bättre om vi säljer vinerna i ordningen 1 -> 5 -> 4 -> 2 -> 3 för en total vinst på:

Detta exempel bör övertyga dig om att problemet inte är så enkelt som det ser ut vid första anblicken. Men det kan lösas med dynamisk programmering.

backtracking:
Att komma med memoiseringslösningen för ett problem att hitta en backtrack-lösning är praktiskt. Backtrack-lösningen utvärderar alla giltiga svar för problemet och väljer det bästa. För de flesta av problemen är det lättare att hitta en sådan lösning. Det kan finnas tre strategier att följa när man närmar sig en backtrack-lösning:

1. det bör vara en funktion som beräknar svaret med rekursion.
2. Det ska returnera svaret med retur uttalande.
3. alla icke-lokala variabler bör användas som skrivskyddad, dvs. funktionen kan endast ändra lokala variabler och dess argument.

För vårt exempelproblem försöker vi sälja vinet längst till vänster eller längst till höger och beräkna rekursivt svaret och returnera det bättre. Backtrack-lösningen skulle se ut:

// year represents the current year
// [begin, end] represents the interval of the unsold wines on the shelf
Procedure profitDetermination(year, begin, end):
if begin > end                  //there are no more wines left on the shelf
    Return 0
Return max(profitDetermination(year+1, begin+1, end) + year * p[begin], //selling the leftmost item
           profitDetermination(year+1, begin, end+1) + year * p[end])   //selling the rightmost item

Om vi kallar proceduren med profitDetermination(1, 0, n-1) , där n är det totala antalet viner, kommer det att returnera svaret.

Denna lösning försöker helt enkelt alla möjliga giltiga kombinationer av försäljning av vinerna. Om det finns n viner i början, kommer det att kontrolleras möjligheter. Även om vi får rätt svar nu växer algoritmens tidskomplexitet exponentiellt.

Den korrekt skrivna backtrackfunktionen ska alltid representera ett svar på en väl uttalad fråga. I vårt exempel representerar proceduren profitDetermination ett svar på frågan: Vad är den bästa vinsten vi kan få av att sälja vinerna med priser lagrade i matrisen p, när innevarande år är år och intervallet för osålda viner sträcker sig genom [börja , slut], inklusive? Du bör alltid försöka skapa en sådan fråga för din backtrack-funktion för att se om du har rätt och förstå exakt vad den gör.

Bestämma tillstånd:
Tillstånd är antalet parametrar som används i DP-lösningen. I det här steget måste vi tänka på vilka av de argument du skickar till funktionen är överflödig, dvs. vi kan konstruera dem utifrån de andra argumenten eller vi behöver inte dem alls. Om det finns några sådana argument behöver vi inte skicka dem till funktionen, vi beräknar dem inuti funktionen.

I exemplet funktionen profitDetermination visas ovan argumentet year är överflödig. Det motsvarar antalet viner vi redan har sålt plus ett. Det kan bestämmas med det totala antalet viner från början minus antalet viner vi inte har sålt plus ett. Om vi lagrar det totala antalet viner n som en global variabel kan vi skriva om funktionen som:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
year := n - (end-begin+1) + 1        //as described above
Return max(profitDetermination(begin+1, end) + year * p[begin],
           profitDetermination(begin, end+1) + year * p[end])

Vi måste också tänka på intervallet med möjliga värden på parametrarna kan få från en giltig input. I vårt exempel kan var och en av parametrarna begin och end innehålla värden från 0 till n-1 . I en giltig inmatning förväntar vi oss också att begin <= end + 1 . Det kan finnas O(n²) olika argument som vår funktion kan kallas med.

memoisation:
Vi är nu nästan klara. För att transformera backtrack-lösningen med tidskomplexitet till memoiseringslösning med tidskomplexitet , vi kommer att använda ett litet trick som inte kräver mycket ansträngning.

Som nämnts ovan finns det bara olika parametrar som vår funktion kan anropas med. Med andra ord finns det bara olika saker vi faktiskt kan beräkna. Så var gör tidskomplexitet kommer från och vad beräknar det !!

Svaret är: den exponentiella tidskomplexiteten kommer från den upprepade rekursionen och därför beräknar den samma värden om och om igen. Om du kör koden som nämns ovan för en godtycklig matris med n = 20 viner och beräknar hur många gånger den funktionen som krävdes för argument började = 10 och slut = 10 får du ett nummer 92378 . Det är ett enormt slöseri med tid att beräkna samma svar som många gånger. Vad vi kan göra för att förbättra detta är att lagra värdena när vi beräknar dem och varje gång funktionen ber om ett redan beräknat värde behöver vi inte köra hela rekursionen igen. Vi har en matris dp [N] [N] , initialiserar det med -1 (eller något värde som inte kommer med i vår beräkning), där -1 anger värdet som ännu inte har beräknats. Storleken på matrisen bestäms av det maximala möjliga värdet för början och slut eftersom vi lagrar motsvarande värden för vissa start- och slutvärden i vår grupp. Vår procedur skulle se ut:

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
if dp[begin][end] is not equal to -1                //Already calculated
    Return dp[begin][end]
year := n - (end-begin+1) + 1
dp[begin][end] := max(profitDetermination(year+1, begin+1, end) + year * p[begin],
           profitDetermination(year+1, begin, end+1) + year * p[end])
Return dp[begin][end]

Detta är vår obligatoriska DP-lösning. Med vårt mycket enkla trick kör lösningen tid, för det finns olika parametrar som vår funktion kan anropas med och för var och en av dem fungerar funktionen bara en gång med komplexitet.

Sommarlik:
Om du kan identifiera ett problem som kan lösas med DP använder du följande steg för att konstruera en DP-lösning:

• Skapa en backtrack-funktion för att ge rätt svar.
• Ta bort de överflödiga argumenten.
• Uppskatta och minimera det maximala intervallet för möjliga värden på funktionsparametrar.
• Försök att optimera tidskomplexiteten för ett funktionssamtal.
• Lagra värdena så att du inte behöver beräkna dem två gånger.

Komplexiteten hos en DP-lösning är: intervall med möjliga värden som funktionen kan kallas med * tidskomplexitet för varje samtal .