En début d’année nous avons étudié la récursivité. Nous allons reprendre l’exemple de la suite de Fibonacci.
Les différents appels de fonction (en mémoire vive) :
On constate que de nombreux appels de fonctions sont répétés plusieurs fois.
Nous allons étudier une méthode algorithmique appelée programmation dynamique qui va permettre de réutiliser des solutions de sous problèmes après avoir stocké les résultats intermédiaires.
1) Programmation dynamique¶
La programmation dynamique a été introduite par Richard Bellman au début des années 1950.
Programmation
Attention programmation signifie planification et n’a rien avoir avec un langage de programmation.
Une des différences entre la programmation dynamique et l’approche diviser pour régner, est que dans le cas de la programmation dynamique les sous problèmes ont des problèmes communs et sont donc dépendant les un des autres.
Par exemple, dans le calcul de la suite de Fibonacci, fib(4) et fib(3) ont des sous problèmes communs, puisque pour calculer fib(4) j’ai besoin de fib(2) et fib(1) et c’est également le cas pour calculer fib(3).
Il y a deux types d’approches :
- Descendante (de haut en bas)
- Ascendante (de bas en haut)
1.1) Approche descendante et mémoïsation¶
Dans cas de l’approche descendante on effectue les appels récursifs et on stocke (typiquement dans un tableau associatif) les résultats intermédiaires. On parle dans ce cas de mémoïsation, dérivé du mot anglais memo (qui a lui-même une origine latine) pour pense-bête.
Exemple
Pour calculer le cinquième terme de la suite de Fibonacci, on commence par calculer fib(5), ensuite on calcule f(4) et f(3), et on stocke les résultats au fur et à mesure pour ne pas avoir à les recalculer :
memo_fib = {0: 0, 1: 1}
def fib(n):
if n not in memo_fib:
memo_fib[n] = fib(n -1) + fib(n - 2)
return memo_fib[n]
On peut également rencontrer par moment une liste que l’on initialise dans une fonction (appelée une seule fois) qui elle même inclut une autre fonction (qui elles peut être appelée plusieurs fois) :
def fibo(n) :
memo_fib = [0, 1] + [None] * (n - 1)
def calculer(n, memo_fib) :
if memo_fib[n] is None :
memo_fib[n] = calculer(n - 1, memo_fib) + calculer(n - 2, memo_fib)
return memo_fib[n]
return calculer(n, memo_fib)
1.2) Approche ascendante¶
Dans l’approche ascendante on n’effectue pas d’appels récursifs. On part des données initiales du problèmes et on itère progressivement en partant des solutions correspondant aux plus petits sous problèmes et en remontant petit à petit jusqu’à aboutir à la solution du problème général.
Exemple
def fibo(n) :
fib_n = [0, 1] + [0] * (n - 1)
for i in range(2, n + 1):
fib_n[i] = fib_n[i - 1] + fib_n[i - 2]
return fib_n[n]
Vous noterez en particulier qu’il n’y a pas d’appels récursifs dans cette version.
Revenons sur un autre exemple, celui du problème de rendu de monnaie vu en première.
2) Programmation dynamique et rendu de monnaie¶
En première nous avons étudié un algorithme glouton pour résoudre ce problème.
Un énoncé du problème de rendu de monnaie
Vous avez à votre disposition un nombre illimité de pièces de 2 cts, 5 cts, 10 cts, 50 cts et 1 euro (100 cts). Vous devez rendre une certaine somme (rendu de monnaie).
Le problème est le suivant : "Quel est le nombre minimum de pièces qui doivent être utilisées pour rendre la monnaie"
Dans le cas d’un algorithme glouton, on cherche une solution locale étape par étape en essayant d’obtenir un optimum global.
Un algorithme glouton pour le problème de rendu de monnaie consiste à essayer à chaque fois avec la plus grande pièce telle que la valeur de cette pièce soit inférieur ou égale à la monnaie restant à rendre jusqu’à ce que la somme à rendre soit nulle.
- Appliquer cette méthode pour une somme de 1 € 57 (157cts) à rendre.
- Appliquer cette méthode à la somme de 21 centimes.
- Quel est le problème ?
- Proposer une solution permettant de rendre 21 centimes.
Nous allons commencer par résoudre ce problème en utilisant un algorithme récursif, sans optimisation. Pour cela, on va s’appuyer sur une relation de récurrence. Ce sera difficile au début, mais c’est cet effort d’abstraction qui va nous permettre de résoudre ce problème de manière élégante et efficace.
Exemples préalables
On doit rendre 2 centimes en utilisant un minimum de pièces avec les pièces suivantes : 1 centime, 2 centimes.
Explication intuitive
Si je peux rendre 2 centimes, je peux aussi rendre 2 - 1 = 1 centime et j’aurai utilisé une pièce (d’où le plus un), mais il me restera encore 1 dernier centime à rendre, en répétant l’opération j’utiliserai une nouvelle pièce de 1 centime et finalement j’arriverai au cas de base : il me restera 0 centime à rendre. Au total j’aurai donc utilisé deux pièces.
Si je peux aussi rendre 2 centimes, je peux aussi rendre 2 - 2 = 0 centime et j’aurai utilisé une seule pièce et j’arriverai au cas de base : il me restera 0 centime à rendre. Au total j’aurai donc utilisé une seule pièce.
Explication formelle
Soit s la somme à rendre. On note P(s) le nombre minimum de pièces à rendre pour une certaine somme s. Soit \({p_{1}, p_{2}, \dots, p_{n}}\) l’ensemble des pièces que je peux utiliser.
Dans notre exemple, on a : \(p_{1} = 1, p_{2} = 2\)
s = 2 (la somme que l’on doit rendre)
Si on choisit la première pièce
P(s - 1) = P(2 - 1) = P(1), on a alors utilisé une pièce pour arriver à la somme s. Mais il nous reste encore un centime à rendre, donc maintenant s = 1 on utilise donc à nouveau une pièce de un centime, avant d’arriver au cas où s = 0 et là on a plus de pièces à utiliser. On a donc utilisé au total 2 pièces de 1 centimes.
Si on choisit la deuxième pièce
P(s - 2) = 0 (On a pas de pièce à utiliser lorsqu’il ne reste rien à rendre). On ajoute alors une pièce uniquement pour obtenir la somme s : la pièce de deux centimes.
On prend le minimum des deux cas possibles, soit le cas où on utilise une pièce de 2 centimes.
Formellement le raisonnement que l’on a effectué peut se résumer de manière synthétique par cette formule :
\(P(s) = min( P(2 - 2), P(2 - 1)) + 1\)
Sous forme arborescente, cela donne :
Évidemment ce cas là ne représente pas un cas intéressant pour la résolution par la programmation dynamique, mais est utilisé uniquement dans le but de définir le problème de manière récursive.
Nous allons maintenant généraliser le résultat précédent.
En supposant que la valeur de la ième pièce que l’on note \(p_{i}\) soit inférieure ou égale à la somme restant à rendre, alors après avoir utilisé cette pièce, il restera \(s - p_{i}\) monnaie à rendre.
Si s = 0 alors on a pas besoin de pièces supplémentaires et donc : P(s) = 0
Si s > 0 alors : P(s) = min(P(s - \(p_{i}\) )) + 1 avec \(1 \leq i < n\) et \(p_{i} \leq s\)
Cela signifie qu’à chaque étape on reprend la solution optimale précédente et on ajoute une nouvelle pièce. Maintenant, nous pouvons implémenter cet algorithme en Python de manière récursive :
def rendu_monnaie(pieces, somme):
if somme == 0:
return 0
else:
nb_mini = 10000
for i in range(len(pieces)):
if pieces[i] <= somme:
nb_pieces = 1 + rendu_monnaie(pieces, somme - pieces[i])
if nb_pieces < nb_mini:
nb_mini = nb_pieces
return nb_mini
pieces = (3,5,10,50,100)
Par exemple, dans ce cas :
On ne peut pas rendre 7 centimes avec l'ensemble des pièces que l'on a et alors la valeur 10000 sera renvoyée.
Maintenant que l'on a une version récursive qui fonctionne on peut utiliser l'approche descendante et stocker les résultats intermédiaires.
En effet il faut bien voir que comme pour le calcul des termes de la suite de Fibonacci, de nombreux calculs seront potentiellement répétés inutilement (schéma extrait de : https://pixees.fr/informatiquelycee/n_site/nsi_term_algo_progdyn.html ):
En utilisant un dictionnaire pour stocker les résultats intermédiaires, nous obtenons alors :
def rendu_monnaie():
memo = {}
pieces = (3,5,10,50,100)
somme = 2000
def calcul_rendu_monnaie(pieces, somme):
if somme == 0:
return 0
else:
nb_mini = 10000
for i in range(len(pieces)):
if pieces[i] <= somme:
if somme - pieces[i] not in memo:
memo[somme - pieces[i]] = 1 + calcul_rendu_monnaie(pieces, somme - pieces[i])
elif memo[somme - pieces[i]] < nb_mini:
nb_mini = memo[somme - pieces[i]]
return nb_mini
return calcul_rendu_monnaie(pieces, somme)
Il est parfois difficile de reconnaître une situation où la programmation dynamique peut être utile. En TP nous étudierons des cas suffisamment variés.