Fibonacci comme exemple de programmation dynamique

La récurrence de Fibonacci est

$$F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}.$$

Une récursion naïve développe plusieurs fois les mêmes sous-problèmes et prend un temps exponentiel. La mémoïsation évalue une seule fois chacun des $n+1$ états distincts au lieu de les recalculer ; une évaluation ascendante rend explicite l'ordre de leurs dépendances.

Voir l’image en grand

Les flèches vertes descendantes écrivent les résultats dans le cache ; les rouges montantes les réutilisent. Quand l’appel de droite demande F5, sa valeur est déjà enregistrée : le sous-arbre grisé n’est donc pas développé. Le schéma calcule F7 = 13 par récursion mémoïsée. La boucle ci-dessous va plus loin : elle calcule dans l’ordre et ne conserve que les deux valeurs nécessaires à l’addition suivante.

Jeff Erickson, Algorithms, figure 3.2 (p. 101) ; extrait recadré du PDF. · CC BY 4.0

def fibonacci(n: int) -> int:
    if n < 0:
        raise ValueError("n must be non-negative")
    previous, current = 0, 1
    for _ in range(n):
        previous, current = current, previous + current
    return previous

Compression de l'état

Pour calculer $F_n$, une table conserverait toutes les valeurs de $F_0$ à $F_n$. La transition ne lit que les deux précédentes : deux variables suffisent donc.

• temps : $O(n)$ opérations arithmétiques ;
• état auxiliaire : $O(1)$ variables entières ;
• la taille en bits des entiers augmente tout de même avec $n$ : pour de très grands indices, la complexité en bits d'une addition n'est pas constante.

Ce que montre cet exemple

Fibonacci aide à reconnaître les sous-problèmes qui se chevauchent et les compressions de mémoire sûres, mais ne représente pas bien les problèmes d'optimisation. En exploitant une structure algébrique supplémentaire, la méthode de doublement rapide ou les matrices calculent $F_n$ avec une profondeur de récurrence en $O(\log n)$.

Dans les exemples Python mémoïsés, évitez un dictionnaire mutable comme argument par défaut : la propriété et la durée de vie du cache doivent être explicites.

Trace et coût des entiers

Avant l'itération k, (previous, current) vaut (F_k, F_(k+1)). L'affectation simultanée préserve cet invariant ; après n itérations, previous est la réponse. Pour n=5, les paires successives sont (0,1), (1,1), (1,2), (2,3), (3,5), (5,8) : le résultat est 5. Pour n=0, la boucle ne s'exécute pas et renvoie 0 ; un n négatif est refusé. L'entrée doit être entière.

Les deux variables représentent un nombre constant d'entiers, pas un nombre constant de mots machine de taille fixe pour tout n. Les nombres de Fibonacci occupent Θ(n) bits. Avec une addition linéaire en leur taille, la boucle coûte donc O(n²) opérations sur les bits et O(n) bits auxiliaires.

assert fibonacci(0) == 0
assert fibonacci(5) == 5

Essayez un petit indice comme 6 dans l’atelier Fibonacci de l’USF, en comparant récursion, mémoïsation et tableau. Comptez les indices distincts séparément du nombre total d’appels : vous verrez ce que le cache évite avant que la boucle à deux variables supprime le tableau. La démonstration part de 1 et 1 : sa suite est décalée par rapport aux valeurs initiales 0 et 1 de cette page. Comparez surtout la réutilisation des sous-problèmes.

Source

• MIT OpenCourseWare : programmation dynamique I

Mes lectures · Les notes ouvertes sont mémorisées dans ce navigateur.