Nous prolongeons la méthode générale « diviser pour régner » implémentée grâce à la récursivité en systématisant la démarche de mémoïsation, puis en allant plus loin pour compléter encore ces algorithmes lorsqu’ils ne sont pas efficaces.
I. De l’approche DR à la programmation dynamique (DP)
Dans l’approche diviser pour régner (DR) appliquée sur les exemples de tri fusion ou de la recherche dichotomique, nous avons utilisé comme outils la récursivité et la création de sous-problèmes indépendants dont la résolution permet de traiter le problème initial.
Cette approche est améliorée par la technique de la mémoïsation. Dans l’approche de la programmation dynamique (DP), les sous-problèmes se recoupent parfois et sont réutilisés dans la résolution de plusieurs problèmes différents. Nous allons le voir en reprenant l’exemple de la suite de Fibonacci.
II. Exemple de redondance avec Fibonnaci
Partons d’une fonction fibo() classiquement définie de manière récursive par :
On obtient l’arbre des appels suivant en lançant fibo(5) où l’on voit que la démarche n’est pas efficace car de nombreux appels (indiqués en orange) sont redondants. La mémoïsation améliore fortement l’efficacité de l’algorithme.
III. Mémoïsation d’une fonction quelconque
Le procédé de mémoïsation a été introduit au chapitre 2 où une version mémoïsée de fonction fibonacci est proposée. L’arbre des appels correspondant est maintenant beaucoup plus simple car tous les appels indiqués en orange ont déjà été calculés et leur valeur est immédiatement disponible.
Il existe dans Python un décorateur de mémoïsation : lru_cache dans le module functools que nous pouvons directement utiliser. Ce décorateur met en place une mémoïsation pour la fonction décorée :
Nous bénéficions ainsi de performances bien meilleures. En effet, si on appelle fibonacci(5), on obtient l’arbre des appels ci-dessus, beaucoup plus réduit.
Les méthodes vues à ce stade sont de type DR « top-down » ou « haut-bas ». La mémoïsation constitue l’un des outils de base de la programmation dynamique, DP.
IV. Démarche « bas vers haut »
La démarche inverse de type itérative « bottom-up », du bas vers le haut, est également possible, par exemple pour fibo :
Mot-clé
Dans une forme itérative « bottom-up », on résout d’abord les sous-problèmes de « petite taille », puis ceux de la taille intermédiaire… jusqu’à la taille voulue. On stocke les résultats partiels dans un tableau ou un dictionnaire comme dans la mémoïsation.
Les performances sont semblables à celles de la fonction mémoïsée, une exécution en temps linéaire, proportionnel à n, et une occupation mémoire de taille n.