Introducere în programarea dinamică: subprobleme suprapuse și substructură optimă

Publicat: 2021-02-08

Cuprins

Introducere

Să presupunem că avem o întrebare pentru a rezolva pătratul lui 25. Dacă ne confruntăm cu această întrebare pentru prima dată, atunci o putem rezolva fie pe mână, fie folosind un calculator. Dar dacă am mai văzut această întrebare sau am rezolvat-o înainte, atunci există posibilitatea să răspundem rapid la ea memorând-o.

Acest lucru ne duce la concluzia că, dacă ne putem aminti, atunci îl putem sări peste data viitoare. Programarea dinamică funcționează pe un concept similar, ideea este de a reține rezultatul unui calcul și de a-l folosi în viitor, dacă este necesar.

Această procedură simplă de programare dinamică o face o armă puternică pentru un programator pentru a cuceri bătălia codului eficient.

De exemplu, să presupunem că avem o întrebare complexă și întotdeauna ne gândim la o soluție care împarte întrebarea în subprobleme. Dar este posibil să rămânem blocați într-o situație în care vom calcula o subproblemă de mai multe ori. Acolo folosim programarea dinamică pentru o soluție optimă.

Programarea dinamică are două concepte:

Subprobleme suprapuse
Substructură optimă

Subprobleme suprapuse

Un exemplu clasic de înțelegere a conceptului de subproblemă suprapusă este un program de tipărire a seriei Fibonacci.

Logica seriei Fibonacci este dată de „fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)”. Și executarea perfectă a acestei funcții se poate face folosind o soluție recursivă, cu un caz de bază de Fibonacci(0)=0 și Fibonacci(1)=1.

public static int Fibonacci(int n){
dacă (n== 0 || n== 1 )
întoarcere n;
returnează fibonacci(n -1 )+fibonacci(n -2 );
}
public static void main(String[] args){
System.out.print( „al patrulea număr Fibonacci este „ +fibonacci( 4 ));
}

Să presupunem că trebuie să tipărim a 4-a cifră Fibonacci, apoi arborele recursiv merge ca

Fibonacci(4)

/ \

Fibonacci(3) + Fibonacci(2)

/ \ / \

Fibonacci (2) + Fibonacci (1) Fibonacci (1) + Fibonacci (0)

/ \

Fibonacci(1) + Fibonacci(0)

Rețineți că Fibonacci(4) este a cincea cifră din seria Fibonacci, deoarece începem de la Fibonacci(0). În arborele recursiv de mai sus, putem vedea că Fibonacci(2) se repetă de două ori. Am observat o duplicare într-un arbore recursiv de înălțime 4, acum imaginați-vă că avem un apel recursiv de un număr mare și, ulterior, va exista un arbore recursiv cu o înălțime mare. Și vor exista multe astfel de calcule duplicate, care sunt cunoscute ca subprobleme suprapuse.

Avem două metode pentru a face față acestei (i)tabulare, (ii) memorare

Să le înțelegem trecând prin implementările lor.

Memorarea

Rezolvarea problemei Fibonacci folosind metoda memorizării se poate face după cum se arată mai jos

static int[] memo;
public static int Fibonacci(int n){
dacă(notă[n]!=-1)
retur memoriu[n];
dacă(n==0 || n==1){
memo[n]=n;
întoarcere n;
}
memo[n] = Fibonacci(n-1)+fibonacci(n-2);
retur memoriu[n];
}
public static void main(String[] args){
memo=new int[5];
for(int i=0;i<=4;i++)
memo[i]=-1;
System.out.println(„al patrulea număr Fibonacci este „+fibonacci(4));
}

În codul de mai sus, creăm un fișier jurnal de întreținere sau menținem un tabel de căutare și stocăm valorile rezultatelor calculate. Deoarece am memorat toate valorile calculate, le putem folosi în viitor dacă este necesar, evitând astfel calculele duplicate și subproblemele suprapuse.

Toată logica este similară cu soluția recursivă, dar singura diferență pe care am făcut-o este că le notăm în tabloul memo înainte de a returna valoarea metodei principale. Singura constrângere a acestui algoritm este că avem nevoie de un spațiu suplimentar de dimensiunea O(n), dar optimizăm soluția recursivă anterioară.

Intabulare

Această metodă este puțin diferită de soluția de mai sus. Memorizarea urmează aceeași soluție recursivă. Dar în tabulare, urmărim o soluție iterativă. Se mai numește și abordarea de jos în sus. Să ne uităm la implementarea abordării de jos în sus.

public static int Fibonacci(int n){
int table[]=new int[n+ 1 ];
pentru (int i= 0 ;i<=n;i++){
dacă (i== 0 || i== 1 )
tabel[i]=i;
else {
tabel[i]=tabel[i -1 ]+tabel[i -2 ];
}
}
tabel de returnare [n];
}
public static void main(String[] args){
System.out.println( „al patrulea număr Fibonacci este „ +fibonacci( 4 ));
}

Deoarece știm că fibonacci(n)=fibonacci(n-1)+fibonacci(n-2), în memorare am început cu apelul funcției fibonacci(4), apoi ne-am dat seama că nu i-am calculat valoarea, așa că am i-am calculat valorile și apoi l-am stocat.

O situație similară se va confrunta cu apeluri recursive ulterioare, cum ar fi Fibonacci(3), Fibonacci(2). Acum, asta face ca o mulțime de apeluri recursive să aștepte în stiva recursive, dar oricum omitem duplicarea subproblemelor care se suprapun.

Avem, de asemenea, o modalitate de a calcula Fibonacci de la 0 la al-lea element iterativ și apoi să returnăm al-lea element Fibonacci. Aceasta este ceea ce am implementat în codul de mai sus. Acest cod are, de asemenea, aceeași cerință de spațiu O(n).

Checkout: Abilități pentru a deveni un dezvoltator full stack

Substructură optimă

În acest concept, putem obține o soluție optimă a unei probleme numai dacă am rezolvat în mod optim subproblemele ei corespunzătoare.

Și un exemplu clasic al acestui concept este luarea în considerare a unei traversări între noduri dintr-un grafic.

Să presupunem că avem mai multe rădăcini de la Telangana la Delhi. Și dacă avem cel mai scurt traseu care trece prin Nagpur și Gwalior. Apoi, cea mai scurtă rută de la Nagpur la Delhi Delhi trebuie să treacă prin Gwalior. Acum ne putem împărți problema în subprobleme care sunt Telangana la Nagpur, Nagpur la Gwalior, Gwalior la Delhi.

Și un exemplu clasic pentru această proprietate este cea mai lungă subsecvență comună din ambele șiruri. O subsecvență este diferită de un subșir. Într-o succesiune, caracterele nu trebuie să fie consecutive în șirul original.

Deci ideea este să o rezolvi prin rezolvarea optimă a subproblemelor sale. Fie n lungimea celei mai lungi subsecvențe comune.

Dacă n=LCS(cartof, tatuaj), atunci n=LCS(cartof,tatuaj)+1 (dacă ultimele caractere sunt aceleași), altfel n=maximum(LCS(cartof,tatuaj), LCS(cartof, tatuaj).

static int lcs(String s1, String s2, int m, int n ){
int dp[][] = new int[m+ 1 ][n+ 1 ];
pentru (int i= 0 ; i<=m; i++){
pentru (int j= 0 ; j<=n; j++){
dacă (i == 0 || j == 0 )
dp[i][j] = 0 ;
else if (s1.charAt(i -1 ) == s2.charAt(j -1 ))
dp[i][j] = dp[i - 1 ][j - 1 ] +1 ;
altfel
dp[i][j] = Math.max(dp[i -1 ][j], dp[i][j -1 ]);
}
}
returnare dp[m][n];
}
public static void main(String[] args){
System.out.println( „lungimea celei mai lungi subsecvențe comune este „ +lcs( „cartof” , „tatuaj” , 6 , 6 ));
}

În codul de mai sus, am implementat logica noastră folosind metoda tabelării și am calculat lungimea celei mai lungi subsecvențe comune prezente în ambele șiruri.

Citiți și: Salariu Full Stack pentru dezvoltatori în India

Învață cursuri de dezvoltare software online de la cele mai bune universități din lume. Câștigă programe Executive PG, programe avansate de certificat sau programe de master pentru a-ți accelera cariera.

Concluzie

Acum că știți că folosiți una dintre tehnicile puternice pentru a cuceri bătălia codului eficient, încercați să implementați programarea dinamică pentru alte probleme și începeți să vă consolidați capacitatea de a codifica o întrebare folosind programarea dinamică.

În concluzie, cursurile pentru dezvoltatori Full Stack sunt experți cu înaltă calificare care se pot ocupa de tot ceea ce are legătură cu dezvoltarea web. Aceste abilități Full Stack Developer sunt ceea ce îi diferențiază de dezvoltatorii Frontend și Backend.

Ce este programarea dinamică?

Un program de calculator conține mult cod repetitiv. Acest lucru este ineficient și poate afecta performanța acestuia. În acest caz, se utilizează programarea dinamică. Programarea dinamică este o metodă de rezolvare a unei probleme complexe, împărțind-o în sub-probleme mai simple, rezolvând fiecare dintre aceste sub-probleme o singură dată și stocând soluțiile lor folosind tabele, care sunt apoi căutate ori de câte ori apare o sub-problemă similară mai târziu în cursul rezolvarea problemei complexe. Algoritmii de programare dinamică sunt utilizați pentru a rezolva diferite tipuri de probleme de optimizare în domeniile cercetării operaționale, estimării statistice, recunoașterii modelelor, inteligenței artificiale, învățării automate, biologiei computaționale și în alte domenii.

Care este subproblema de suprapunere în programarea dinamică?

Subproblema de suprapunere este un concept folosit atunci când subproblemele au soluții care sunt utilizate și în alte subprobleme. Această suprapunere face ca aceeași subsarcină să fie rezolvată de mai multe ori. Problema este să găsești o modalitate de a rezolva subsarcina o singură dată și să folosești acea soluție pentru a obține soluțiile altor subprobleme. Algoritmii de programare dinamică rezolvă această problemă folosind memorarea. Memorizarea este o tehnică prin care stocăm soluții la subprobleme, astfel încât să nu fie nevoie să le rezolvăm din nou.

Care este substructura optimă în programarea dinamică?

Substructura optimă implică faptul că soluția optimă a unei probleme este legată de o soluție optimă a unei probleme mai mici în cadrul aceleiași definiții de problemă. Substructura optimă este o cerință suplimentară necesară pentru a rezolva probleme sau pentru a demonstra că nu există o soluție. Cu o substructură optimă, putem demonstra multe probleme NP-hard. O abordare generală pentru rezolvarea problemelor DP este utilizarea matricei de programare dinamică pentru a stoca soluția optimă a subproblemelor. Matricea de programare dinamică poate fi utilizată pentru a rezolva orice probleme DP ale substructurii optime diferite de zero.