La programmation dynamique est un modèle d'algorithme qui résout un problème complexe en le divisant en sous-problèmes, en stockant leurs résultats afin d'éviter d'avoir à recalculer ces 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 l'essentiel, cette programmation est utilisée pour l'optimisation.
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 de 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'elle 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ù en utilisant de l'espace supplémentaire, vous pouvez améliorer le temps nécessaire pour trouver une solution..
Index des articles
Vous devez avoir un problème avec les caractéristiques essentielles suivantes avant que la programmation dynamique puisse être appliquée:
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 routes les plus courtes, la solution peut être facilement formulée de manière récursive, ce que fait l'algorithme Floyd-Warshall..
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, cette formulation récursive peut être considérée: 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-arborescences récursives 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, de sorte qu'il ne résout chaque sous-problème qu'une seule fois. Cela peut être accompli de deux manières:
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. Si 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 le tableau.
Une fois que la solution d'un problème est formulée de manière récursive en termes de ses sous-problèmes, il sera possible d'essayer de reformuler le problème de manière ascendante: nous allons d'abord essayer de résoudre les sous-problèmes et utiliser leurs solutions pour arriver à des solutions aux sous-problèmes plus grands..
Ceci est également généralement fait 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.
Une caractéristique importante d'un problème qui peut être résolu dynamiquement est qu'il doit avoir des sous-problèmes qui se chevauchent. 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 des valeurs calculées précédemment.
Pour tout entier positif "e", l'une des trois étapes suivantes peut être effectuée.
- Soustrayez 1 du nombre. (e = e-1).
- S'il est divisible par 2, divisez par 2 (si e% 2 == 0, alors e = e / 2).
- S'il est divisible par 3, divisez 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).
On pourrait penser à toujours choisir le pas qui rend n aussi bas que 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, nous pouvons 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:
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 du programme.
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 optimum 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..
- Beaucoup de mémoire est nécessaire pour stocker le résultat calculé de chaque sous-problème, incapable de 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 lors de l'exécution. Cela conduit à une utilisation inutile de la mémoire.
- Dans la programmation dynamique, les fonctions sont appelées récursivement. Cela maintient la mémoire de la pile en constante augmentation.
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 que vous n'avez pas de restrictions de mémoire, il est préférable d'utiliser la programmation dynamique.
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 scientifiques, y compris de nombreux exemples en intelligence artificielle, de la résolution de problèmes de planification à la reconnaissance vocale..
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 les plus courtes par 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.
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.
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é plus tard.
Dans ce cas, pour la même série de Fibonacci, f (0) est d'abord calculé, puis f (1), f (2), f (3), etc. Ainsi, les solutions des sous-problèmes seront construites de bas en haut.
Personne n'a encore commenté ce post.