La sous-structure optimale en programmation dynamique

La sous-structure optimale signifie que la solution optimale à un problème de taille n (ayant n éléments) est basée sur une solution optimale au même problème de plus petite taille (moins de n éléments). c'est-à-dire que, tout en construisant la solution d'un problème de taille n, on la définit en fonction de problèmes similaires de taille plus petite, disons k (k<n). Nous trouvons les solutions optimales de moins d'éléments et combinons les solutions pour obtenir le résultat final.

Exemple

Considérons le problème de trouver le chemin le plus court pour voyager entre deux villes en voiture. Une personne veut conduire de la ville A à la ville C, la ville B se situe entre les deux villes.

Il existe trois chemins différents reliant A à B et trois chemins reliant B à C, comme indiqué dans la figure ci-dessous :

Le chemin le plus court pour aller de A à C (95km) impliquera à la fois de prendre le chemin le plus court de A vers B et le chemin le plus court de B vers C. Cela signifie par exemple :

•  Si le chemin le plus court de Rabat à Fès passe par Meknès, alors ce sera la somme du chemin le plus court de Rabat à Meknès et du chemin le plus court de Meknès à Fès.
•  Si le chemin le plus court de Rabat à Fès passe par Khemisat et Meknès, alors le chemin le plus court de Khemisat à Fès passe aussi par Meknès.

En d'autres termes, le problème de se rendre de Rabat à Meknès est imbriqué dans le problème de se rendre de Rabat à Fès.

En bref, cela signifie que nous pouvons écrire une formule récursive pour une solution au problème de la recherche du chemin le plus court.

Nous disons que le problème de la recherche de la route la plus courte entre deux villes démontre la propriété de sous-structure optimale. Il s'agit de l'une des deux conditions de la programmation dynamique. Une autre condition est le chevauchement des sous-problèmes.

Utilisation de la sous-structure optimale en programmation dynamique (DP)

Fondamentalement, la programmation dynamique est un outil important pour optimiser les solutions récursives d'une manière plus efficace, à la fois en termes de mémoire et de temps, que la récursivité régulière.

L'écriture d'une formule récursive ou la définition de la sous-structure optimale est la première étape vers la programmation dynamique. Si nous ne pouvons pas écrire une formule récursive pour le problème, nous ne pensons peut-être pas à utiliser la programmation dynamique.

La logique de la programmation dynamique vient généralement de la récursivité. La solution du problème est dérivée de la solution des sous-problèmes, la solution des sous-problèmes est dérivée de la solution des sous-sous-problèmes et ainsi de suite.

Dans les questions de programmation dynamique, c'est une bonne idée de résoudre d'abord le problème en utilisant une formule récursive, puis d'utiliser la même formule avec une approche ascendante(bottom-up) de la programmation dynamique.