algorithm
Programmation dynamique
Recherche…
Introduction
La programmation dynamique est un concept largement utilisé et souvent utilisé pour l’optimisation. Il s'agit de simplifier un problème compliqué en le décomposant en sous-problèmes plus simples de manière récursive, généralement l'approche Bottom up. Il y a deux attributs clés qu'un problème doit avoir pour que la programmation dynamique soit applicable "Sous-structure optimale" et "Sous-problèmes chevauchants". Pour parvenir à son optimisation, la programmation dynamique utilise un concept appelé Mémorisation.
Remarques
La programmation dynamique est une amélioration de Brute Force. Voir cet exemple pour comprendre comment obtenir une solution de programmation dynamique de Brute Force.
Une solution de programmation dynamique a deux exigences principales:
Problèmes de chevauchement
Structure optimale
Les sous-problèmes qui se chevauchent signifient que les résultats des versions plus petites du problème sont réutilisés plusieurs fois pour arriver à la solution du problème initial
La sous-structure optimale signifie qu'il existe une méthode de calcul d'un problème à partir de ses sous-problèmes.
Une solution de programmation dynamique a 2 composants principaux, l' état et la transition
L’ État fait référence à un sous-problème du problème initial.
La transition est la méthode pour résoudre un problème basé sur ses sous-problèmes
Le temps pris par une solution de programmation dynamique peut être calculé en nombre No. of States * Transition Time . Ainsi, si une solution a N^2 états et que la transition est O(N) , alors la solution prendrait approximativement le temps O(N^3) .
Problème de sac à dos
0-1 sac à dos
Le problème de sac à dos est un problème lorsqu'il est donné un ensemble d'éléments, chacun avec un poids, une valeur et exactement 1 copie , déterminer quel (s) élément (s) inclure dans une collection de sorte que le poids total soit inférieur ou égal à un limite et la valeur totale est aussi grande que possible.
Exemple C ++:
Mise en œuvre :
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
Sortie :
3
Cela signifie que la valeur maximale peut être atteinte est 3, ce qui est obtenu en choisissant (2,1) et (3,2).
Sac à dos sans limite
Le problème de sac à dos sans limite est un problème qui, avec un ensemble d'éléments, chacun avec un poids, une valeur et des copies infinies , détermine le nombre de chaque élément à inclure dans une collection de sorte que le poids total soit inférieur ou égal à une limite donnée et la valeur totale est la plus grande possible.
Python (2.7.11) Exemple:
Mise en œuvre :
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 complexité de cette implémentation est O(nC) , n étant le nombre d'éléments.
Test :
w = [2, 3, 4, 5, 6]
v = [2, 4, 6, 8, 9]
print unbounded_knapsack(w, v, 13)
Sortie :
20
Cela signifie que la valeur maximale pouvant être atteinte est de 20, obtenue en choisissant (5, 8), (5, 8) et (3, 4).
Algorithme de planification des travaux pondérés
L'algorithme de planification des travaux pondérés peut également être appelé algorithme de sélection d'activité pondérée.
Le problème est que, compte tenu de certains emplois avec leur heure de début et de fin, et un bénéfice que vous faites lorsque vous avez terminé le travail, quel est le profit maximum que vous pouvez faire étant donné qu'aucun travail ne peut être exécuté en parallèle?
Celui-ci ressemble à la sélection d'activité à l'aide de l'algorithme gourmand, mais il y a une torsion supplémentaire. Autrement dit, au lieu de maximiser le nombre d’emplois terminés, nous mettons l’accent sur le profit maximum. Le nombre d'emplois effectués n'a pas d'importance ici.
Regardons un exemple:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Les emplois sont désignés par un nom, leur heure de début et de fin et leur profit. Après quelques itérations, nous pouvons savoir si nous réalisons Job-A et Job-E , nous pouvons obtenir un profit maximum de 17. Maintenant, comment le découvrir en utilisant un algorithme?
La première chose à faire est de trier les travaux en fonction de leur temps d’arrivée dans un ordre non décroissant. Pourquoi faisons-nous cela? C'est parce que si nous choisissons un travail qui prend moins de temps pour finir, nous laissons le plus de temps possible pour choisir d'autres emplois. Nous avons:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Nous aurons un tableau temporaire supplémentaire Acc_Prof de taille n (Ici, n désigne le nombre total de travaux). Cela contiendra le profit maximum accumulé de l'exécution des travaux. Ne comprends pas? Attendez et regardez. Nous allons initialiser les valeurs du tableau avec le profit de chaque travail. Cela signifie que , Acc_Prof [i] sera tout d' abord maintenir le bénéfice d'effectuer travail i-ème.
+-------------------------+---------+---------+---------+---------+---------+---------+
| Acc_Prof | 5 | 6 | 5 | 4 | 11 | 2 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Notons maintenant la position 2 avec i et la position 1 avec j . Notre stratégie sera d'itérer j de 1 à i-1 et après chaque itération, nous incrémenterons i de 1 jusqu'à ce que i devienne 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Nous vérifions si les tâches [i] et la tâche [j] se chevauchent, c’est-à-dire que si l’ heure de fin de la tâche [j] est supérieure à celle de la tâche [i] , ces deux tâches ne peuvent pas être effectuées ensemble. Cependant, s'ils ne se chevauchent pas, nous vérifierons si Acc_Prof [j] + Profit [i]> Acc_Prof [i] . Si tel est le cas, nous mettrons à jour Acc_Prof [i] = Acc_Prof [j] + Profit [i] . C'est:
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
Ici, Acc_Prof [j] + Profit [i] représente le bénéfice cumulé de la réalisation de ces deux tâches. Vérifions-le pour notre exemple:
Ici Job [j] chevauche Job [i] . Donc, ils ne peuvent pas être faits ensemble. Puisque notre j est égal à i-1 , nous incrémentons la valeur de i à i + 1 soit 3 . Et on fait 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Maintenant, Job [j] et Job [i] ne se chevauchent pas. Le montant total des bénéfices que nous pouvons réaliser en choisissant ces deux emplois est le suivant: Acc_Prof [j] + Profit [i] = 5 + 5 = 10 qui est supérieur à Acc_Prof [i] . Nous mettons donc à jour Acc_Prof [i] = 10 . Nous incrémentons aussi j de 1. Nous obtenons,
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Ici, Job [j] chevauche Job [i] et j est également égal à i-1 . Nous incrémentons donc i de 1 et faisons j = 1 . On a,
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Maintenant, Job [j] et Job [i] ne se chevauchent pas, nous obtenons le bénéfice cumulé 5 + 4 = 9 , qui est supérieur à Acc_Prof [i] . Nous mettons à jour Acc_Prof [i] = 9 et incrémentons j de 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Encore une fois, Job [j] et Job [i] ne se chevauchent pas. Le bénéfice accumulé est de: 6 + 4 = 10 , ce qui est supérieur à Acc_Prof [i] . Nous mettons à jour à nouveau Acc_Prof [i] = 10 . Nous incrémentons j de 1. Nous obtenons:
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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
Si nous continuons ce processus, après avoir parcouru toute la table en utilisant i , notre table ressemblera à ceci:
+-------------------------+---------+---------+---------+---------+---------+---------+
| 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 |
+-------------------------+---------+---------+---------+---------+---------+---------+
* Quelques étapes ont été sautées pour raccourcir le document.
Si nous parcourons le tableau Acc_Prof , nous pouvons trouver le profit maximum à 17 ! Le pseudo-code:
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 complexité de remplissage du tableau Acc_Prof est O (n 2 ). La traversée du tableau prend O (n) . La complexité totale de cet algorithme est donc O (n 2 ).
Maintenant, si nous voulons savoir quels travaux ont été effectués pour obtenir le maximum de profit, nous devons parcourir le tableau dans l’ordre inverse et si Acc_Prof correspond au maxProfit , nous allons pousser le nom du travail dans une pile et soustraire Profit de ce travail de maxProfit . Nous le ferons jusqu'à notre maxProfit> 0 ou nous atteignons le point de départ du tableau Acc_Prof . Le pseudo-code ressemblera à:
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 complexité de cette procédure est la suivante: O (n) .
Une chose à retenir: si plusieurs horaires de travail peuvent nous permettre de réaliser des bénéfices maximum, nous ne pouvons trouver qu'un seul emploi par cette procédure.
Modifier la distance
L'énoncé du problème est comme si on nous donnait deux chaînes str1 et str2, puis combien de nombres minimum d'opérations pourraient être exécutés sur la str1 qu'elle serait convertie en str2.
Implémentation en 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()];
}
}
Sortie
3
La plus longue sous-séquence commune
Si on nous donne les deux chaînes, nous devons trouver la plus longue sous-séquence commune présente dans les deux.
Exemple
LCS pour les séquences d'entrée "ABCDGH" et "AEDFHR" est "ADH" de longueur 3.
LCS pour les séquences d’entrée “AGGTAB” et “GXTXAYB” est “GTAB” de longueur 4.
Implémentation en 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()];
}
}
Sortie
4
Numéro de Fibonacci
Approche ascendante pour imprimer le nième numéro de Fibonacci en utilisant la programmation dynamique.
Arbre récursif
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)
Chevauchement des sous-problèmes
Ici, fib (0), fib (1) et fib (3) sont les sous-problèmes qui se chevauchent.fib (0) se répète 3 fois, fib (1) se répète 5 fois et fib (3) se répète 2 fois.
la mise en oeuvre
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];
}
La complexité du temps
Sur)
Plus longue sous-chaîne commune
Compte tenu de 2 chaînes str1 et str2, il faut trouver la longueur de la plus longue sous-chaîne commune entre elles.
Exemples
Entrée: X = "abcdxyz", y = "xyzabcd" Sortie: 4
La plus longue sous-chaîne commune est "abcd" et est de longueur 4.
Entrée: X = "zxabcdezy", y = "yzabcdezx" Sortie: 6
La plus longue sous-chaîne commune est "abcdez" et est de longueur 6.
Implémentation en 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;
}
La complexité du temps
O (m * n)