dynamic-programming Zelfstudie
Aan de slag met dynamisch programmeren

Opmerkingen

Inleiding tot dynamisch programmeren

Dynamisch programmeren lost problemen op door de oplossingen voor subproblemen te combineren. Het kan analoog zijn aan de methode van delen en veroveren, waarbij het probleem wordt verdeeld in onsamenhangende subproblemen, subproblemen recursief worden opgelost en vervolgens worden gecombineerd om de oplossing van het oorspronkelijke probleem te vinden. Dynamische programmering is daarentegen van toepassing wanneer de subproblemen elkaar overlappen - dat wil zeggen wanneer subproblemen subproblemen delen. In deze context doet een verdeel-en-verover-algoritme meer werk dan nodig, en lost het herhaaldelijk de algemene subsubproblemen op. Een dynamisch programmeeralgoritme lost elk subsubprobleem slechts één keer op en slaat vervolgens het antwoord op in een tabel, waardoor het herberekenen van het antwoord wordt vermeden telkens wanneer het elk subsubprobleem oplost.

Laten we een voorbeeld bekijken. De Italiaanse wiskundige Leonardo Pisano Bigollo , die we gewoonlijk Fibonacci noemen, ontdekte een aantal reeksen door de geïdealiseerde groei van de konijnenpopulatie te overwegen. De serie is:

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

We kunnen opmerken dat elk getal na de eerste twee de som is van de twee voorgaande nummers. Laten we nu een functie F (n) formuleren die ons het negende Fibonacci-getal teruggeeft, wat betekent dat

F(n) = nth Fibonacci Number

Tot nu toe wisten we dat

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

We kunnen het generaliseren door:

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

Als we het nu als een recursieve functie willen schrijven, hebben we F(1) en F(2) als basisscenario. Dus onze Fibonacci-functie zou zijn:

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)

Als we nu F(6) aanroepen, wordt F(5) en F(4) aangeroepen, wat nog meer aanroept. Laten we dit grafisch weergeven:

Op de foto kunnen we zien dat F(6) F(5) en F(4) . Nu F(5) zullen noemen F(4) en F(3) . Na het berekenen van F(5) kunnen we zeker zeggen dat alle functies die werden aangeroepen door F(5) al zijn berekend. Dat betekent dat we F(4) al hebben berekend. Maar we berekenen opnieuw F(4) zoals het juiste kind van F(6) aangeeft. Moeten we echt herberekenen? Wat we kunnen doen, is dat we, zodra we de waarde van F(4) hebben berekend, deze opslaan in een array met de naam dp en deze opnieuw gebruiken wanneer dat nodig is. We initialiseren onze dp- array met -1 (of een waarde die niet in onze berekening komt). Dan zullen we F (6) noemen , waar onze gemodificeerde F (n) eruit zal zien:

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

We hebben dezelfde taak als voorheen uitgevoerd, maar met een eenvoudige optimalisatie. Dat wil zeggen dat we memo- techniek hebben gebruikt. In eerste instantie zullen alle waarden van dp array -1 zijn . Wanneer F(4) wordt opgeroepen, controleren we of deze leeg is of niet. Als het -1 opslaat, zullen we de waarde berekenen en opslaan in dp [4] . Als het iets anders dan -1 opslaat, betekent dit dat we de waarde al hebben berekend. Dus we zullen gewoon de waarde teruggeven.

Deze eenvoudige optimalisatie met behulp van memoization wordt Dynamic Programming genoemd .

Een probleem kan worden opgelost met Dynamic Programming als het enkele kenmerken heeft. Dit zijn:

• deelproblemen:
  Een DP-probleem kan worden onderverdeeld in een of meer subproblemen. Bijvoorbeeld: F(4) kan worden onderverdeeld in kleinere subproblemen F(3) en F(2) . Omdat de subproblemen vergelijkbaar zijn met ons hoofdprobleem, kunnen deze met dezelfde techniek worden opgelost.
• Overlappende subproblemen:
  Een DP-probleem moet overlappende subproblemen hebben. Dat betekent dat er een gemeenschappelijk onderdeel moet zijn waarvoor dezelfde functie meer dan eens wordt aangeroepen. Bijvoorbeeld: F(5) en F(6) hebben F(3) en F(4) gemeenschappelijk. Dit is de reden dat we de waarden in onze array hebben opgeslagen.

• Optimale onderstructuur:
  Stel dat u wordt gevraagd om de functie g(x) te minimaliseren. Je weet dat de waarde van g(x) afhankelijk is van g(y) en g(z) . Als we nu g(x) kunnen minimaliseren door zowel g(y) als g(z) minimaliseren, kunnen we alleen zeggen dat het probleem een optimale substructuur heeft. Als g(x) wordt geminimaliseerd door alleen g(y) minimaliseren en als het minimaliseren of maximaliseren van g(z) geen effect heeft op g(x) , dan heeft dit probleem geen optimale substructuur. In eenvoudige woorden, als een optimale oplossing van een probleem kan worden gevonden in de optimale oplossing van het subprobleem, dan kunnen we zeggen dat het probleem een optimale substructuur bezit.

Inzicht in status in dynamisch programmeren

Laten we bespreken met een voorbeeld. Uit n items, op hoeveel manieren kunt u r items kiezen? Je weet dat het wordt aangegeven door . Denk nu aan een enkel item.

• Als u het item niet selecteert, moet u daarna r items nemen van de resterende n-1 items, die wordt gegeven door .
• Als u het item selecteert, moet u daarna r-1 items nemen van de resterende n-1 items, die wordt gegeven door .

De samenvatting van deze twee geeft ons het totale aantal manieren. Dat is:

Als we denken dat nCr(n,r) een functie is die n en r als parameter neemt en bepaalt kunnen we de hierboven genoemde relatie schrijven als:

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

Dit is een recursieve relatie. Om het te beëindigen, moeten we basisscenario's bepalen. We weten dat, en . Met behulp van deze twee als basisgevallen, ons algoritme om te bepalen zal zijn:

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)

Als we de procedure grafisch bekijken, zien we dat sommige recursies meer dan eens worden aangeroepen. Bijvoorbeeld: als we n = 8 en r = 5 nemen , krijgen we:

We kunnen dit herhaalde gesprek vermijden door een array te gebruiken, dp . Omdat er 2 parameters zijn, hebben we een 2D-array nodig. We initialiseren de dp- array met -1 , waarbij -1 aangeeft dat de waarde nog niet is berekend. Onze procedure zal zijn:

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]

Om te bepalen , we hadden twee parameters n en r nodig . Deze parameters worden status genoemd . We kunnen eenvoudigweg afleiden dat het aantal toestanden het aantal dimensies van de dp- array bepaalt. De grootte van de array verandert afhankelijk van onze behoefte. Onze dynamische programmeeralgoritmen behouden het volgende algemene patroon:

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

Het bepalen van de staat is een van de meest cruciale onderdelen van dynamisch programmeren. Het bestaat uit het aantal parameters dat ons probleem definieert en het optimaliseren van hun berekening, we kunnen het hele probleem optimaliseren.

Een DP-oplossing construeren

Hoeveel problemen u ook oplost met Dynamic Programming (DP), het kan u nog steeds verrassen. Maar zoals al het andere in het leven, maakt oefening je beter. Met dit in gedachten, zullen we kijken naar het proces van het bouwen van een oplossing voor DP-problemen. Andere voorbeelden over dit onderwerp helpen u te begrijpen wat DP is en hoe het werkt. In dit voorbeeld proberen we te begrijpen hoe we helemaal opnieuw een DP-oplossing kunnen bedenken.

Iterative VS Recursief:
Er zijn twee technieken voor het construeren van een DP-oplossing. Zij zijn:

• Iteratief (for-cycles gebruiken)
• Recursief (met recursie)

Een algoritme voor het berekenen van de lengte van de langste gemene reeks van twee reeksen s1 en s2 ziet er bijvoorbeeld uit als:

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]

Dit is een iteratieve oplossing. Er zijn een paar redenen waarom het op deze manier wordt gecodeerd:

• Iteratie is sneller dan recursie.
• Het bepalen van tijd en ruimtecomplexiteit is eenvoudiger.
• Broncode is kort en schoon

Kijkend naar de broncode, kunt u gemakkelijk begrijpen hoe en waarom het werkt, maar het is moeilijk te begrijpen hoe u met deze oplossing kunt komen. De twee bovengenoemde benaderingen vertalen zich echter in twee verschillende pseudocodes. De ene maakt gebruik van iteratie (Bottom-Up) en een andere maakt gebruik van recursie (Top-Down). De laatste staat ook bekend als memo-techniek. De twee oplossingen zijn echter min of meer gelijkwaardig en de ene kan gemakkelijk in een andere worden omgezet. In dit voorbeeld laten we zien hoe u een recursieve oplossing voor een probleem kunt bedenken.

Voorbeeld probleem:
Laten we zeggen dat je N ( 1, 2, 3, ...., N ) wijnen naast elkaar op een plank hebt geplaatst. De prijs van ide wijn p [i]. De prijs van de wijnen stijgt elk jaar. Stel dat dit jaar 1 is , op jaar y zal de prijs van de i de wijn zijn: jaar * prijs van de wijn = y * p [i] . U wilt de wijnen die u heeft verkopen, maar u moet vanaf dit jaar precies één wijn per jaar verkopen. Nogmaals, je mag elk jaar alleen de meest linkse of meest rechtse wijn verkopen en je kunt de wijnen niet herschikken, wat betekent dat ze in dezelfde volgorde moeten blijven als in het begin.

Bijvoorbeeld: laten we zeggen dat je 4 wijnen op de plank hebt, en hun prijzen zijn (van links naar rechts):

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

De optimale oplossing zou zijn om de wijnen in de volgorde 1 -> 4 -> 3 -> 2 te verkopen, wat ons een totale winst oplevert van:

Hebzuchtige aanpak:
Na een tijdje brainstormen kun je misschien de oplossing bedenken om de dure wijn zo laat mogelijk te verkopen. Dus je hebzuchtige strategie zal zijn:

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

Hoewel de strategie niet vermeldt wat te doen wanneer de twee wijnen hetzelfde kosten, voelt de strategie nogal goed. Maar helaas is dat niet zo. Als de prijzen van de wijnen zijn:

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

De hebzuchtige strategie zou ze verkopen in de volgorde 1 -> 2 -> 5 -> 4 -> 3 voor een totale winst van:

Maar we kunnen het beter doen als we de wijnen verkopen in de volgorde 1 -> 5 -> 4 -> 2 -> 3 voor een totale winst van:

Dit voorbeeld moet u ervan overtuigen dat het probleem niet zo eenvoudig is als het op het eerste gezicht lijkt. Maar het kan worden opgelost met behulp van dynamische programmering.

terugkrabbelen:
Het is handig om met de memo-oplossing te komen voor een probleem bij het vinden van een backtrack-oplossing. Backtrack-oplossing evalueert alle geldige antwoorden voor het probleem en kiest de beste. Voor de meeste problemen is het gemakkelijker om met een dergelijke oplossing te komen. Er kunnen drie strategieën worden gevolgd bij het benaderen van een backtrack-oplossing:

1. het moet een functie zijn die het antwoord berekent met behulp van recursie.
2. het zou het antwoord met terugkeerverklaring moeten teruggeven.
3. alle niet-lokale variabelen moeten als alleen-lezen worden gebruikt, dwz dat de functie alleen lokale variabelen en zijn argumenten kan wijzigen.

Voor ons voorbeeldprobleem proberen we de meest linkse of meest rechtse wijn te verkopen en het antwoord recursief te berekenen en het betere te retourneren. De backtrack-oplossing ziet er als volgt uit:

// 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

Als we de procedure profitDetermination(1, 0, n-1) met profitDetermination(1, 0, n-1) , waarbij n het totale aantal wijnen is, wordt het antwoord geretourneerd.

Deze oplossing probeert eenvoudig alle mogelijke geldige combinaties van verkoop van de wijnen. Als er in het begin n wijnen zijn, wordt dit gecontroleerd mogelijkheden. Hoewel we nu het juiste antwoord krijgen, neemt de tijdcomplexiteit van het algoritme exponentieel toe.

De correct geschreven backtrack-functie moet altijd een antwoord zijn op een goed gestelde vraag. In ons voorbeeld is de procedure profitDetermination een antwoord op de vraag: wat is de beste winst die we kunnen behalen door de wijnen te verkopen met prijzen die zijn opgeslagen in de array p, wanneer het huidige jaar het jaar is en het interval van onverkochte wijnen loopt door [begin , einde], inclusief? Probeer altijd zo'n vraag voor je backtrackfunctie te maken om te zien of je het goed hebt en precies te begrijpen wat het doet.

Bepalende staat:
Status is het aantal parameters dat wordt gebruikt in de DP-oplossing. In deze stap moeten we nadenken over welke van de argumenten die u aan de functie doorgeeft overbodig zijn, dat wil zeggen dat we ze kunnen samenstellen uit de andere argumenten of we hebben ze helemaal niet nodig. Als er dergelijke argumenten zijn, hoeven we ze niet aan de functie door te geven, we berekenen ze binnen de functie.

In het voorbeeld functie profitDetermination hierboven, het argument year is overbodig. Het is gelijk aan het aantal wijnen dat we al hebben verkocht plus één. Het kan worden bepaald met behulp van het totale aantal wijnen vanaf het begin minus het aantal wijnen dat we niet hebben verkocht plus één. Als we het totale aantal wijnen n opslaan als een globale variabele, kunnen we de functie herschrijven als:

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])

We moeten ook nadenken over het bereik van mogelijke waarden van de parameters die kunnen worden verkregen uit een geldige invoer. In ons voorbeeld kan elk van de parameters begin en end waarden bevatten van 0 tot n-1 . Bij een geldige invoer verwachten we ook begin <= end + 1 . Er kunnen O(n²) verschillende argumenten zijn waarmee onze functie kan worden opgeroepen.

memoization:
We zijn nu bijna klaar. De backtrack-oplossing transformeren met tijdcomplexiteit in memo-oplossing met tijdcomplexiteit , zullen we een kleine truc gebruiken die niet veel moeite kost.

Zoals hierboven vermeld, zijn er alleen verschillende parameters waarmee onze functie kan worden opgeroepen. Met andere woorden, er zijn er alleen verschillende dingen die we daadwerkelijk kunnen berekenen. Dus waar doet tijd complexiteit komt uit en wat berekent het !!

Het antwoord is: de exponentiële tijdcomplexiteit komt van de herhaalde recursie en daarom berekent het steeds opnieuw dezelfde waarden. Als u de hierboven genoemde code uitvoert voor een willekeurige reeks van n = 20 wijnen en berekent hoe vaak de functie werd aangeroepen voor argumenten begin = 10 en einde = 10 , krijgt u een nummer 92378 . Dat is een enorme verspilling van tijd om hetzelfde antwoord zo vaak te berekenen. Wat we zouden kunnen doen om dit te verbeteren, is om de waarden op te slaan nadat we ze hebben berekend en elke keer dat de functie om een reeds berekende waarde vraagt, hoeven we niet de hele recursie opnieuw uit te voeren. We hebben een array dp [N] [N] , initialiseren deze met -1 (of een andere waarde die niet in onze berekening komt), waarbij -1 de waarde aangeeft die nog niet is berekend. De grootte van de matrix wordt bepaald door de maximaal mogelijke waarde van beginnen en eindigen we de overeenkomstige waarden zullen slaan van bepaalde begin- en eindwaarden in onze array. Onze procedure ziet er als volgt uit:

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]

Dit is onze vereiste DP-oplossing. Met onze zeer eenvoudige truc werkt de oplossing tijd, want die zijn er verschillende parameters waarmee onze functie kan worden opgeroepen en voor elk ervan werkt de functie slechts eenmaal met complexiteit.

zomerse:
Als u een probleem kunt identificeren dat met DP kan worden opgelost, voert u de volgende stappen uit om een DP-oplossing te maken:

• Maak een backtrackfunctie om het juiste antwoord te geven.
• Verwijder de overbodige argumenten.
• Schat en minimaliseer het maximale bereik van mogelijke waarden van functieparameters.
• Probeer de tijdcomplexiteit van één functieaanroep te optimaliseren.
• Sla de waarden op, zodat u deze niet twee keer hoeft te berekenen.

De complexiteit van een DP-oplossing is: bereik van mogelijke waarden de functie kan worden opgeroepen met * tijdcomplexiteit van elk gesprek .