La de jos în sus abordare (pentru programare dinamică) constă în primul rând se uită la "mici" subproblemelor, și apoi rezolva mai mare subproblemelor folosind soluția la probleme mai mici.
Desus-jos** constă în rezolvarea problemei într-un "mod natural" și verificați dacă ați calculat soluția la subproblema înainte.
Am'm un pic confuz. Care este diferența între aceste două?
rev4: Un foarte elocvent comentariu de utilizator Sammaron a menționat că, probabil, acest răspuns anterior confuz de sus în jos și de jos în sus. În timp ce inițial acest răspuns (rev3) și alte răspunsuri spus că "de jos în sus este memoization" (" - și asume subproblemelor"), poate fi inversă (care este, "de sus în jos" poate " - și asume subproblemelor" și "de jos în sus" poate "compune subproblemelor"). Anterior, am citit pe memoization fiind un alt fel de programare dinamică, spre deosebire de un subtip de programare dinamică. Citam din acest punct de vedere, în ciuda nu vă abona la acesta. Am rescris acest răspuns să fie agnostic terminologiei până referințe pot fi găsite în literatura de specialitate. De asemenea, am transformat acest răspuns la o comunitate wiki. Vă rugăm să prefera surse academice. Lista de referințe: {Web: 1,2} {Literatură: 5}
Recapitulare
Programarea dinamică este tot despre comanda ta calcule într-un mod care evită recalcularea muncă duplicat. Ai o problemă principală (rădăcină de copac subproblemelor), și subproblemelor (subarbore). La subproblemelor de obicei se repetă și se suprapun. De exemplu, ia în considerare exemplul tău preferat de Fibonnaci. Acest lucru este plin de copac subproblemelor, dacă am făcut un naiv apel recursiv:
TOP of the tree
fib(4)
fib(3)...................... + fib(2)
fib(2)......... + fib(1) fib(1)........... + fib(0)
fib(1) + fib(0) fib(1) fib(1) fib(0)
fib(1) fib(0)
BOTTOM of the tree
Există cel puțin două principale tehnici de programare dinamică care nu sunt reciproc exclusive:
fib(100)
, te-ar suna acest lucru, și l-ar numi fib(100)=fib(99)+fib(98), care ar suna fib(99)=fib(98)+fib(97)
, ...etc..., care-ar numi fib(2)=fib(1)+fib(0)=1+0=1
. Atunci s-ar rezolva fib(3)=fib(2)+fib(1), dar nu't nevoie pentru a recalcula
fib(2)`, pentru că noi în cache-l. fib(2)
,fib(3)
,fib(4)
... caching fiecare valoare astfel încât să puteți calcula următorii cele mai ușor. Puteți, de asemenea, cred că de ea ca umple un tabel (o altă formă de caching). Memoization este foarte ușor de cod (în general, puteți scrie un "memoizer" adnotare sau funcția înveliș, care face în mod automat pentru tine), și ar trebui să fie prima linie de abordare. Dezavantajul de intabulare este că trebuie să vină cu o comanda.
(aceasta este de fapt doar ușor dacă scrieți funcția tine, și/sau de codificare într-un impur/non-funcționale limbaj de programare... de exemplu daca cineva deja a scris o precompilate fib
funcție, nu neapărat de face apeluri recursive la sine, și puteți't magic memoize funcția fără asigurarea acele apeluri recursive suna noul memoized funcție (și nu originalul unmemoized funcție))
Rețineți că ambele de sus în jos și de jos în sus pot fi implementate cu recursivitate sau iterativ de masă de umplere, deși nu poate fi natural.
Cu memoization, dacă pomul este foarte profundă (de exemplu, fib(10^6)
), va alerga afară de spațiu de stivă, pentru că fiecare întârziată de calcul trebuie să fie pus pe stiva, și veți avea 10^6 dintre ele.
Nici o abordare nu poate fi optimă dacă ordinea se întâmple (sau să încerce să) vizita subproblemelor nu este optimă, în special dacă există mai mult de un mod de a calcula o subproblema (în mod normal cache-ar rezolva asta, dar's posibil, teoretic, caching nu s-ar putea, în unele exotice cazuri). Memoization va adăuga, de obicei, pe timp de complexitate a spațiu-complexitate (de exemplu, cu totalizarea ai mai multă libertate de a arunca calcule, cum ar fi utilizarea de totalizare cu Fib vă permite să utilizați O(1) spațiu, dar memoization cu Fib folosește O(N) spațiu de stivă).
Aici avem lista de exemple de interes special, care nu sunt doar generale DP probleme, dar interesant distinge memoization și totalizarea voturilor. De exemplu, o formulare ar putea fi mult mai ușor decât celelalte, sau poate exista o optimizare care, practic, necesită intabulare:
De sus în jos și de jos în sus DP sunt două moduri diferite de a rezolva aceleași probleme. Ia în considerare o memoized (de sus în jos) vs dinamic (de jos în sus) soluție de programare pentru calcul numerele lui fibonacci.
fib_cache = {}
def memo_fib(n):
global fib_cache
if n == 0 or n == 1:
return 1
if n in fib_cache:
return fib_cache[n]
ret = memo_fib(n - 1) + memo_fib(n - 2)
fib_cache[n] = ret
return ret
def dp_fib(n):
partial_answers = [1, 1]
while len(partial_answers) <= n:
partial_answers.append(partial_answers[-1] + partial_answers[-2])
return partial_answers[n]
print memo_fib(5), dp_fib(5)
Mie personal mi se pare memoization mult mai natural. Puteți lua o funcție recursivă și memoize-l printr-un procedeu mecanic (prima căutare răspuns în cache-și reveni, dacă este posibil, în caz contrar calcula recursiv și apoi înainte de a se întoarce, salvați de calcul în cache pentru o utilizare viitoare), întrucât face de jos în sus de programare dinamică necesită vă pentru a codifica un ordin în care soluțiile sunt calculate, astfel că nici un "mare problemă" este calculată cea mai mică problemă de care depinde.
O caracteristică cheie de programare dinamică este prezența de suprapunerea subproblemelor. Care este problema cu care vă sunt încercarea de a rezolva poate fi rupt în subproblemelor, și mulți dintre cei subproblemelor împărtășească subsubproblems. Este ca "Divide și cuceri", dar ajungi să faci același lucru de multe, multe ori. Un exemplu pe care l-am folosit din 2003, atunci când predarea sau explicarea acestor aspecte: puteți calcula numere Fibonacci recursiv.
def fib(n):
if n < 2:
return n
return fib(n-1) + fib(n-2)
Utilizați dumneavoastră preferat limba și încercați să rulați-l pentru fib(50)
. Va dura foarte, foarte mult timp. Aproximativ la fel de mult timp ca fib(50)
în sine! Cu toate acestea, o mulțime de inutile locul de muncă se face. fib(50)
sun fib(49) " și " fib(48), dar apoi atât de cei care vor suna
fib(47), chiar daca valoarea este aceeași. În fapt, fib(47) va fi calculat de trei ori: de un apel direct la
fib(49), printr-un apel direct de la
fib(48), și, de asemenea, printr-un apel direct la un alt fib(48)
, cel care a fost generat de calcul de fib(49)
... Deci, veți vedea, ne-am suprapunerea subproblemelor.
Vești bune: nu este nevoie pentru a calcula aceeași valoare de mai multe ori. Odată ce ați calcula o dată, cache rezultatul, și data viitoare când utilizați cache valoare! Aceasta este esența de programare dinamică. Puteți să-l numesc "de sus în jos", "memoization", sau orice altceva vrei. Această abordare este foarte intuitiv și foarte ușor să pună în aplicare. Scrie doar o soluție recursivă în primul rând, testați-l pe teste mici, se adauga memoization (caching deja valorile calculate), și --- bingo! --- ai terminat.
De obicei, puteți scrie, de asemenea, un echivalent iterativ program care funcționează de jos în sus, fără recursivitate. În acest caz, acest lucru ar fi cel mai natural de abordare: bucla de la 1 la 50 de calcul toate numerele lui Fibonacci ca te duci.
fib[0] = 0
fib[1] = 1
for i in range(48):
fib[i+2] = fib[i] + fib[i+1]
În orice scenariu interesant bottom-up soluție este de obicei mai dificil de înțeles. Cu toate acestea, odată ce ați înțeles că, de obicei'd a obține o mult mai clară imagine mare de cum functioneaza algoritmul. În practică, atunci când rezolvarea trivial probleme, vă recomandăm în primul rând scris abordare de sus în jos și de testare-l pe mici exemple. Apoi scrie jos în sus soluție și compara cele două pentru a vă asigura că sunt obtinerea același lucru. Ideal ar fi să comparați cele două soluții automat. Scrie un mic rutină, care ar genera o mulțime de teste, în mod ideal - toate teste mici până la anumite dimensiuni --- și valida faptul că ambele soluții dea același rezultat. După care folosesc bottom-up soluție în producție, dar menține în partea de sus-de jos cod, comentate. Acest lucru va face mai ușor pentru alți dezvoltatori pentru a înțelege ceea ce este pe care o faci: de jos în sus, codul poate fi destul de neînțeles, chiar tu ai scris-o și chiar dacă știți exact ceea ce faci.
În multe aplicații abordarea de jos în sus este puțin mai repede, deoarece aeriene de apeluri recursive. Stack overflow poate fi, de asemenea, o problemă în anumite probleme, și rețineți că acest lucru poate depinde foarte mult de datele de intrare. În unele cazuri, este posibil să nu fi capabil de a scrie un test provoacă o depășire de stivă, dacă nu't înțeleg de programare dinamică destul de bine, dar într-o zi acest lucru se poate întâmpla în continuare.
Acum, există probleme în cazul în care partea de sus-în jos abordare este singura soluție fezabilă pentru că problema spațiului este atât de mare încât este imposibil de a rezolva toate subproblemelor. Cu toate acestea, "cache" încă mai funcționează în timp rezonabil pentru dvs. de intrare are nevoie doar de o fracțiune de subproblemelor pentru a fi rezolvate --- dar este prea dificil de a defini în mod explicit, care subproblemelor aveți nevoie pentru a rezolva, și, prin urmare, pentru a scrie un bottom-up soluție. Pe de altă parte, există situații când știi că va trebui să rezolve toate ** subproblemelor. În acest caz, du-te pe și de a folosi de jos în sus.
Personal, aș folosi de sus-jos pentru Punctul de optimizare a.k.o Word wrap problemă de optimizare (uită-te la Knuth-Plass linie de rupere algoritmi; cel puțin TeX folosește, și unele software-ul de Adobe Systems folosește o abordare similară). Mi-ar folosi de jos în sus pentru Fast Fourier Transform.
Vă permite să ia seria fibonacci ca un exemplu
1,1,2,3,5,8,13,21....
first number: 1
Second number: 1
Third Number: 2
Un alt mod de a pune problema,
Bottom(first) number: 1
Top (Eighth) number on the given sequence: 21
În caz de primele cinci numere fibonacci
Bottom(first) number :1
Top (fifth) number: 5
Acum, vă permite să ia o privire recursive seria Fibonacci algoritm ca un exemplu
public int rcursive(int n) {
if ((n == 1) || (n == 2)) {
return 1;
} else {
return rcursive(n - 1) + rcursive(n - 2);
}
}
Acum, dacă vom executa acest program cu următoarele comenzi
rcursive(5);
dacă ne-am strâns uite în algoritm, în scopul de a genera de-al cincilea număr este nevoie de 3 și 4 numere. Deci mi recursivitate, de fapt, începe de la partea de sus(5) și apoi merge tot drumul în jos/numere mai mici. Această abordare este, de fapt abordare de sus în jos.
Pentru a evita să fac aceleași calcule de mai multe ori, folosim Dinamic tehnici de Programare. Am stoca valoarea calculată anterior și refolosi. Această tehnică se numește memoization. Există mai mult pentru programare Dinamică atunci memoization care nu este necesar pentru a discuta despre problema actuală.
De Sus În Jos
Vă permite să rescrie algoritm original și adaugă memoized tehnici.
public int memoized(int n, int[] memo) {
if (n <= 2) {
return 1;
} else if (memo[n] != -1) {
return memo[n];
} else {
memo[n] = memoized(n - 1, memo) + memoized(n - 2, memo);
}
return memo[n];
}
Și vom executa această metodă ca următoarele
int n = 5;
int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
memoized(n, memo);
Această soluție este încă sus în jos ca algoritmul începe de la valoarea de sus și du-te în jos fiecare pas pentru a obține noastră valoare de top.
De Jos În Sus
Dar, întrebarea este, putem porni de jos, de la primul număr fibonacci apoi de mers pe drum in sus. Vă permite să rescrie cu ajutorul acestei tehnici,
public int dp(int n) {
int[] output = new int[n + 1];
output[1] = 1;
output[2] = 1;
for (int i = 3; i <= n; i++) {
output[i] = output[i - 1] + output[i - 2];
}
return output[n];
}
Acum, dacă ne uităm în acest algoritm este de fapt începe de la valori mai mici apoi du-te la partea de sus. Dacă am nevoie de 5-lea număr fibonacci sunt de fapt calcul 1, apoi a doua, apoi a treia tot drumul până la al 5-lea numar. Acest tehnici de fapt numit de jos în sus tehnici.
Ultimele două, algoritmi complet umple de programare dinamică a cerințelor. Dar una este de sus în jos și un altul este de jos în sus. Atât algoritmul are similar spațiu și timp complexitate.
Programarea dinamică este adesea numit Memoization!
1.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ă)
2.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.
Pur și simplu spune abordare de sus în jos foloseste recursivitate pentru chemarea Sub-probleme din nou și din nou
în cazul în care, ca abordare de jos în sus folosi singur, fără a sunat nici unul și, prin urmare, este mai eficient.
Următoarele este DP soluție bazată pe pentru a Edita Distanța problemă care este de sus în jos. Sper că va ajuta, de asemenea, în înțelegerea lumii de Programare Dinamică:
public int minDistance(String word1, String word2) {//Standard dynamic programming puzzle.
int m = word2.length();
int n = word1.length();
if(m == 0) // Cannot miss the corner cases !
return n;
if(n == 0)
return m;
int[][] DP = new int[n + 1][m + 1];
for(int j =1 ; j <= m; j++) {
DP[0][j] = j;
}
for(int i =1 ; i <= n; i++) {
DP[i][0] = i;
}
for(int i =1 ; i <= n; i++) {
for(int j =1 ; j <= m; j++) {
if(word1.charAt(i - 1) == word2.charAt(j - 1))
DP[i][j] = DP[i-1][j-1];
else
DP[i][j] = Math.min(Math.min(DP[i-1][j], DP[i][j-1]), DP[i-1][j-1]) + 1; // Main idea is this.
}
}
return DP[n][m];
}
Vă puteți gândi sale de implementare recursivă la casa ta. L's destul de bun și interesant, dacă te-ai't rezolvat ceva ca acest lucru înainte.