Fibonacci et programmation dynamique
Demandez à un ordinateur le 40e nombre de Fibonacci de la façon la plus évidente, et il fait plus de 331 millions d'appels. Demandez-le-lui avec un tableau, et il lui suffit de 39 additions. La différence, c'est la programmation dynamique, et c'est avec les nombres de Fibonacci que presque tout le monde la découvre.
Le problème
Les nombres de Fibonacci commencent par 0, 1, et chaque nombre suivant est la somme des deux précédents : 0, 1, 1, 2, 3, 5, 8, 13, 21, etc. Sous forme de règle : F(0) = 0, F(1) = 1 et F(n) = F(n − 1) + F(n − 2). La règle est récursive, et la traduire directement en programme récursif est facile, mais ce programme se révèle très lent.
Pourquoi la récursion se répète
Pour trouver F(5), le programme demande F(4) et F(3). F(4) demande F(3) et F(2), donc F(3) est calculé deux fois, F(2) trois fois et F(1) cinq fois. Dessinés sous forme d'arbre, les appels doublent presque à chaque niveau, et le total pour F(n) est de 2·F(n + 1) − 1 appels. Les problèmes plus petits se chevauchent : les mêmes reviennent encore et encore. C'est le signe que la programmation dynamique va aider.
Deux façons de se souvenir
La mémoïsation garde la récursion mais écrit chaque réponse dans un tableau, et chaque appel regarde dans le tableau avant de faire le moindre calcul. La tabulation remplit le tableau de bas en haut : F(0) et F(1) d'abord, puis F(2) à partir d'eux, F(3) à partir de F(2) et F(1), et ainsi de suite jusqu'à F(n). Dans les deux cas, chaque terme est calculé une fois, donc F(n) coûte n − 1 additions au lieu d'un nombre exponentiel d'appels.
Un exemple
Avec la méthode ascendante pour F(7) : on part de 0 et 1. Puis 0 + 1 = 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8 et 5 + 8 = 13, donc F(7) = 13 après six additions. La récursion simple ferait 2·F(8) − 1 = 41 appels pour la même réponse. Avec la méthode descendante, les premiers appels descendent jusqu'à F(1) le long du bord gauche de l'arbre ; à la remontée, presque un appel sur deux trouve sa réponse déjà dans le tableau.
D'où vient le nom
Richard Bellman a donné son nom à la programmation dynamique au début des années 1950, alors qu'il travaillait à la RAND Corporation. Il a écrit plus tard qu'il avait choisi « programmation » au sens ancien de planification, et « dynamique » parce que cela sonnait de façon impressionnante et qu'il était difficile d'y trouver à redire. La méthode elle-même, résoudre un problème grâce aux réponses de versions plus petites de ce problème, tourne aujourd'hui dans les correcteurs orthographiques, les calculateurs d'itinéraire et la comparaison d'ADN.
À vous d'explorer
Ouvrez l'application et appuyez sur Étape. Avec Ascendante, la case orange est celle en cours de remplissage et les deux cases bleues sont les termes qu'elle additionne. Passez à Descendante et regardez la pile d'appels sous le tableau grandir jusqu'à n, puis rétrécir à mesure que les réponses reviennent ; l'indication sous Additions compte combien d'appels ont trouvé leur réponse directement dans le tableau.
Questions fréquemment posées
Que sont les sous-problèmes qui se chevauchent ?
Des problèmes plus petits dont une solution a besoin plus d'une fois. F(n) et F(n − 1) ont tous deux besoin de F(n − 2), donc la récursion simple le calcule deux fois, et le gaspillage se multiplie plus bas. La programmation dynamique résout chacun une seule fois et retient la réponse.
La mémoïsation est-elle plus rapide que la tabulation ?
Elles font les mêmes additions. La tabulation est en général un peu plus rapide parce qu'elle ne fait aucun appel, et elle ne peut pas épuiser la pile ; la mémoïsation est pratique quand seules certaines des réponses plus petites sont nécessaires, car elle ne calcule que celles-là.
Peut-on calculer les nombres de Fibonacci encore plus vite ?
Oui. Avec F(2k) = F(k)·(2·F(k + 1) − F(k)) et F(2k + 1) = F(k)² + F(k + 1)², la méthode du doublement rapide n'a besoin que d'environ log₂ n étapes. La formule de Binet, avec le nombre d'or, donne les mêmes nombres, mais les erreurs d'arrondi la rendent peu fiable pour les grands n.
De combien de mémoire le tableau a-t-il besoin ?
Un tableau complet contient n + 1 nombres, mais chaque nouveau terme n'a besoin que des deux précédents, donc une boucle qui garde deux nombres fait le même travail en mémoire constante. Garder tout le tableau est utile quand on veut tous les termes, ou pour voir comment la méthode fonctionne.
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Essayer Fibonacci par programmation dynamique