Programmation dynamique
La programmation dynamique est une méthode algorithmique destinée à résoudre des problèmes d’optimisation. Elle consiste à faire en sorte de ne pas calculer plusieurs fois la même chose. Pour cela, les résultats intermédiaires sont momentanément stockés dans une structure de données.
Principe
Certaines villes sont construites selon un plan hippodamien : un type d’organisation de la ville dans lequel les rues sont rectilignes et se croisent en angle droit, créant des îlots de forme quadrangulaire, généralement parfaitement carrée ou rectangulaire.
C’est le cas par exemple de la ville de Barcelone.
Lorsqu’il s’agit de se déplacer dans ce type de ville, on peut se poser la question suivante :
Dans un quartier rectangulaire, combien existe-t-il de chemins menant d’un carrefour A à un autre B ?
(en allant toujours de la gauche vers la droite)
Pour un « petit » quartier, le problème peut être résolu rapidement :
10 solutions !
Mais si le problème s’applique à un quartier plus grand, le nombre de solutions augmente rapidement.
Existe-t-il un moyen de déterminer rapidement le nombre de chemins dans un quartier plus grand ?
OUI !! en utilisant les résultats obtenus pour des « quartiers » plus petits.
Si on note ces résultats pour chaque carrefour :
On remarque que l’on peut obtenir le résultat pour un carrefour en additionnant les résultats des carrefours précédents (un seul si on considère un carrefour en bordure du quartier).
Coefficients binomiaux
Formule de Pascal :
\({n \choose p} = \begin{cases}
1, & \text{si $n=p$ ou $p=0$} \\
{n-1 \choose p-1}+{n-1 \choose p}, & \text{sinon}
\end{cases}\)
Approche naïve par récursivité
def C(n,p) :
if p == n or p == 0:
return 1
else :
return C(n-1, p-1) + C(n-1, p)
Exemple : calcul de C(6,4) = \({6 \choose 4}\)
Complexité : factorielle !
Dans le pire des cas, \(p=\frac{n}{2}\)
\(\mathcal{O}\left(\frac{!n}{(!p)^2}\right)\)
Problème du rendu de monnaie
Comment rendre la monnaie avec le moins de pièces possible ?
Algorithme naïf
On calcule toutes les possibilités et on ne retient que la meilleure.
Exemple : somme à rendre 5, système 
Implémentation en Python
def rendu_monnaie_naif(somme, pieces = (5, 2, 1)):
if somme == 0:
return 0
nbr_pieces = somme # dans le pire des cas, on n'utilise que des pièces de 1
for piece in pieces:
if piece <= somme:
nbr_pieces = min(nbr_pieces, 1 + rendu_monnaie_naif(somme - piece, pieces))
return nbr_pieces
Complexité : exponentielle
\(\mathcal{O}\left(k^n\right)\)
Inconvénient : beaucoup trop long…
Autre exemple : cas du système de monnaie 
On peut démontrer que pour une somme à rendre \(n\), le nombre d’appels récursifs est égal à \(F_{n+3}-1\), \(F\) étant la suite de Fibonacci.
Ainsi, pour rendre 100€, il faudrait faire 1500 milliards de milliards d’appels !!!!
Alors que le calcul de la meilleure solution au problème du rendu de 100€ avec des pièces de 1€ ou 2€ est si simple qu’il peut être calculé de tête…
Algorithme glouton
L’approche gloutonne consiste à construire une solution complète par une succession de choix locaux donnant systématiquement la meilleure solution partielle.
Pour l’exemple du problème du rendu de monnaie, on choisit de rendre la plus grande pièce possible pour diminuer le plus rapidement possible la somme qui reste à rendre.
Exemple : somme à rendre 5, système
Implémentation en Python
def rendu_monnaie_glouton(somme, pieces = (5, 2, 1)):
num_piece = 0
nbr_pieces = 0
while somme > 0:
if somme >= pieces[num_piece]:
somme -= pieces[num_piece]
nbr_pieces += 1
else:
num_piece += 1
return nbr_pieces
Complexité : linéaire
\(\mathcal{T}\left(\frac{n}{k}\right)\) (\(k\) étant la valeur de la plus grande pièce)
\(\mathcal{O}\left(n\right)\)
Inconvénient : ne donne pas toujours la solution optimale.
Exemple : somme à rendre 12, système 
L’algorithme donne la solution (10, 1, 1), alors qu’il est possible de rendre la monnaie avec seulement deux pièces (6, 6).
Algorithme dynamique
Pour ne pas avoir à recalculer les résultats des solutions, on choisit de les mémoriser. On utilise pour cela une liste nbr_pieces, initialement remplie d’autant de 0 que de sommes plus petites à rendre.
Exemple : somme à rendre 5, système
Implémentation en Python
def rendu_monnaie_dyn(somme, pieces = (5, 2, 1)):
# pour mettre en mémoire les meilleurs résultats
nbr_pieces = [0] * (somme+1) # 1 résultat par valeur possible
for n in range(1, somme+1):
nbr_pieces[n] = n # pire des cas : n = n*1
for piece in pieces:
if piece <= n:
nbr_pieces[n] = min(nbr_pieces[n], 1 + nbr_pieces[n - piece])
return nbr_pieces[somme]
Complexité : linéaire
\(\mathcal{O}\left(n\right)\)
Mémoïzation
Puisque qu’un algorithme naïf conduit à recalculer plusieurs fois une même valeur, on peut conserver en mémoire, au fur et à mesure, toutes les valeurs déjà calculées afin de ne pas recommencer le calcul.
Ceci demande plus de mémoire mais permet un gain de temps.
La structure de donnée contenant les résultats mis en mémoire s’appelle le cache.
Mémoïzer une fonction consiste à la doter de cette fonctionnalité de cache.
En Python, on peut mémoïzer toute fonction de cette manière :
# Fonction de mémoïzation
def memoize(f):
cache = {} # la structure où seront mémorisés les résultats de l'appel à la fonction
def fct_memoizee(x, *args, **kargs):
if x not in cache:
cache[x] = f(x, *args, **kargs)
return cache[x]
return fct_memoizee
# Fonction à mémoïzer
def ma_fonction(n, autres_paramètres):
...
print(ma_fonction(x)) # appel à la fonction non mémoïzée
# Mémoïzation de la fonction
ma_fonction = memoize(ma_fonction)
# et voila !
print(ma_fonction(x)) # appel à la fonction mémoïzée
Remarque : pour qu’une fonction soit mémoïzable, il faut que son premier paramètre
nsoit hashable (int,str,tuple, …), car il doit servir de clé au dictionnairecache.
On peut aussi utiliser le décorateur cache du module functools :
from functools import cache
# Fonction mémoïzée
@cache
def ma_fonction(n, autres_paramètres):
...
Et c’est tout !
Sources : https://www.supinfo.com/cours/2ADS/chapitres/05-programmation-dynamique
