Care este diferența între memoization și programarea dinamică? Cred programare dinamică este un subset al memoization. Este corect?
care este diferența între memoization și programarea dinamică?
Memoization este un termen care descrie o tehnica de optimizare în cazul în care cache calculat anterior rezultate, și să se întoarcă în cache urmare, atunci când același calcul este nevoie din nou.
Programare dinamică este o tehnică pentru a rezolva probleme de natură recursivă, iterativ și este aplicabilă atunci când calcule ale subproblemelor se suprapun.
Programarea dinamică este de obicei implementat folosind intabulare, dar poate fi, de asemenea, puse în aplicare cu ajutorul memoization. Deci, după cum puteți vedea, nici unul nu este un "subset" de cealaltă.
Un rezonabile întrebare este: care este diferența între intabulare (tipic de programare dinamică tehnică) și memoization?
Atunci când a rezolva o problemă de programare dinamică folosind intabulare să rezolve problema "de jos în sus", și anume, de a rezolva toate legate de sub-probleme, în primul rând, de obicei, prin completarea unui n-dimensional masă. Pe baza rezultatelor din tabel, soluția la "sus" / original problemă este apoi calculat.
Dacă utilizați memoization pentru a rezolva problema ce face de către menținerea o hartă a rezolvat deja sub-probleme. Faci "de sus în jos", în sensul că puteți rezolva "sus" prima problemă (care de obicei recurses jos pentru a rezolva sub-probleme).
Un diapozitiv bun de la <grevă>aici (link-ul este acum mort, slide este încă bine, deși):
- Dacă toate subproblemelor trebuie să fie rezolvată de cel puțin o dată, de jos în sus, dinamic-algoritm de programare, de obicei, surclasează o de sus în jos memoized algoritm printr-un factor constant
- Nu deasupra capului pentru recursivitate și mai puțin deasupra capului pentru menținerea masa
- Există unele probleme pentru care model regulat de masa accesează în dinamică-algoritm de programare pot fi exploatate pentru a reduce timpul sau cerințele de spațiu și mai mult
- Dacă unele subproblemelor în subproblema spațiu nu trebuie să fie rezolvate la toate, memoized soluție are avantajul de a rezolva doar cei subproblemelor care sunt cu siguranta necesare
Resurse suplimentare:
Acest lucru a fost rescris ca un articol aici.
Programarea Dinamică este o algoritmica paradigme care rezolvă o anumită probleme complexe de rupere-l în subproblemelor și stochează rezultatele subproblemelor pentru a evita calcul aceleași rezultate, din nou.
http://www.geeksforgeeks.org/dynamic-programming-set-1/
Memoization este o metodă ușoară de a urmări anterior rezolvate soluții (de multe ori puse în aplicare ca un hash pereche valoare-cheie, spre deosebire de intabulare, care este de multe ori bazate pe tablouri), astfel încât acestea nu sunt't recalculate atunci când ei se întâlnesc din nou. Acesta poate fi folosit în atât de jos în sus sau de sus în jos de metode.
A se vedea acest discussion pe memoization vs intabulare.
Deci, programarea Dinamică este o metodă de a rezolva anumite clase de probleme prin rezolvarea relațiile de recurență/recursivitate și stocarea anterior găsit soluții, fie printr-intabulare sau memoization. Memoization este o metodă de a ține evidența soluțiilor anterior rezolvate probleme și poate fi folosit cu orice funcție care are unic deterministe soluții pentru un set dat de inputuri.
Programarea dinamică este adesea numit Memoization!
Memoization este de sus în jos tehnică(începe rezolvarea anumită problemă de rupere-l în jos) și de programare dinamică este un bottom-up tehnica(începe rezolvarea de banal sub-problemă, spre anumită problemă)
DP găsește soluția pornind de la cazul de bază(s) și își face drum în sus. DP rezolvă toate sub-probleme, pentru că o face de jos în sus
spre Deosebire de Memoization, care rezolvă doar nevoie de sub-probleme
DP are potențialul de a transforma exponențială în timp brute-force soluții în polinomului algoritmi de timp.
DP poate fi mult mai eficientă, deoarece ei iterativ
dimpotrivă, Memoization trebuie să plătească pentru (de multe ori semnificative) deasupra capului din cauza recursivitate.
Pentru a fi mai simplu, Memoization folosește abordare de sus în jos pentru a rezolva problema, adică se începe cu bază(principal) problema apoi se rupe în sub-probleme și de a rezolva aceste sub-probleme în mod similar. În această abordare același sub-problemă poate apărea de mai multe ori, si consuma mai mult CPU ciclu, prin urmare, crește complexitatea de timp. Întrucât în programare Dinamică același sub-problemă nu va fi rezolvată de mai multe ori, dar înainte rezultat va fi folosit pentru a optimiza soluția.
(1) Memoization și DP, din punct de vedere conceptual, este într-adevăr același lucru. Pentru că: ia în considerare definiția DP: "se suprapun subproblemelor" "și substructura optima". Memoization posedă pe deplin aceste 2.
(2) Memoization este DP cu riscul de stack overflow este recursivitate este profundă. DP jos în sus nu au acest risc.
(3) Memoization are nevoie de un tabel hash. Deci, spațiu suplimentar, iar unele de căutare timp.
Deci, pentru a răspunde la întrebarea:
-Din punct de vedere conceptual, (1) înseamnă că sunt același lucru.
-Având (2) în cont, dacă vrei cu adevărat, memoization este un subset al PD, în sensul că o problemă rezolvabilă prin memoization va fi rezolvabile prin DP, dar o problemă rezolvabilă prin DP-ar putea să nu fie rezolvabil de memoization (pentru că s-ar putea stack overflow).
-Lua (3) în cont, au diferențe minore de performanță.
De la wikipedia:
Memoization
În calcul, memoization este o tehnica de optimizare utilizate în principal pentru a accelera programele de calculator având funcția de apeluri evita repetarea calculul rezultatelor pentru anterior prelucrate intrări.
Programare Dinamică
În matematică și informatică, programare dinamică este o metodă pentru rezolvarea unor probleme complexe de rupere le în jos în simplu subproblemelor.
Atunci când încalci o problemă în mai mică/mai simplu subproblemelor, vom întâlni de multe ori același subproblema de mai multe ori - deci, vom folosi Memoization pentru a salva rezultate din calculele anterioare, astfel că nu ne't nevoie să le repete.
Programare dinamică întâlnește adesea situații în care este logic de a folosi memoization dar puteți folosi fie tehnica fără a fi necesar să utilizați alte.
Ambele Memoization și Programare Dinamică rezolvă individual subproblema doar o singură dată.
Memoization folosește recursivitate și funcționează de sus în jos, în timp ce de programare Dinamică se mișcă în direcția opusă rezolvarea problemei de jos în sus.
Mai jos este o analogie interesantă -
De sus în jos - în Primul rând vă spun că va lua peste tot în lume. Cum vei face asta? Vă spun că va prelua prima Asia. Cum vei face asta? Voi lua de-a lungul Indiei în primul rând. Eu va deveni Ministru de Delhi, etc. etc.
De jos în sus - Ți spun că va deveni CM din Delhi. Apoi va prelua India, apoi toate celelalte țări din Asia și în cele din urmă voi lua peste tot în lume.
Aș vrea să merg cu un exemplu;
Problema:
de a urca o scara caz. Este nevoie de n pași pentru a ajunge la partea de sus.
de Fiecare dată, puteți urca pe 1 sau 2 trepte. În câte moduri distincte puteți urca la partea de sus?
Recursivitate cu Memoization
În acest fel suntem în tăiere (o îndepărtarea excesului de material dintr-un copac sau arbust) recursivitate copac cu ajutorul memo matrice și reducerea dimensiunii de recursivitate copac pana la 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];
}
}
Programare Dinamică
După cum putem vedea această problemă poate fi rupt în subproblemelor, și conține optim infrastructura de proprietate, adică soluția optimă pot fi construite în mod eficient la soluțiile optime ale subproblemelor sale, ne putem folosi de programare dinamică pentru a rezolva această problemă.
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];
}
}
Exemple lua de la https://leetcode.com/problems/climbing-stairs/