Wat is het verschil tussen memoriseren en dynamisch programmeren?

Wat is het verschil tussen memo’s en dynamisch programmeren? Ik denk dat dynamisch programmeren een onderdeel is van memoriseren. Klopt het?

Antwoord 1, autoriteit 100%

Relevant artikel over Programming.Guide: Dynamisch programmeren versus memoization versus tabulatie

Wat is het verschil tussen memo’s en dynamisch programmeren?

Memoisatieis een term die een optimalisatietechniek beschrijft waarbij u eerder berekende resultaten in de cache opslaat en het in de cache opgeslagen resultaat retourneert wanneer dezelfde berekening opnieuw nodig is.

Dynamisch programmerenis een techniek voor het iteratief oplossen van problemen van recursieve aard en is toepasbaar wanneer de berekeningen van de deelproblemen elkaar overlappen.

Dynamisch programmeren wordt typischgeïmplementeerd met behulp van tabulatie, maar kan ook worden geïmplementeerd met behulp van memorisatie. Dus zoals je kunt zien, is geen van beide een “subset” van de andere.

Een redelijke vervolgvraag is: Wat is het verschil tussen tabulatie (de typische dynamische programmeertechniek) en memorisatie?

Als je een dynamisch programmeerprobleem oplost met behulp van tabulatie, los je het probleem “van onderaf” op, dwz door eerst alle gerelateerde subproblemen op te lossen, meestal door een n-dimensionale tabel. Op basis van de resultaten in de tabel wordt vervolgens de oplossing voor het “top” / oorspronkelijke probleem berekend.

Als u memo’s gebruikt om het probleem op te lossen, doet u dit door een kaart bij te houden van reeds opgeloste subproblemen. Je doet het “van boven naar beneden” in de zin dat je eerst het “top” probleem oplost (wat meestal terugkomt om de subproblemen op te lossen).

Een goede dia van hier(link is nu dood, dia is echter nog steeds goed):

• Als alle subproblemen minstens één keer moeten worden opgelost, presteert een dynamisch-programmeeralgoritme van onderaf meestal met een constante factor beter dan een van bovenaf gememoriseerd algoritme
  • Geen overhead voor recursie en minder overhead voor het onderhouden van de tabel
  • Er zijn enkele problemen waarvoor het reguliere patroon van tabeltoegangen in het dynamisch-programmeeralgoritme kan worden misbruikt om de tijd- of ruimtevereisten nog verder te verminderen
• Als sommige subproblemen in de subprobleemruimte helemaal niet hoeven te worden opgelost, heeft de gememoriseerde oplossing het voordeel dat alleen die subproblemen worden opgelost die absoluut nodig zijn

Aanvullende bronnen:

• Wikipedia: Memoization, Dynamisch programmeren
• Gerelateerde SO Q/A: Memoization of Tabulation-benadering voor dynamisch programmeren

Antwoord 2, autoriteit 11%

Dynamisch programmeren is een algoritmisch paradigma dat een gegeven oplost
complex probleem door het op te splitsen in deelproblemen en de resultaten op te slaan
van subproblemen om te voorkomen dat dezelfde resultaten opnieuw worden berekend.

http://www.geeksforgeeks.org/dynamic-programming-set-1 /

Memoisatie is een gemakkelijke methode om eerder opgeloste oplossingen te volgen (vaak geïmplementeerd als een hash-sleutelwaardepaar, in tegenstelling tot tabulatie die vaak is gebaseerd op arrays), zodat ze niet opnieuw worden berekend wanneer ze opnieuw worden aangetroffen. Het kan zowel bottom-up als top-down worden gebruikt.

Bekijk deze discussieover memoization versus tabulation.

Dynamisch programmeren is dus een methode om bepaalde soorten problemen op te lossen door recursierelaties/recursie op te lossen en eerder gevonden oplossingen op te slaan via tabulatie of memovorming. Memoiseren is een methode om oplossingen voor eerder opgeloste problemen bij te houden en kan worden gebruikt met elke functie die unieke deterministische oplossingen heeft voor een bepaalde reeks invoer.

Antwoord 3, autoriteit 5%

Zowel Memoization als Dynamic Programming lossen individuele subproblemen slechts één keer op.

Memoisatie maakt gebruik van recursie en werkt top-down, terwijl dynamisch programmeren in tegengestelde richting beweegt om het probleem bottom-up op te lossen.

Hieronder staat een interessante analogie –

Top-down– Eerst zeg je dat ik de wereld overneem. Hoe ga je dat doen? U zegt dat ik eerst Azië zal overnemen. Hoe ga je dat doen? Ik zal eerst India overnemen. Ik zal de Chief Minister van Delhi worden, enz. enz.

Bottom-up– Je zegt dat ik de CM van Delhi zal worden. Dan zal India overnemen, dan alle andere landen in Azië en uiteindelijk zal ik de wereld overnemen.

Antwoord 4, autoriteit 4%

Dynamisch programmeren wordt vaak Memoiseren genoemd!

1. Memoisatie is de top-down techniek (begin het gegeven probleem op te lossen door het op te splitsen) en dynamisch programmeren is een bottom-up techniek (begin met het oplossen van het triviale subprobleem, omhoog naar het gegeven probleem)

2. DP vindt de oplossing door uit te gaan van de basiscase(s) en zich een weg naar boven te banen.
   DP lost alle subproblemen op, omdat het het bottom-up doet

   In tegenstelling tot Memoization, dat alleen de benodigde subproblemen oplost

3. DP heeft het potentieel om exponentiële brute-force-oplossingen om te zetten in polynomiale algoritmen.

4. DP kan veel efficiënter zijn omdat het iteratief is

   Integendeel, Memoization moet betalen voor de (vaak aanzienlijke) overhead als gevolg van recursie.

Om het eenvoudiger te maken,
Memoization gebruikt de top-down-benadering om het probleem op te lossen, d.w.z. het begint met het kern (hoofd) probleem en verdeelt het vervolgens in subproblemen en lost deze subproblemen op dezelfde manier op. In deze benadering kan hetzelfde subprobleem meerdere keren voorkomen en meer CPU-cyclus verbruiken, waardoor de tijdcomplexiteit toeneemt. Terwijl bij dynamisch programmeren hetzelfde subprobleem niet meerdere keren zal worden opgelost, maar het eerdere resultaat zal worden gebruikt om de oplossing te optimaliseren.

Antwoord 5, autoriteit 2%

(1) Memoiseren en DP, conceptueel, is eigenlijk hetzelfde. Want: denk aan de definitie van DP: “overlappende deelproblemen” “en optimale onderbouw”. Memoization beschikt volledig over deze 2.

(2) Memoiseren is DP met het risico van stack overflow als de recursie diep is. DP bottom up heeft dit risico niet.

(3) Memorisatie heeft een hashtabel nodig. Dus extra ruimte en wat zoektijd.

Dus om de vraag te beantwoorden:

–Conceptueelbetekent (1) dat ze hetzelfde zijn.

-Rekening houdend met (2), als je echt wilt, is memoisatie een subset van DP, in die zin dat een probleem dat oplosbaar is door memorisatie, oplosbaar is door DP, maar een probleem dat oplosbaar is door DP mogelijk niet oplosbaar is door memorisatie (omdat het kan overlopen).

-Rekening houdend met (3) hebben ze kleine prestatieverschillen.

Antwoord 6, autoriteit 2%

Van wikipedia:

Memo’s

Bij computergebruik is geheugenopslag een optimalisatietechniek die voornamelijk wordt gebruikt
om computerprogramma’s te versnellen door functieaanroepen te laten voorkomen dat ze worden herhaald
de berekening van resultaten voor eerder verwerkte invoer.

Dynamisch programmeren

In wiskunde en informatica is dynamisch programmeren een methode
voor het oplossen van complexe problemen door ze op te splitsen in eenvoudiger
subproblemen.

Als we een probleem opsplitsen in kleinere/eenvoudigere subproblemen, komen we hetzelfde subprobleem vaak meer dan eens tegen – dus gebruiken we Memoization om resultaten van eerdere berekeningen op te slaan, zodat we ze niet hoeven te herhalen.

Dynamisch programmeren komt vaak voor in situaties waarin het zinvol is om memorisatie te gebruiken, maar u kunt beide technieken gebruiken zonder noodzakelijkerwijs de andere te gebruiken.

Antwoord 7

Ik wil graag een voorbeeld;

Probleem:

Je beklimt een trap. Het kost n stappen om de top te bereiken.

Je kunt elke keer 1 of 2 treden beklimmen. Op hoeveel verschillende manieren?
kun jij naar de top klimmen?

Recursie met memorisatie

Op deze manier snoeien we (een verwijdering van overtollig materiaal van een boom of struik) recursieboom met behulp van memo-array en verkleinen we de recursieboom tot nn.

public class Solution {
    public int climbStairs(int n) {
        int memo[] = new int[n + 1];
        return climb_Stairs(0, n, memo);
    }
    public int climb_Stairs(int i, int n, int memo[]) {
        if (i > n) {
            return 0;
        }
        if (i == n) {
            return 1;
        }
        if (memo[i] > 0) {
            return memo[i];
        }
        memo[i] = climb_Stairs(i + 1, n, memo) + climb_Stairs(i + 2, n, memo);
        return memo[i];
    }
}

Dynamisch programmeren

Zoals we kunnen zien, kan dit probleem worden opgedeeld in subproblemen en bevat het de optimale eigenschap van de substructuur, dat wil zeggen dat de optimale oplossing efficiënt kan worden geconstrueerd uit optimale oplossingen van zijn subproblemen. We kunnen dynamisch programmeren gebruiken om dit probleem op te lossen.

>

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

Voorbeelden van https://leetcode.com/problems/climbing-stairs/

Antwoord 8

Denk maar aan twee manieren,

1. We splitsen het grotere probleem op in kleinere subproblemen – Top-down benadering.
2. We beginnen bij het kleinste subprobleem en bereiken het grotere probleem – Bottom-up benadering.

In memoisatie We gaan met (1.) waar we elke functie-oproep in een cache opslaan en vanaf daar bellen. Het is een beetje duur omdat het recursieve oproepen betreft.

In Dynamic Programming We gaan met (2.) waar we een tafel onderhouden, bottom-up door subproblemen op te lossen met behulp van de gegevens die in de tabel worden opgeslagen, vaak wordt aangeduid als de DP-tabel.

Opmerking:

• Beide zijn beide van toepassing op problemen met overlappende subproblemen.

• Memoisatie voert relatief slecht uit aan DP vanwege de overheadkosten die bij recursieve functie-oproepen worden betrokken.

• De asymptotische tijd-complexiteit blijft hetzelfde.

Antwoord 9

In Dynamic Programming ,

• Geen overhead voor recursie, minder overhead voor het handhaven van de tafel.
• Het reguliere patroon van de tabelapparaten kan worden gebruikt om de tijd- of ruimtevereisten te verkorten.

In memorisatie ,

• Sommige subproblemen hoeven niet op te lossen.