algorithm
Programmazione dinamica
Ricerca…
introduzione
La programmazione dinamica è un concetto ampiamente utilizzato e viene spesso utilizzato per l'ottimizzazione. Si riferisce alla semplificazione di un problema complicato suddividendolo in sottoprocessi più semplici in modo ricorsivo, in genere approccio Bottom-up. Ci sono due attributi chiave che un problema deve avere affinché la programmazione dinamica sia applicabile "Sottostruttura ottimale" e "Sottosistemi sovrapposti". Per ottenere la sua ottimizzazione, la programmazione Dynamics utilizza un concetto chiamato Memorizzazione
Osservazioni
La programmazione dinamica è un miglioramento di Brute Force, vedi questo esempio per capire come si può ottenere una soluzione di programmazione dinamica da Brute Force.
Una soluzione di programmazione dinamica ha 2 requisiti principali:
Problemi sovrapposti
Sottostruttura ottimale
Sottoprogetti sovrapposti significa che i risultati di versioni più piccole del problema vengono riutilizzati più volte per arrivare alla soluzione del problema originale
Optimal Substructure significa che esiste un metodo per calcolare un problema dai suoi sottoproblemi.
Una soluzione di programmazione dinamica ha 2 componenti principali, lo stato e la transizione
Lo stato fa riferimento a un sottoproblema del problema originale.
La transizione è il metodo per risolvere un problema in base ai suoi sottoproblemi
Il tempo impiegato da una soluzione di programmazione dinamica può essere calcolato come No. of States * Transition Time . Quindi se una soluzione ha stati N^2 e la transizione è O(N) , allora la soluzione richiederebbe circa O(N^3) tempo.
Problema dello zaino
0-1 Zaino
Il Problema dello zaino è un problema quando viene dato un insieme di oggetti, ciascuno con un peso, un valore e esattamente 1 copia , determinare quale articolo (i) includere in una collezione in modo che il peso totale sia inferiore o uguale a un dato limite e il valore totale è il più ampio possibile.
Esempio C ++:
Implementazione :
int knapsack(vector<int> &value, vector<int> &weight, int N, int C){
int dp[C+1];
for (int i = 1; i <= C; ++i){
dp[i] = -100000000;
}
dp[0] = 0;
for (int i = 0; i < N; ++i){
for (int j = C; j >= weight[i]; --j){
dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
}
}
return dp[C];
}
Test :
3 5
5 2
2 1
3 2
Uscita :
3
Ciò significa che il valore massimo può essere raggiunto è 3, che si ottiene scegliendo (2,1) e (3,2).
Zaino illimitato
Il problema dello zaino non legato è un problema che, dato un insieme di elementi, ciascuno con un peso, un valore e copie infinite , determina il numero di ogni oggetto da includere in una collezione in modo che il peso totale sia inferiore o uguale a un dato limite e il valore totale è il più grande possibile.
Python (2.7.11) Esempio:
Implementazione :
def unbounded_knapsack(w, v, c): # weight, value and capactiy
m = [0]
for r in range(1, c+1):
val = m[r-1]
for i, wi in enumerate(w):
if wi > r:
continue
val = max(val, v[i] + m[r-wi])
m.append(val)
return m[c] # return the maximum value can be achieved
La complessità di tale implementazione è O(nC) , che n è il numero di elementi.
Test :
w = [2, 3, 4, 5, 6]
v = [2, 4, 6, 8, 9]
print unbounded_knapsack(w, v, 13)
Uscita :
20
Ciò significa che il valore massimo può essere raggiunto è 20, che si ottiene scegliendo (5, 8), (5, 8) e (3, 4).
Algoritmo di pianificazione del lavoro ponderato
Algoritmo di pianificazione dei lavori ponderati può anche essere indicato come algoritmo di selezione delle attività ponderate.
Il problema è che, dati determinati lavori con l'ora di inizio e l'ora di fine e un profitto che si ottiene quando si finisce il lavoro, qual è il profitto massimo che si può dare dato che non è possibile eseguire due lavori in parallelo?
Questo assomiglia ad Activity Selection usando Greedy Algorithm, ma c'è una svolta in più. Cioè, invece di massimizzare il numero di posti di lavoro finiti, ci concentriamo sulla realizzazione del massimo profitto. Il numero di lavori eseguiti non importa qui.
Diamo un'occhiata a un esempio:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | A | B | C | D | E | F |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (2,5) | (6,7) | (7,9) | (1,3) | (5,8) | (4,6) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 6 | 4 | 2 | 5 | 11 | 5 |
+-------------------------+---------+---------+---------+---------+---------+---------+
I lavori sono indicati con un nome, il loro inizio e fine e il profitto. Dopo alcune iterazioni, possiamo scoprire se eseguiamo Job-A e Job-E , possiamo ottenere il massimo profitto di 17. Ora come scoprirlo usando un algoritmo?
La prima cosa che facciamo è ordinare i lavori per il loro tempo di completamento in ordine decrescente. Perché lo facciamo? È perché se selezioniamo un lavoro che richiede meno tempo per terminare, lasciamo il maggior tempo per scegliere altri lavori. Abbiamo:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Avremo un array temporaneo aggiuntivo Acc_Prof di dimensione n (Qui, n indica il numero totale di lavori). Ciò conterrà il profitto massimo accumulato nell'esecuzione dei lavori. Non capisco? Aspetta e guarda. Inizializzeremo i valori dell'array con il profitto di ogni lavoro. Ciò significa che Acc_Prof [i] in un primo momento deterrà il profitto derivante dall'eseguire l' i-esimo lavoro.
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Ora denotiamo la posizione 2 con i , e la posizione 1 sarà denotata con j . La nostra strategia sarà quella di iterare j da 1 a i-1 e dopo ogni iterazione, noi incrementiamo i di 1, fino a quando i diventa n + 1.
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Controlliamo se Job [i] e Job [j] si sovrappongono, cioè se il tempo di fine di Job [j] è maggiore dell'ora di inizio di Job [i] , quindi questi due lavori non possono essere eseguiti insieme. Tuttavia, se non si sovrappongono, controlleremo se Acc_Prof [j] + Profitto [i]> Acc_Prof [i] . Se questo è il caso, aggiorneremo Acc_Prof [i] = Acc_Prof [j] + Profitto [i] . Questo è:
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
Qui Acc_Prof [j] + Profitto [i] rappresenta il profitto accumulato di questi due posti di lavoro. Controlliamolo per il nostro esempio:
Qui Job [j] si sovrappone a Job [i] . Quindi questi non possono essere fatti insieme. Poiché il nostro j è uguale a i-1 , incrementiamo il valore di i in i + 1 cioè 3 . E facciamo j = 1 .
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Ora Job [j] e Job [i] non si sovrappongono. L'importo totale del profitto che possiamo ottenere selezionando questi due lavori è: Acc_Prof [j] + Profitto [i] = 5 + 5 = 10 che è maggiore di Acc_Prof [i] . Quindi aggiorniamo Acc_Prof [i] = 10 . Aumentiamo anche j di 1. Otteniamo,
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Qui, Job [j] si sovrappone a Job [i] e j è anche uguale a i-1 . Quindi incrementiamo i di 1, e facciamo j = 1 . Noi abbiamo,
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Ora, Job [j] e Job [i] non si sovrappongono, otteniamo il profitto accumulato 5 + 4 = 9 , che è maggiore di Acc_Prof [i] . Aggiorniamo Acc_Prof [i] = 9 e incrementiamo j di 1.
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 9 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Ancora Job [j] e Job [i] non si sovrappongono. Il profitto accumulato è: 6 + 4 = 10 , che è maggiore di Acc_Prof [i] . Aggiorniamo nuovamente Acc_Prof [i] = 10 . Aumentiamo j di 1. Otteniamo:
j i
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 10 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Se continuiamo questo processo, dopo aver ripetuto l'intera tabella usando i , la nostra tabella sarà finalmente la seguente:
+-------------------------+---------+---------+---------+---------+---------+---------+
| Name | D | A | F | B | E | C |
+-------------------------+---------+---------+---------+---------+---------+---------+
|(Start Time, Finish Time)| (1,3) | (2,5) | (4,6) | (6,7) | (5,8) | (7,9) |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Profit | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 10 | 14 | 17 | 8 |
+-------------------------+---------+---------+---------+---------+---------+---------+
* Sono stati saltati alcuni passaggi per abbreviare il documento.
Se iteriamo attraverso l'array Acc_Prof , possiamo scoprire che il profitto massimo è 17 ! Lo pseudo-codice:
Procedure WeightedJobScheduling(Job)
sort Job according to finish time in non-decreasing order
for i -> 2 to n
for j -> 1 to i-1
if Job[j].finish_time <= Job[i].start_time
if Acc_Prof[j] + Profit[i] > Acc_Prof[i]
Acc_Prof[i] = Acc_Prof[j] + Profit[i]
endif
endif
endfor
endfor
maxProfit = 0
for i -> 1 to n
if maxProfit < Acc_Prof[i]
maxProfit = Acc_Prof[i]
return maxProfit
La complessità del popolamento dell'array Acc_Prof è O (n 2 ). L'array traversal prende O (n) . Quindi la complessità totale di questo algoritmo è O (n 2 ).
Ora, se vogliamo scoprire quali lavori sono stati eseguiti per ottenere il massimo profitto, dobbiamo attraversare la matrice in ordine inverso e se Acc_Prof corrisponde a maxProfit , invieremo il nome del lavoro in una pila e sottrai Profitto di quel lavoro da maxProfit . Lo faremo fino a maxProfit> 0 o raggiungiamo il punto iniziale dell'array Acc_Prof . Lo pseudo-codice sarà simile a:
Procedure FindingPerformedJobs(Job, Acc_Prof, maxProfit):
S = stack()
for i -> n down to 0 and maxProfit > 0
if maxProfit is equal to Acc_Prof[i]
S.push(Job[i].name
maxProfit = maxProfit - Job[i].profit
endif
endfor
La complessità di questa procedura è: O (n) .
Una cosa da ricordare, se ci sono più piani di lavoro che possono darci il massimo profitto, possiamo trovare solo un programma di lavoro tramite questa procedura.
Modifica distanza
L'affermazione del problema è come se venissero dati due string str1 e str2, quindi quanti numeri minimi di operazioni possono essere eseguiti sullo str1 che viene convertito in str2.
Implementazione in Java
public class EditDistance {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "march";
String str2 = "cart";
EditDistance ed = new EditDistance();
System.out.println(ed.getMinConversions(str1, str2));
}
public int getMinConversions(String str1, String str2){
int dp[][] = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
if(i==0)
dp[i][j] = j;
else if(j==0)
dp[i][j] = i;
else if(str1.charAt(i-1) == str2.charAt(j-1))
dp[i][j] = dp[i-1][j-1];
else{
dp[i][j] = 1 + Math.min(dp[i-1][j], Math.min(dp[i][j-1], dp[i-1][j-1]));
}
}
}
return dp[str1.length()][str2.length()];
}
}
Produzione
3
La più lunga successiva in comune
Se veniamo dati con le due stringhe, dobbiamo trovare la più lunga sotto-sequenza comune presente in entrambe.
Esempio
LCS per le sequenze di input "ABCDGH" e "AEDFHR" è "ADH" di lunghezza 3.
LCS per le sequenze di input "AGGTAB" e "GXTXAYB" è "GTAB" di lunghezza 4.
Implementazione in Java
public class LCS {
public static void main(String[] args) {
// TODO Auto-generated method stub
String str1 = "AGGTAB";
String str2 = "GXTXAYB";
LCS obj = new LCS();
System.out.println(obj.lcs(str1, str2, str1.length(), str2.length()));
System.out.println(obj.lcs2(str1, str2));
}
//Recursive function
public int lcs(String str1, String str2, int m, int n){
if(m==0 || n==0)
return 0;
if(str1.charAt(m-1) == str2.charAt(n-1))
return 1 + lcs(str1, str2, m-1, n-1);
else
return Math.max(lcs(str1, str2, m-1, n), lcs(str1, str2, m, n-1));
}
//Iterative function
public int lcs2(String str1, String str2){
int lcs[][] = new int[str1.length()+1][str2.length()+1];
for(int i=0;i<=str1.length();i++){
for(int j=0;j<=str2.length();j++){
if(i==0 || j== 0){
lcs[i][j] = 0;
}
else if(str1.charAt(i-1) == str2.charAt(j-1)){
lcs[i][j] = 1 + lcs[i-1][j-1];
}else{
lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
}
}
}
return lcs[str1.length()][str2.length()];
}
}
Produzione
4
Numero di Fibonacci
Approccio bottom-up per la stampa dell'ennesimo numero di Fibonacci mediante la programmazione dinamica.
Albero ricorsivo
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
/ \
fib(1) fib(0)
Sottosistemi sovrapposti
Qui fib (0), fib (1) e fib (3) sono i sottosistemi sovrapposti.fib (0) viene ripetuto 3 volte, fib (1) viene ripetuto 5 volte e fib (3) viene ripetuto 2 volte.
Implementazione
public int fib(int n){
int f[] = new int[n+1];
f[0]=0;f[1]=1;
for(int i=2;i<=n;i++){
f[i]=f[i-1]+f[i-2];
}
return f[n];
}
Complessità del tempo
Sopra)
La sottostringa comune più lunga
Con 2 string str1 e str2 dobbiamo trovare la lunghezza della più lunga sottostringa comune tra loro.
Esempi
Input: X = "abcdxyz", y = "xyzabcd" Output: 4
La sottostringa comune più lunga è "abcd" ed è di lunghezza 4.
Input: X = "zxabcdezy", y = "yzabcdezx" Output: 6
La sottostringa comune più lunga è "abcdez" ed è di lunghezza 6.
Implementazione in Java
public int getLongestCommonSubstring(String str1,String str2){
int arr[][] = new int[str2.length()+1][str1.length()+1];
int max = Integer.MIN_VALUE;
for(int i=1;i<=str2.length();i++){
for(int j=1;j<=str1.length();j++){
if(str1.charAt(j-1) == str2.charAt(i-1)){
arr[i][j] = arr[i-1][j-1]+1;
if(arr[i][j]>max)
max = arr[i][j];
}
else
arr[i][j] = 0;
}
}
return max;
}
Complessità del tempo
O (m * n)