Introduction à la programmation dynamique : chevauchement des sous-problèmes et sous-structure optimale

Publié: 2021-02-08

Table des matières

introduction

Supposons que nous ayons une question pour résoudre le carré de 25. Si nous sommes confrontés à cette question pour la première fois, nous pouvons la résoudre soit à portée de main, soit à l'aide d'une calculatrice. Mais si nous avons déjà vu cette question auparavant ou si nous l'avons déjà résolue auparavant, il est possible que nous puissions y répondre rapidement en la mémorisant.

Cela nous amène à la conclusion que, si nous pouvons nous en souvenir, nous pouvons l'ignorer la prochaine fois. La programmation dynamique fonctionne sur un concept similaire, l'idée est de se souvenir du résultat d'un calcul et de l'utiliser à l'avenir si nécessaire.

Cette procédure simple de programmation dynamique en fait une arme puissante pour un programmeur pour conquérir la bataille du code efficace.

Par exemple, supposons que nous avons une question complexe et que nous pensons toujours à une solution qui divise la question en sous-problèmes. Mais nous pouvons rester coincés dans une situation où nous allons calculer un sous-problème plusieurs fois. Là, nous utilisons la programmation dynamique pour une solution optimale.

La programmation dynamique a deux concepts :

  1. Sous-problèmes qui se chevauchent
  2. Sous-structure optimale

Sous-problèmes qui se chevauchent

Un exemple classique de compréhension du concept de sous-problème de chevauchement est un programme pour imprimer la série de Fibonacci.

La logique de la suite de Fibonacci est donnée par « fibonacci(n) = fibonacci(n-1) + fibonacci(n-2) ». Et l'exécution de cette fonction de manière transparente peut être effectuée à l'aide d'une solution récursive, avec un cas de base de fibonacci(0)=0 et fibonacci(1)=1.

public static int fibonacci(int n){
 si (n== 0 || n== 1 )
 retour n;
 retourner fibonacci(n -1 )+fibonacci(n -2 );
 }
 public static void main(String[] args){
 System.out.print( "Le 4ème nombre de Fibonacci est " +fibonacci( 4 ));
 }

Disons que nous devons imprimer le 4ème chiffre de Fibonacci, puis l'arbre de récursivité va comme

fibonacci(4)

/ \

fibonacci(3) + fibonacci(2)

/ \ / \

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

/ \

fibonacci(1) + fibonacci(0)

Notez que fibonacci (4) est le 5ème chiffre de la série fibonacci car nous partons de fibonacci (0). Dans l'arbre de récursivité ci-dessus, nous pouvons voir que fibonacci(2) est répété deux fois. Nous avons observé une duplication dans un arbre de récursivité de hauteur 4, imaginons maintenant que nous avons un appel récursif d'un nombre énorme, et par la suite, il y aura un arbre de récursivité avec une grande hauteur. Et il y aura beaucoup de ces calculs en double, connus sous le nom de sous-problèmes qui se chevauchent.

Nous avons deux méthodes pour traiter cette (i) tabulation, (ii) mémorisation

Comprenons-les en parcourant leurs implémentations.

Mémoïsation

La résolution du problème de Fibonacci à l'aide de la méthode de mémorisation peut être effectuée comme indiqué ci-dessous

mémo int[] statique ;
public static int fibonacci(int n){
si(mémo[n]!=-1)
retour mémo[n] ;
si(n==0 || n==1){
mémo[n]=n ;
retour n;
}
mémo[n] = fibonacci(n-1)+fibonacci(n-2);
retour mémo[n] ;
}
public static void main(String[] args){
mémo=nouveau entier[5] ;
pour(entier i=0;i<=4;i++)
mémo[i]=-1 ;
System.out.println("4ème nombre de fibonacci est "+fibonacci(4));
}

Dans le code ci-dessus, nous créons un fichier journal ou maintenons une table de recherche et stockons les valeurs des résultats calculés. Puisque nous avons mémorisé toutes les valeurs calculées, nous pouvons les utiliser à l'avenir si nécessaire, évitant ainsi les calculs en double et les sous-problèmes qui se chevauchent.

Toute la logique est similaire à la solution récursive, mais la seule différence que nous avons faite est que nous les notons dans le tableau mémo avant de renvoyer la valeur à la méthode principale. La seule contrainte à cet algorithme est que nous avons besoin d'un espace supplémentaire de taille O(n), mais nous optimisons la solution récursive précédente.

Tabulation

Cette méthode est un peu différente de la solution ci-dessus. La mémorisation suit la même solution récursive. Mais dans la tabulation, nous suivons une solution itérative. On l'appelle aussi l'approche ascendante. Examinons la mise en œuvre de l'approche ascendante.

public static int fibonacci(int n){
 int table[]=new int[n+ 1 ] ;
 pour (int i= 0 ;i<=n;i++){
 si (je== 0 || je== 1 )
 table[i]=i ;
 sinon {
 table[i]=table[i -1 ]+table[i -2 ] ;
 }
 }
 table de retour [n] ;
 }
 public static void main(String[] args){
 System.out.println( "Le 4ème nombre de Fibonacci est " +fibonacci( 4 ));
 }

Comme nous savons que fibonacci(n)=fibonacci(n-1)+fibonacci(n-2), dans la mémorisation, nous avons commencé avec l'appel de la fonction fibonacci(4), puis nous avons réalisé que nous n'avions pas calculé sa valeur, nous 'ai calculé ses valeurs, puis stocké.

Une situation similaire sera rencontrée par d'autres appels récursifs comme fibonacci(3), fibonacci(2). Maintenant, cela fait attendre beaucoup d'appels récursifs dans la pile de récursivité, mais de toute façon nous sautons la duplication des sous-problèmes qui se chevauchent.

Nous avons également un moyen de calculer les fibonacci de 0 au nième élément de manière itérative, puis de renvoyer le nième élément de fibonacci. C'est ce que nous avons implémenté dans le code ci-dessus. Ce code a également le même encombrement O(n).

Checkout : Compétences pour devenir un développeur full stack

Sous-structure optimale

Dans ce concept, nous ne pouvons obtenir une solution optimale à un problème que si nous avons résolu de manière optimale ses sous-problèmes correspondants.

Et un exemple classique de ce concept envisage un parcours entre les nœuds d'un graphe.

Supposons que nous ayons plusieurs racines de Telangana à Delhi. Et si nous avons le chemin le plus court qui passe par Nagpur et Gwalior. Ensuite, l'itinéraire le plus court de Nagpur à Delhi Delhi doit passer par Gwalior. Maintenant, nous pouvons diviser notre problème en sous-problèmes qui sont Telangana à Nagpur, Nagpur à Gwalior, Gwalior à Delhi.

Et un exemple classique de cette propriété est la plus longue sous-séquence commune dans les deux chaînes. Une sous-séquence est différente d'une sous-chaîne. Dans une sous-séquence, les caractères n'ont pas besoin d'être conséquents dans la chaîne d'origine.

L'idée est donc de le résoudre en résolvant ses sous-problèmes de manière optimale. Soit n la longueur de la plus longue sous-suite commune.

Si n=LCS(potato,tatto), alors n=LCS(potat,tatto)+1 (si les derniers caractères sont identiques), sinon n=maximum(LCS(potato,tatto), LCS(potat,tatto).

static int lcs(String s1, String s2, int m, int n ){
 int dp[][] = new int[m+ 1 ][n+ 1 ] ;
 pour (int je= 0 ; je<=m; je++){
 pour (int j= 0 ; j<=n; j++){
 si (je == 0 || j == 0 )
 dp[i][j] = 0 ;
 sinon si (s1.charAt(i -1 ) == s2.charAt(j -1 ))
 dp[i][j] = dp[i -1 ][j -1 ]+ 1 ;
 autre
 dp[i][j] = Math.max(dp[i -1 ][j], dp[i][j -1 ]);
 }
 }
 retourner dp[m][n] ;
 }
 public static void main(String[] args){
 System.out.println( "la longueur de la plus longue sous-séquence commune est " +lcs( "potato" , "tattoo" , 6 , 6 ));
 }

Dans le code ci-dessus, nous avons implémenté notre logique en utilisant la méthode de tabulation et calculé la longueur de la plus longue sous-séquence commune présente dans les deux chaînes.

Lisez aussi: Salaire d'un développeur Full Stack en Inde

Apprenez des cours de développement de logiciels en ligne dans les meilleures universités du monde. Gagnez des programmes Executive PG, des programmes de certificat avancés ou des programmes de maîtrise pour accélérer votre carrière.

Conclusion

Maintenant que vous savez utiliser l'une des techniques puissantes pour conquérir la bataille du code efficace, essayez de mettre en œuvre la programmation dynamique pour d'autres problèmes et commencez à renforcer votre capacité à coder une question à l'aide de la programmation dynamique.

Pour conclure, les cours de développeurs Full Stack sont des experts hautement qualifiés qui peuvent gérer tout ce qui concerne le développement Web. Ces compétences de Développeur Full Stack sont ce qui les distingue des Développeurs Frontend et Backend.

Qu'est-ce que la programmation dynamique ?

Un programme informatique contient beaucoup de code répétitif. Ceci est inefficace et peut avoir un impact sur ses performances. Dans ce cas, la programmation dynamique est utilisée. La programmation dynamique est une méthode pour résoudre un problème complexe en le divisant en sous-problèmes plus simples, en résolvant chacun de ces sous-problèmes une seule fois et en stockant leurs solutions à l'aide de tableaux, qui sont ensuite consultés chaque fois qu'un sous-problème similaire se produit plus tard dans la solution du problème complexe. Les algorithmes de programmation dynamique sont utilisés pour résoudre divers types de problèmes d'optimisation dans les domaines de la recherche opérationnelle, de l'estimation statistique, de la reconnaissance de formes, de l'intelligence artificielle, de l'apprentissage automatique, de la biologie computationnelle et d'autres domaines.

Qu'est-ce qu'un sous-problème de chevauchement dans la programmation dynamique ?

Le sous-problème de chevauchement est un concept utilisé lorsque les sous-problèmes ont des solutions qui sont également utilisées dans d'autres sous-problèmes. Ce chevauchement entraîne la résolution de la même sous-tâche plusieurs fois. Le problème est de trouver un moyen de résoudre la sous-tâche une seule fois et d'utiliser cette solution pour obtenir les solutions d'autres sous-problèmes. Les algorithmes de programmation dynamique résolvent ce problème en utilisant la mémorisation. La mémorisation est une technique où nous stockons des solutions à des sous-problèmes afin de ne pas avoir à les résoudre à nouveau.

Quelle est la sous-structure optimale en programmation dynamique ?

La sous-structure optimale implique que la solution optimale à un problème est liée à une solution optimale à un problème plus petit dans la même définition de problème. Une sous-structure optimale est une exigence supplémentaire nécessaire pour résoudre des problèmes ou pour prouver qu'il n'y a pas de solution. Avec une sous-structure optimale, nous pouvons prouver de nombreux problèmes NP-difficiles. Une approche générale pour résoudre les problèmes DP consiste à utiliser une matrice de programmation dynamique pour stocker la solution optimale des sous-problèmes. La matrice de programmation dynamique peut être utilisée pour résoudre tous les problèmes DP de sous-structure optimale non nulle.