DAA - Programmation dynamique

La programmation dynamique est également utilisée dans les problèmes d'optimisation. À l'instar de la méthode de division et de conquête, la programmation dynamique résout les problèmes en combinant les solutions de sous-problèmes. De plus, l'algorithme de programmation dynamique résout chaque sous-problème une seule fois, puis enregistre sa réponse dans un tableau, évitant ainsi le travail de recalculer la réponse à chaque fois.

Deux propriétés principales d'un problème suggèrent que le problème donné peut être résolu à l'aide de la programmation dynamique. Ces propriétés sontoverlapping sub-problems and optimal substructure.

Sous-problèmes qui se chevauchent

Semblable à l'approche Divide-and-Conquer, la programmation dynamique combine également des solutions à des sous-problèmes. Il est principalement utilisé lorsque la solution d'un sous-problème est nécessaire à plusieurs reprises. Les solutions calculées sont stockées dans une table, de sorte qu'elles ne doivent pas être recalculées. Par conséquent, cette technique est nécessaire lorsque des sous-problèmes se chevauchent.

Par exemple, la recherche binaire n'a pas de sous-problème de chevauchement. Alors que le programme récursif des nombres de Fibonacci a de nombreux sous-problèmes qui se chevauchent.

Sous-structure optimale

Un problème donné a une propriété de sous-structure optimale, si la solution optimale du problème donné peut être obtenue en utilisant des solutions optimales de ses sous-problèmes.

Par exemple, le problème du chemin le plus court a la propriété de sous-structure optimale suivante -

Si un nœud x se trouve dans le chemin le plus court depuis un nœud source u au nœud de destination v, puis le chemin le plus court depuis u à v est la combinaison du chemin le plus court depuis u à x, et le chemin le plus court depuis x à v.

Les algorithmes standard All Pair Shortest Path comme Floyd-Warshall et Bellman-Ford sont des exemples typiques de programmation dynamique.

Étapes de l'approche de programmation dynamique

L'algorithme de programmation dynamique est conçu en utilisant les quatre étapes suivantes -

• Caractériser la structure d'une solution optimale.
• Définissez récursivement la valeur d'une solution optimale.
• Calculez la valeur d'une solution optimale, généralement de manière ascendante.
• Construisez une solution optimale à partir des informations calculées.

Applications de l'approche de programmation dynamique

• Multiplication de la chaîne matricielle
• Sous-séquence commune la plus longue
• Problème de vendeur itinérant