Wat is het verschil tussen recursie, memoization & dynamisch programmeren?

Mogelijk duplicaat:
Dynamisch programmeren en memoriseren: top-down vs bottom-up nadert

Ik heb hier veel artikelen over gelezen, maar ik kan er geen vat op krijgen. Soms zien recursie en dynamische programmering er hetzelfde uit en dan weer memoization & dynamisch programmeren op elkaar lijken. Kan iemand mij uitleggen wat het verschil is?

P.S. Het zal ook nuttig zijn als je me op een code zou kunnen wijzen die de drie benaderingen van hetzelfde probleem gebruikt. (bijv. het Fibonacci-reeksprobleem, ik denk dat elk artikel dat ik las recursie gebruikte, maar het dynamisch programmeren noemde)


Antwoord 1, autoriteit 100%

Overweeg om de fibonacci-reeks te berekenen:

Pure recursie:

int fib(int x)
{
    if (x < 2)
        return 1;
    return fib(x-1) + fib(x-2);
}

resulteert in een exponentieel aantal oproepen.

Recursie met memoisatie/DP:

int fib(int x)
{
    static vector<int> cache(N, -1);
    int& result = cache[x];
    if (result == -1)
    {
        if (x < 2)
            result = 1;
        else
            result = fib(x-1) + fib(x-2);
    }
    return result;
}

Nu hebben we de eerste keer een lineair aantal oproepen en daarna constant.

De bovenstaande methode wordt “lui” genoemd. We berekenen de eerdere termen de eerste keer dat ze worden gevraagd.

Het volgende wordt ook als DP beschouwd, maar zonder recursie:

int fibresult[N];
void setup_fib()
{
    fibresult[0] = 1;
    fibresult[1] = 1;
    for (int i = 2; i < N; i++)
       fibresult[i] = fibresult[i-1] + fibresult[i-2];
}
int fib(int x) { return fibresult[x]; }

Op deze manier kan worden omschreven als “Eager”, “Preceren” of “iteratief”. Het is een sneller over het algemeen, maar we moeten de volgorde handmatig achterhalen waaraan de subproblemen moeten worden berekend. Dit is gemakkelijk voor Fibonacci, maar voor meer complexe DP-problemen wordt het moeilijker, en dus vallen we terug naar de luie recursieve methode als het snel is genoeg.

Ook het volgende is noch recursie noch dp:

int fib(int x)
{
    int a = 1;
    int b = 1;
    for (int i = 2; i < x; i++)
    {
        a = a + b;
        swap(a,b);
    }
    return b;
}

Het gebruikt constante ruimte en lineaire tijd.

Ook zal ik noemen voor de volledigheid Er is een gesloten vorm voor Fibonacci die Nether Recursion of DP gebruikt die ons in staat stelt om in constante tijd de Fibonacci-term te berekenen met behulp van een wiskundige formule op basis van de Gouden Ratio:

http://www.dreamincode.net/forums/topic / 115550-Fibonacci-gesloten formulier /


Antwoord 2, Autoriteit 57%

Wel, Recursie + memoisatie is precies een specifieke “smaak” van Dynamische programmering : dynamische programmering in overeenstemming met Top-down -benadering.

Om precies te zijn, er is geen vereiste om specifiek recursiete gebruiken. Elke verdeel & veroveren oplossing gecombineerd met memoization is top-down dynamische programmering. (Recursie is de LIFO-smaak van verdeel & heers, terwijl je ook FIFO verdeel & heers of een andere vorm van verdeel & heers kunt gebruiken).

Dus het is juister om te zeggen dat

divide & conquer + memoization == top-down dynamic programming

Ook vanuit een zeer formeel oogpunt, als u een verdeel & overwin oplossing voor een probleem dat geen repetitieve deeloplossingen genereert (wat betekent dat er geen voordeel is bij het onthouden), dan kun je beweren dat dit verdeel & veroveren-oplossing is een gedegenereerd voorbeeld van “dynamisch programmeren”.

dynamisch programmerenis echter een meer algemeen concept. Dynamisch programmeren kan een bottom-up benadering gebruiken, die verschilt van verdeel & veroveren+memoriseren.


Antwoord 3, autoriteit 23%

Ik weet zeker dat je een gedetailleerde definitie op internet kunt vinden. Hier is mijn poging om dingen te vereenvoudigen.

Recursie roept zichzelf weer op.

Dynamisch programmeren is een manier om problemen op te lossen die een specifieke structuur vertonen (optimale substructuur) waarbij een probleem kan worden opgesplitst in subproblemen die vergelijkbaar zijn met het oorspronkelijke probleem. Het is duidelijk dat men recursie kan inroepen om een DP op te lossen. Maar het is niet nodig. Men kan een DP oplossen zonder recursie.

Memoisatie is een manier om DP-algoritmen te optimaliseren die afhankelijk zijn van recursie. Het gaat er niet om het subprobleem dat al is opgelost opnieuw op te lossen. Je kunt het zien als een cache met oplossingen voor subproblemen.


Antwoord 4, autoriteit 12%

Het zijn verschillende concepten. Ze overlappen elkaar vrij vaak, maar ze zijn verschillend.

Recursie vindt plaats wanneer een functie zichzelf direct of indirect aanroept. Dit is alles.

Voorbeeld:

a -> call a
a -> call b, b -> call c, c -> call a

Dynamisch programmerenis wanneer je oplossingen gebruikt voor kleinere subproblemen om een groter probleem op te lossen. Dit is het gemakkelijkst recursief te implementeren, omdat je bij dergelijke oplossingen meestal denkt in termen van een recursieve functie. Een iteratieve implementatie heeft echter meestal de voorkeur, omdat het minder tijd en geheugen kost.

Memoisatie wordt gebruikt om te voorkomen dat recursieve DP-implementatie veel meer tijd kost dan nodig is. Meestal zal een DP-algoritme hetzelfde subprobleem gebruiken bij het oplossen van meerdere grote problemen. In een recursieve implementatie betekent dit dat we hetzelfde meerdere keren opnieuw zullen berekenen. Memoiseren houdt in dat de resultaten van deze deelproblemen in een tabel worden opgeslagen. Bij het invoeren van een recursieve aanroep controleren we of het resultaat in de tabel voorkomt: zo ja, dan geven we het terug, zo niet, dan berekenen we het, slaan het op in de tabel en retourneren het vervolgens.


Antwoord 5

Recursie heeft absoluut niets te maken met geheugenopslag en dynamisch programmeren; het is een volledig apart concept.

Anders is dit een dubbele vraag van: Dynamisch programmeren en memoriseren: bottom-up versus top-down benaderingen

Other episodes