PROGRAMMATION DYNAMIQUE: CARACTÉRISTIQUES, EXEMPLE, AVANTAGES, INCONVÉNIENTS - LA TECHNOLOGIE - 2025

La programmation dynamique est un algorithme modèle qui résout un problème complexe en le divisant en sous-problèmes, en stockant les résultats de celui-ci pour éviter d'avoir à recalculer les résultats.

Cette planification est utilisée lorsque vous rencontrez des problèmes qui peuvent être divisés en sous-problèmes similaires, afin que leurs résultats puissent être réutilisés. Pour la plupart, ce calendrier est utilisé pour l'optimisation.

Programmation dynamique. Sous-problèmes superposés dans la séquence de Fibonacci. Source: Wikimedia commons, en: Utilisateur: Dcoatzee, tracé par Utilisateur: Stannered / Domaine public

Avant de résoudre le sous-problème disponible, l'algorithme dynamique tentera d'examiner les résultats des sous-problèmes précédemment résolus. Les solutions aux sous-problèmes sont combinées pour obtenir la meilleure solution.

Au lieu de calculer le même sous-problème encore et encore, vous pouvez stocker votre solution dans une certaine mémoire lorsque vous rencontrez ce sous-problème pour la première fois. Lorsqu'il réapparaît lors de la résolution d'un autre sous-problème, la solution déjà stockée en mémoire sera reprise.

C'est une excellente idée pour corriger le temps de mémoire, où l'utilisation d'espace supplémentaire peut améliorer le temps nécessaire pour trouver une solution.

Caractéristiques de la programmation dynamique

Vous devez avoir un problème avec les caractéristiques essentielles suivantes avant que la programmation dynamique puisse être appliquée:

Sous-structure optimale

Cette caractéristique exprime qu'un problème d'optimisation peut être résolu en combinant les solutions optimales des problèmes secondaires qui le composent. Ces sous-structures optimales sont décrites par récursivité.

Par exemple, dans un graphe, une sous-structure optimale sera présentée dans le plus court chemin r qui va d'un sommet s à un sommet t:

Autrement dit, dans ce chemin le plus court r, n'importe quel sommet intermédiaire i peut être pris. Si r est vraiment la route la plus courte, alors elle peut être divisée en sous-routes r1 (de s à i) et r2 (de i à t), de telle sorte que ce sont à leur tour les routes les plus courtes entre les sommets correspondants.

Par conséquent, pour trouver les chemins les plus courts, la solution peut être facilement formulée de manière récursive, ce que fait l'algorithme Floyd-Warshall.

Chevauchement des sous-problèmes

L'espace du sous-problème doit être petit. Autrement dit, tout algorithme récursif qui résout un problème devra résoudre les mêmes sous-problèmes encore et encore, au lieu de générer de nouveaux sous-problèmes.

Par exemple, pour générer la série de Fibonacci, nous pouvons considérer cette formulation récursive: Fn = F (n - 1) + F (n - 2), en prenant comme cas de base que F1 = F2 = 1. On aura alors: F33 = F32 + F31 et F32 = F31 + F30.

Comme vous pouvez le voir, F31 est en cours de résolution dans les sous-arbres récursifs de F33 et F32. Bien que le nombre total de sous-problèmes soit vraiment petit, si vous adoptez une solution récursive comme celle-ci, vous finirez par résoudre les mêmes problèmes encore et encore.

Ceci est pris en compte par la programmation dynamique, donc cela résout chaque sous-problème une seule fois. Cela peut être accompli de deux manières:

Approche descendante

Si la solution à un problème quelconque peut être formulée de manière récursive en utilisant la solution de ses sous-problèmes, et si ces sous-problèmes se chevauchent, alors les solutions aux sous-problèmes peuvent être facilement mémorisées ou stockées dans une table.

Chaque fois qu'une nouvelle solution de sous-problème est recherchée, la table sera vérifiée pour voir si elle a déjà été résolue. Dans le cas où une solution est stockée, elle sera utilisée au lieu de la calculer à nouveau. Sinon, le sous-problème sera résolu, en stockant la solution dans la table.

Une approche en profondeur

Une fois que la solution d'un problème est formulée de manière récursive en termes de sous-problèmes, il est possible d'essayer de reformuler le problème de manière ascendante: d'abord, nous allons essayer de résoudre les sous-problèmes et utiliser leurs solutions pour trouver des solutions aux sous-problèmes plus importants.

Cela se fait également généralement sous forme de tableau, générant de manière itérative des solutions à des sous-problèmes de plus en plus grands en utilisant des solutions à des sous-problèmes plus petits. Par exemple, si les valeurs de F31 et F30 sont déjà connues, la valeur de F32 peut être calculée directement.

Comparaison avec d'autres techniques

Une caractéristique importante d'un problème qui peut être résolu par la programmation dynamique est que les sous-problèmes doivent se chevaucher. C'est ce qui distingue la programmation dynamique de la technique de division et de conquête, où il n'est pas nécessaire de stocker les valeurs les plus simples.

Elle est similaire à la récursivité, car lors du calcul des cas de base, la valeur finale peut être déterminée de manière inductive. Cette approche ascendante fonctionne bien lorsqu'une nouvelle valeur dépend uniquement de valeurs calculées précédemment.

Exemple

Pas minimum pour atteindre 1

Pour tout entier positif "e", l'une quelconque des trois étapes suivantes peut être effectuée.

- Soustrayez 1 du nombre. (e = e-1).

- S'il est divisible par 2, il est divisé par 2 (si e% 2 == 0, alors e = e / 2).

- S'il est divisible par 3, il est divisé par 3 (si e% 3 == 0, alors e = e / 3).

Sur la base des étapes ci-dessus, le nombre minimum de ces étapes doit être trouvé pour amener e à 1. Par exemple:

- Si e = 1, résultat: 0.

- Si e = 4, résultat: 2 (4/2 = 2/2 = 1).

- Lorsque e = 7, résultat: 3 (7-1 = 6/3 = 2/2 = 1).

Concentrer

On pourrait penser à toujours choisir le pas qui rend n le plus bas possible et à continuer ainsi, jusqu'à ce qu'il atteigne 1. Cependant, on peut voir que cette stratégie ne fonctionne pas ici.

Par exemple, si e = 10, les étapes seraient: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 étapes). Cependant, la forme optimale est: 10-1 = 9/3 = 3/3 = 1 (3 étapes). Par conséquent, toutes les étapes possibles qui peuvent être effectuées pour chaque valeur de n trouvée doivent être essayées, en choisissant le nombre minimum de ces possibilités.

Tout commence par la récursivité: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} si e> 1, en prenant comme cas de base: F (1) = 0. Ayant l'équation de récurrence, vous pouvez commencer à coder la récursivité.

Cependant, on peut voir qu'il a des sous-problèmes qui se chevauchent. De plus, la solution optimale pour une entrée donnée dépend de la solution optimale de ses sous-problèmes.

Comme dans la mémorisation, où les solutions des sous-problèmes qui sont résolus sont stockées pour une utilisation ultérieure. Ou comme dans la programmation dynamique, vous commencez par le bas, en remontant jusqu'au e donné. Puis les deux codes:

Mémorisation

Programmation dynamique ascendante

avantage

L'un des principaux avantages de l'utilisation de la programmation dynamique est qu'elle accélère le traitement, car des références précédemment calculées sont utilisées. Comme il s'agit d'une technique de programmation récursive, elle réduit les lignes de code dans le programme.

Algorithmes voraces vs programmation dynamique

Les algorithmes gourmands sont similaires à la programmation dynamique en ce qu'ils sont tous deux des outils d'optimisation. Cependant, l'algorithme glouton recherche une solution optimale à chaque étape locale. Autrement dit, il cherche un choix gourmand dans l'espoir de trouver un optimum global.

Par conséquent, les algorithmes gourmands peuvent faire une hypothèse qui semble optimale à ce moment-là, mais qui devient coûteuse à l'avenir et ne garantit pas un optimal global.

D'autre part, la programmation dynamique trouve la solution optimale pour les sous-problèmes et fait ensuite un choix éclairé en combinant les résultats de ces sous-problèmes pour trouver réellement la solution la plus optimale.

Désavantages

- Il faut beaucoup de mémoire pour stocker le résultat calculé de chaque sous-problème, sans pouvoir garantir que la valeur stockée sera utilisée ou non.

- Plusieurs fois, la valeur de sortie est stockée sans jamais être utilisée dans les sous-problèmes suivants pendant l'exécution. Cela conduit à une utilisation inutile de la mémoire.

- En programmation dynamique, les fonctions sont appelées récursivement. Cela maintient la mémoire de la pile en constante augmentation.

Récursivité vs programmation dynamique

Si vous avez une mémoire limitée pour exécuter votre code et que la vitesse de traitement n'est pas un problème, vous pouvez utiliser la récursivité. Par exemple, si vous développez une application mobile, la mémoire est très limitée pour exécuter l'application.

Si vous souhaitez que le programme s'exécute plus rapidement et n'ait aucune restriction de mémoire, il est préférable d'utiliser la programmation dynamique.

Applications

La programmation dynamique est une méthode efficace pour résoudre des problèmes qui pourraient autrement sembler extrêmement difficiles à résoudre dans un laps de temps raisonnable.

Les algorithmes basés sur le paradigme de programmation dynamique sont utilisés dans de nombreux domaines de la science, y compris de nombreux exemples en intelligence artificielle, de la résolution de problèmes de planification à la reconnaissance vocale.

Algorithmes basés sur la programmation dynamique

La programmation dynamique est assez efficace et fonctionne très bien pour un large éventail de problèmes. De nombreux algorithmes peuvent être considérés comme des applications d'algorithme gourmandes, telles que:

- Série de numéros de Fibonacci.

- Tours de Hanoi.

- Toutes les paires de routes plus courtes à travers Floyd-Warshall.

- Problème de sac à dos.

- Planification du projet.

- Le chemin le plus court à travers Dijkstra.

- Contrôle de vol et contrôle robotique.

- Problèmes d'optimisation mathématique.

- Temps partagé: planifiez le travail pour maximiser l'utilisation du processeur.

Série de numéros de Fibonacci

Les nombres de Fibonacci sont les nombres trouvés dans l'ordre suivant: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, etc.

En terminologie mathématique, la séquence Fn des nombres de Fibonacci est définie par la formule de récurrence: F (n) = F (n -1) + F (n -2), où F (0) = 0 et F (1) = 1.

Approche descendante

Dans cet exemple, un tableau de recherche avec toutes les valeurs initiales est initialisé avec -1. Chaque fois que la solution à un sous-problème est nécessaire, cette matrice de recherche sera recherchée en premier.

Si la valeur calculée est là, cette valeur sera renvoyée. Sinon, le résultat sera calculé pour être stocké dans le tableau de recherche afin qu'il puisse être réutilisé ultérieurement.

Une approche en profondeur

Dans ce cas, pour la même série de Fibonacci, f (0) est d'abord calculé, puis f (1), f (2), f (3), et ainsi de suite. Ainsi, les solutions des sous-problèmes sont construites de bas en haut.

Références

1. Vineet Choudhary (2020). Introduction à la programmation dynamique. Developer Insider. Tiré de: developerinsider.co.
2. Alex Allain (2020). Programmation dynamique en C ++. Programmation C. Tiré de: cprogramming.com.
3. Après l'Académie (2020). Idée de programmation dynamique. Tiré de: afteracademy.com.
4. Aniruddha Chaudhari (2019). Programmation dynamique et récursivité - Différence, avantages avec l'exemple. CSE Stack. Tiré de: csestack.org.
5. Code Chef (2020). Tutoriel pour la programmation dynamique. Tiré de: codechef.com.
6. Programiz (2020). Programmation dynamique. Tiré de: programiz.com.