Programmation dynamique⚓︎

1. Retour sur la suite de Fibonacci⚓︎

1.1 Simple et inefficace⚓︎

la suite de Fibonacci est définie par :

• $F_0=0$
• $F_1=1$
• $\mathrm{\forall }n\in \mathbb{N},F_{n+2}=F_{n+1}+F_n$

se programme récursivement par :

1
2
3
4
5
6
7

def fibo(n):
    if n == 0 :
        return 0   
    elif n == 1 :
        return 1
    else :
        return fibo(n-1) + fibo(n-2)

Ce code, d'une grande simplicité, est malheureusement très inefficace.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import time

def fibo(n):
    if n == 0 :
        return 0   
    elif n == 1 :
        return 1
    else :
        return fibo(n-1) + fibo(n-2)

t0 = time.time()
fibo(40)
print(time.time() - t0)

En cause : la multitude des appels récursifs nous conduit à refaire des calculs déjà effectués.

Observons l'arbre d'appels de fibo(6) :

Le calcul de fibo(2) se retrouve ainsi 5 fois dans l'arbre.

Pour résoudre notre problème, nous l'avons divisé en problèmes plus petits, mais malheureusement pas indépendants : on dit que les problèmes se recouvrent, ce qui nous amène à refaire des choses déjà faites.

Dans l'algorithme de dichotomie, ou du tri-fusion, les problèmes étaient indépendants et ne se recouvraient pas : on ne refaisait jamais deux fois la même chose. Ce n'est pas le cas ici.

1.2 Se souvenir des belles choses des calculs : la mémoïsation⚓︎

Comment éviter de recalculer (par exemple) 5 fois fibo(2) ?

L'idée générale est de stocker le résultat de chaque calcul, par exemple dans un dictionnaire. Ainsi, à chaque demande de calcul :

• Soit le calcul a déjà été effectué : on a donc juste à le lire dans le dictionnaire.
• Soit le calcul n'a jamais été effectué : on l'effectue, et on stocke le résultat dans le dictionnaire.

1
2
3
4
5
6

dict_fibo = {0:0, 1:1}
def fibo(n):
    if n in dict_fibo:
        return ...
    dict_fibo[n] = ... + ...
    return ...

1
2
3
4
5
6

    dict_fibo = {0:0, 1:1}
    def fibo(n):
        if n in dict_fibo:
            return dict_fibo[n]
        dict_fibo[n] = fibo(n-1) + fibo(n-2)
        return dict_fibo[n]

1.3 Quelques remarques⚓︎

1.3.1 Juste une brute-force plus efficace ?⚓︎

Notre technique de mémoïsation ne change pas vraiment la structure du programme : on continue de calculer toutes les valeurs intermédiaires, mais on ne les calcule qu'une seule fois.

1.3.2 Suppression de la variable globale⚓︎

Dans le code précédent, le dictionnaire dict_fibo est à l'extérieur de la fonction. Un dictionnaire étant un type mutable, sa modification à l'intérieur de la fonction ne pose pas de problème. Toutefois, ce genre de pratique est déconseillé : si par exemple on appelle 2 fois la fonction fibo, le dictionnaire n'est pas réinitialisé entre-temps (ce qui dans notre cas n'est pas problématique, mais cela pourrait l'être). Comment éviter cela ?

On peut utiliser une fonction englobante (appelée ici fibonacci ) :

1
2
3
4
5
6
7
8

def fibonacci(n):
    dict_fibo = {0:0, 1:1}
    def fibo(n):
        if n in dict_fibo:
            return dict_fibo[n]
        dict_fibo[n] = fibo(n-1) + fibo(n-2)
        return dict_fibo[n]
    return fibo(n)

>>> fibonacci(50)
12586269025

Remarquez la définition d'une fonction à l'intérieur d'une autre. Cela ne pose aucun problème, mais attention, cette fonction n'existe pas à l'extérieur de sa fonction englobante.

1.3.3 Mémoïsation automatique en Python ⚓︎

La fonction lru_cache du module functools permet de mémoïser automatiquement une fonction récursive. Il suffit, juste avant d'écrire la fonction, de mettre la ligne @lru_cache (appelée décorateur).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import time
from functools import lru_cache

@lru_cache  #
def fibo(n): #
    if n == 0 :
        return 0   
    elif n == 1 :
        return 1
    else :
        return fibo(n-1) + fibo(n-2)

t0 = time.time()
fibo(35)
print(time.time() - t0)

Essayez en commentant / décommentant la ligne 4... c'est magique !

1.4 De bas en haut⚓︎

La structure récursive naturelle de la suite de Fibonacci nous a conduit vers un programme qui calcule (ou plutôt appelle) les valeurs de haut en bas. (méthode top-down)

Et si on commençait par le bas ?

Si nous devions calculer mentalement le 6ème terme de la suite de Fibonacci, on commencerait par calculer le 3ème, puis le 4ème, puis le 5ème et enfin le 6ème.

1
2
3
4
5
6
7

 def fibo(n):
    dict_fibo = {}
    dict_fibo[0] = ...
    dict_fibo[1] = ...
    for k in range(..., ...):
        dict_fibo[k] = dict_fibo[...] + dict_fibo[...]
    return dict_fibo[...]

1
2
3
4
5
6
7

def fibo(n):
    dict_fibo = {}
    dict_fibo[0] = 0
    dict_fibo[1] = 1
    for k in range(2, n+1):
        dict_fibo[k] = dict_fibo[k-1] + dict_fibo[k-2]
    return dict_fibo[n]

Cette méthode itérative part du bas pour aller vers le haut. On parle de méthode bottom-up. De manière plus générale, cette méthode est basée sur le fait de résoudre des problèmes de petite taille, puis de plus en plus gros, jusqu'au problème final.

1.5 Bilan des méthodes employées⚓︎

2. Programmation dynamique et optimisation⚓︎

2.1 Optimisation d'une somme dans une pyramide⚓︎

La suite : TP Pyramides

2.2 Optimisation du rendu de monnaie⚓︎

La suite : TP Rendu de monnaie

Entrainement : Énumération des permutationsDifficulté :

Entrainement : Nombre de chemins dans une grilleDifficulté :