Qu'est-ce que la programmation dynamique ?

En matière de programmation informatique, la programmation dynamique est aussi polyvalente que mathématique. Richard Bellman a créé la technique dans les années 50, et elle a depuis été utilisée dans tout, de l'ingénierie aéronautique à l'économie.

Dans les deux contextes, le mot fait référence à la décomposition d'un sujet compliqué en éléments gérables. Les décisions pluriannuelles se séparent généralement de manière récursive. En informatique, un problème a une sous-structure optimale s'il peut être résolu de manière optimale en le disséquant en sous-problèmes et en trouvant de manière récursive les meilleures solutions.

Il existe une relation entre la valeur du problème principal et les valeurs des sous-problèmes si les sous-problèmes peuvent être imbriqués de manière récursive dans le problème principal et que des techniques de programmation dynamique peuvent être utilisées pour résoudre le problème principal. Dans le domaine de l'optimisation, l'équation de Bellman est un moyen bien connu de parler de ce lien particulier pour une meilleure stratégie.

Vous pouvez apprendre le génie logiciel à l'aide de cours en ligne.

Optimisation mathématique

En décomposant un choix complexe en une série de choix incrémentiels, comme cela se fait dans la programmation dynamique, un problème d'optimisation mathématique peut être rendu beaucoup plus gérable pour les opérations. Pour cela, on définit un ensemble de fonctions valeur V1, V2,…, Vn qui prennent chacune y comme argument pour décrire l'état du système à un certain instant du temps I de 0 à n. Vn(y) est la valeur au temps n qui a été acquise à partir de l'état y. En utilisant une connexion récursive connue sous le nom d'équation de Bellman, nous pouvons déterminer les valeurs de Vi aux périodes précédentes I = n1, n2,…, 2, 1. En maximisant une fonction simple (souvent la somme) du bénéfice d'un choix à temps I 1 et la fonction Vi au nouvel état du système, on peut dériver Vi1 à tout état y de Vi, où I = 2,…, n. Cette procédure renvoie Vi1 pour les états requis puisque Vi a déjà été calculé pour eux. Et enfin, la valeur de la solution optimale, V1, se trouve dans la condition de départ du système. En retraçant les étapes des calculs précédents, les valeurs optimales des variables de choix peuvent être récupérées une par une.

Pour que la programmation dynamique soit utile, un problème doit avoir deux caractéristiques : une sous-structure optimale et des sous-problèmes qui se chevauchent. Le terme « diviser pour régner » est utilisé pour désigner une technique dans laquelle une difficulté est décomposée en problèmes plus petits et indépendants, puis résolue en combinant les meilleures réponses à chacun. C'est pourquoi nous ne considérons pas le tri par fusion et le tri rapide comme des difficultés de programmation dynamique.

Un programme de certificat en génie logiciel peut améliorer vos compétences.

Un problème d'optimisation avec une sous-structure optimale peut être résolu en combinant les solutions à ses sous-problèmes. Les sous-structures idéales sont généralement définies par récursivité. Chaque sommet intermédiaire a gagné le chemin le plus court p d'un sommet u à un sommet v dans le graphe G=(V,E) est un exemple de sous-structure optimale. Si le chemin p est le plus court, il peut être partitionné en deux chemins, p1 de u à w et p2 de w à v, qui sont aussi les plus courts entre leurs paires de sommets respectives. Ainsi, les algorithmes Bellman-Ford et Floyd-Warshall utilisent la récursivité pour trouver les chemins les plus courts.

Quelle est la logique derrière l'utilisation d'une méthode de programmation dynamique ?

La procédure de programmation dynamique est la suivante :

1. Ce faisant, il réduit la complexité de tous les aspects du problème initial.
2. Pour résoudre ces petits problèmes, il détermine la meilleure réponse possible.
3. Il garde une trace des solutions aux petits défis (mémoïsation). La mémorisation est l'acte de se souvenir des solutions à des problèmes plus petits.
4. Il les recycle de sorte que la même partie du problème puisse être résolue plusieurs fois.
5. Après tout cela, vous devez trouver la réponse à la question difficile.

1. Sous-structures optimales et problèmes avec sous-problèmes qui se chevauchent. Dans ce contexte, le terme « sous-structure optimale » fait référence à une méthode par laquelle les problèmes d'optimisation peuvent être résolus en intégrant les meilleures solutions à leurs sous-problèmes constitutifs.
2. Étant donné que les résultats intermédiaires doivent être stockés, la complexité spatiale de la programmation dynamique augmente alors même que la complexité temporelle diminue.