Introduzione alla programmazione dinamica: sottoproblemi sovrapposti e sottostruttura ottimale

Pubblicato: 2021-02-08

Sommario

introduzione

Supponiamo di avere una domanda per risolvere il quadrato di 25. Se ci troviamo di fronte a questa domanda per la prima volta, possiamo risolverla a portata di mano o usando una calcolatrice. Ma se abbiamo già visto questa domanda prima o l'abbiamo già risolta, allora c'è la possibilità che possiamo rispondere rapidamente memorizzandola.

Questo ci porta alla conclusione che, se riusciamo a ricordarlo, possiamo saltarlo la prossima volta. La programmazione dinamica funziona su un concetto simile, l'idea è quella di ricordare il risultato di un calcolo e utilizzarlo in futuro, se necessario.

Questa semplice procedura di programmazione dinamica lo rende un'arma potente per un programmatore per vincere la battaglia del codice efficiente.

Ad esempio, supponiamo di avere una domanda complessa e di pensare sempre a una soluzione che divida la domanda in sottoproblemi. Ma potremmo rimanere bloccati in una situazione in cui calcoleremo un sottoproblema più volte. Lì utilizziamo la programmazione dinamica per una soluzione ottimale.

La programmazione dinamica ha due concetti:

Sottoproblemi sovrapposti
Sottostruttura ottimale

Sottoproblemi sovrapposti

Un classico esempio di comprensione del concetto di sottoproblema sovrapposto è un programma per stampare la serie di Fibonacci.

La logica della serie di Fibonacci è data da “fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)”. E l'esecuzione di questa funzione senza problemi può essere eseguita utilizzando una soluzione ricorsiva, con un caso base di fibonacci(0)=0 e fibonacci(1)=1.

public static int fibonacci(int n){
se (n== 0 || n== 1 )
ritorno n;
restituisce fibonacci(n -1 )+fibonacci(n -2 );
}
public static void main(String[] args){
System.out.print( “Il 4° numero di Fibonacci è “ +fibonacci( 4 ));
}

Supponiamo di dover stampare la 4a cifra di Fibonacci, quindi l'albero di ricorsione va come

fibonacci(4)

/ \

fibonacci(3) + fibonacci(2)

/ \ / \

fibonacci(2) + fibonacci(1) fibonacci(1) + fibonacci(0)

/ \

fibonacci(1) + fibonacci(0)

Si noti che fibonacci(4) è la quinta cifra nella serie di fibonacci perché partiamo da fibonacci(0). Nell'albero di ricorsione sopra, possiamo vedere che fibonacci(2) viene ripetuto due volte. Abbiamo osservato la duplicazione in un albero di ricorsione di altezza 4, ora immaginiamo di avere una chiamata ricorsiva di un numero enorme e, successivamente, ci sarà un albero di ricorsione con una grande altezza. E ci saranno molti di questi calcoli duplicati, noti come sottoproblemi sovrapposti.

Abbiamo due metodi per gestire questa (i) tabulazione, (ii) memorizzazione

Cerchiamo di capirli esaminando le loro implementazioni.

Memorizzazione

La risoluzione del problema di Fibonacci utilizzando il metodo di memorizzazione può essere eseguita come mostrato di seguito

promemoria int[] statico;
public static int fibonacci(int n){
if(memo[n]!=-1)
nota di ritorno[n];
se(n==0 || n==1){
promemoria[n]=n;
ritorno n;
}
memo[n] = fibonacci(n-1)+fibonacci(n-2);
nota di ritorno[n];
}
public static void main(String[] args){
memo=nuovo int[5];
for(int i=0;i<=4;i++)
memo[i]=-1;
System.out.println("Il quarto numero di Fibonacci è "+fibonacci(4));
}

Nel codice precedente, stiamo creando un file di registro di mantenimento o una tabella di ricerca e memorizzando i valori dei risultati calcolati. Poiché abbiamo memorizzato tutti i valori calcolati, possiamo utilizzarli in futuro se necessario, evitando così calcoli duplicati e sottoproblemi sovrapposti.

Tutta la logica è simile alla soluzione ricorsiva, ma l'unica differenza che abbiamo fatto è che li stiamo annotando nell'array memo prima di restituire il valore al metodo principale. L'unico vincolo a questo algoritmo è che abbiamo bisogno di uno spazio extra di dimensione O(n), ma stiamo ottimizzando la precedente soluzione ricorsiva.

Tabulazione

Questo metodo è leggermente diverso dalla soluzione precedente. La memorizzazione segue la stessa soluzione ricorsiva. Ma nella tabulazione, seguiamo una soluzione iterativa. Viene anche chiamato approccio dal basso verso l'alto. Esaminiamo l'attuazione dell'approccio bottom-up.

public static int fibonacci(int n){
int table[]=nuovo int[n+ 1 ];
for (int i= 0 ;i<=n;i++){
se (i== 0 || i== 1 )
tabella[i]=i;
altro {
tabella[i]=tabella[i -1 ]+tabella[i -2 ];
}
}
tabella di ritorno [n];
}
public static void main(String[] args){
System.out.println( “Il quarto numero di Fibonacci è “ +fibonacci( 4 ));
}

Poiché sappiamo che fibonacci(n)=fibonacci(n-1)+fibonacci(n-2), nella memorizzazione abbiamo iniziato con la chiamata di funzione fibonacci(4), e poi ci siamo resi conto che non ne abbiamo calcolato il valore, quindi abbiamo ho calcolato i suoi valori e poi li ho memorizzati.

Una situazione simile sarà affrontata da ulteriori chiamate ricorsive come fibonacci(3), fibonacci(2). Ora ciò fa attendere molte chiamate ricorsive nello stack di ricorsione, ma comunque stiamo saltando la duplicazione dei sottoproblemi sovrapposti.

Abbiamo anche un modo per calcolare Fibonacci da 0 all'n-esimo elemento in modo iterativo e quindi restituire l'n-esimo elemento di Fibonacci. Questo è ciò che abbiamo implementato nel codice sopra. Questo codice ha anche lo stesso requisito di spazio O(n).

Checkout: abilità per diventare uno sviluppatore full stack

Sottostruttura ottimale

In questo concetto, possiamo ottenere una soluzione ottima di un problema solo se abbiamo risolto in modo ottimale i suoi corrispondenti sottoproblemi.

E un classico esempio di questo concetto è considerare un attraversamento tra nodi in un grafo.

Assumiamo di avere radici multiple da Telangana a Delhi. E se abbiamo il percorso più breve che passa per Nagpur e Gwalior. Quindi il percorso più breve da Nagpur a Delhi Delhi deve passare attraverso Gwalior. Ora possiamo dividere il nostro problema in sottoproblemi che sono Telangana a Nagpur, Nagpur a Gwalior, Gwalior a Delhi.

E un classico esempio di questa proprietà è la sottosequenza comune più lunga in entrambe le stringhe. Una sottosequenza è diversa da una sottostringa. In una sottosequenza, i caratteri non devono necessariamente essere conseguenti nella stringa originale.

Quindi l'idea è di risolverlo risolvendo i suoi sottoproblemi in modo ottimale. Sia n la lunghezza della sottosequenza comune più lunga.

Se n=LCS(patata, tatuaggio), allora n=LCS(patata,tatuaggio)+1 (se gli ultimi caratteri sono gli stessi), altrimenti n=massimo(LCS(patata,tatuaggio), LCS(patata, tatuaggio).

static int lcs(String s1, String s2, int m, int n ){
int dp[][] = nuovo int[m+ 1 ][n+ 1 ];
for (int i= 0 ; i<=m; i++){
for (int j= 0 ; j<=n; j++){
se (io == 0 || j == 0 )
dp[i][j] = 0 ;
altrimenti se (s1.charAt(i -1 ) == s2.charAt(j -1 ))
dp[i][j] = dp[i -1 ][j -1 ]+ 1 ;
altro
dp[i][j] = Math.max(dp[i -1 ][j], dp[i][j -1 ]);
}
}
restituire dp[m][n];
}
public static void main(String[] args){
System.out.println( “la lunghezza della sottosequenza comune più lunga è “ +lcs( “patata” , “tatuaggio” , 6 , 6 ));
}

Nel codice precedente, abbiamo implementato la nostra logica utilizzando il metodo tabulazione e calcolato la lunghezza della sottosequenza comune più lunga presente in entrambe le stringhe.

Leggi anche: Stipendio per sviluppatori Full Stack in India

Impara i corsi di sviluppo software online dalle migliori università del mondo. Guadagna programmi Executive PG, programmi di certificazione avanzati o programmi di master per accelerare la tua carriera.

Conclusione

Ora che sei consapevole dell'utilizzo di una delle potenti tecniche per vincere la battaglia del codice efficiente, prova a implementare la programmazione dinamica per altri problemi e inizia a rafforzare la tua capacità di codificare una domanda usando la programmazione dinamica.

Per concludere, i corsi per sviluppatori Full Stack sono esperti altamente qualificati in grado di gestire tutto ciò che riguarda lo sviluppo web. Queste competenze di sviluppatore full stack sono ciò che li distingue dagli sviluppatori frontend e backend.

Cos'è la programmazione dinamica?

Un programma per computer contiene molto codice ripetitivo. Questo è inefficiente e può influire sulle sue prestazioni. In questo caso viene utilizzata la programmazione dinamica. La programmazione dinamica è un metodo per risolvere un problema complesso suddividendolo in sottoproblemi più semplici, risolvendo ciascuno di questi sottoproblemi una sola volta e memorizzandone le soluzioni utilizzando tabelle, che vengono poi ricercate ogni volta che si verifica un sottoproblema simile più avanti in la soluzione del complesso problema. Gli algoritmi di programmazione dinamica vengono utilizzati per risolvere vari tipi di problemi di ottimizzazione nei campi della ricerca operativa, della stima statistica, del riconoscimento di modelli, dell'intelligenza artificiale, dell'apprendimento automatico, della biologia computazionale e di altri campi.

Qual è il sottoproblema di sovrapposizione nella programmazione dinamica?

Il sottoproblema di sovrapposizione è un concetto utilizzato quando i sottoproblemi hanno soluzioni che vengono utilizzate anche in altri sottoproblemi. Questa sovrapposizione fa sì che la stessa sottoattività venga risolta più di una volta. Il problema è trovare un modo per risolvere il sottocompito solo una volta e utilizzare quella soluzione per ottenere le soluzioni di altri sottoproblemi. Gli algoritmi di programmazione dinamica risolvono questo problema utilizzando la memorizzazione. La memorizzazione è una tecnica in cui memorizziamo le soluzioni ai sottoproblemi in modo da non doverli risolvere di nuovo.

Qual è la sottostruttura ottimale nella programmazione dinamica?

La sottostruttura ottimale implica che la soluzione ottimale a un problema è correlata a una soluzione ottimale a un problema più piccolo all'interno della stessa definizione di problema. Una sottostruttura ottimale è un requisito aggiuntivo necessario per risolvere problemi o per dimostrare che non esiste una soluzione. Con una sottostruttura ottimale, possiamo provare molti problemi NP-hard. Un approccio generale per risolvere i problemi DP consiste nell'utilizzare la matrice di programmazione dinamica per memorizzare la soluzione ottimale dei sottoproblemi. La matrice di programmazione dinamica può essere utilizzata per risolvere qualsiasi problema DP di sottostruttura ottimale diverso da zero.