La programmation dynamique n’est pas de la magie noire

 (qsantos.fr)
2 points par GN⁺ 2024-01-15 | 1 commentaires | Partager sur WhatsApp
  • Même des problèmes avec beaucoup de cas particuliers, comme l’Advent of Code 2023 Day 12, peuvent être traités avec la programmation dynamique dès lors qu’on repère une structure qui résout plusieurs fois les mêmes sous-problèmes
  • L’idée clé consiste à découper le problème de façon récursive, puis à réduire les calculs redondants par mémoïsation, avant de le transformer en calcul itératif en remplissant les valeurs nécessaires selon leur ordre de dépendance
  • L’exemple de Fibonacci montre qu’une récursion naïve réévalue f(1) de nombreuses fois, alors qu’avec un cache il suffit d’évaluer seulement n + 1 valeurs, de f(0) à f(n)
  • La distance de Levenshtein et l’Advent of Code Day 12 montrent comment utiliser comme clés de cache des indices d’état tels que la longueur de chaîne ou l’index d’une règle, puis convertir les appels récursifs en remplissage de tableau
  • Maîtriser la programmation dynamique permet non seulement d’améliorer les performances, mais aussi de mieux voir les états intermédiaires et les dépendances d’un algorithme, ce qui facilite aussi les optimisations mémoire

Le nom prête à confusion, mais l’idée est simple

  • Le terme “dynamic programming” n’a pas de lien direct avec les sens modernes de “programmation”, comme un style de programmation ou le typage dynamique
  • L’essentiel est une manière de concevoir un algorithme en découpant un problème en plus petits problèmes similaires, puis en réutilisant leurs résultats
  • Une note éditoriale ajoute que l’expression devient logique si l’on se réfère au sens historique de “programming”
  • Le point de départ est souvent une fonction récursive, qui décompose le problème en sous-problèmes plus petits
  • Quand le même sous-problème apparaît plusieurs fois, il devient naturel d’enregistrer le résultat du calcul pour le réutiliser via du caching

Caching et itération à travers Fibonacci

  • La fonction de Fibonacci est définie par f(n) = f(n - 1) + f(n - 2), et une implémentation récursive naïve recalcule plusieurs fois les mêmes valeurs
  • f(1) contribue réellement au résultat final, donc à mesure que f(n) grandit, le nombre d’évaluations dans la récursion naïve augmente très vite
  • Avec un cache ou la mémoïsation, il n’est plus nécessaire de recalculer f(4), f(3) ou f(2) une fois qu’ils ont déjà été obtenus
  • Dans cette approche, on n’évalue au total que 7 valeurs de f(0) à f(6), et plus généralement cela se ramène à n + 1 évaluations
  • En allant une étape plus loin, on peut remplir les valeurs nécessaires dans l’ordre à partir de f(0) et f(1), ce qui élimine les appels récursifs
    • F[2] = F[1] + F[0]
    • F[3] = F[2] + F[1]
    • et de la même manière jusqu’à F[6] = 8
  • Pour Fibonacci, le tableau complet n’est même pas nécessaire : il suffit de conserver la valeur précédente et celle d’avant
  • Cette progression montre un chemin systématique allant de la définition mathématique vers une implémentation itérative

Étendre l’idée avec la distance d’édition

  • La distance d’édition entre deux chaînes est le nombre minimal de modifications nécessaires pour transformer l’une en l’autre
  • Le problème varie selon les types de modifications autorisées
    • Si seules les substitutions de caractères sont permises, on obtient la distance de Hamming
    • Si l’on autorise aussi les insertions et suppressions, on obtient la distance de Levenshtein
  • La distance de Levenshtein entre deux chaînes A et B peut être découpée en plus petits problèmes à partir de leur dernier caractère
    • Si les derniers caractères sont identiques, on les ignore et on utilise la distance sur le reste des chaînes
    • S’ils diffèrent, on choisit le coût minimal entre substitution, suppression et insertion
    • Si A est vide, il faut insérer tous les caractères de B, donc le coût vaut b
    • Si B est vide, il faut supprimer tous les caractères de A, donc le coût vaut a
  • Si l’on traduit directement cette définition en récursion Python, cela devient très lent sur les longues chaînes et sur celles qui diffèrent beaucoup
  • Là où Fibonacci se ramifie approximativement en deux appels à chaque niveau de l’arbre, cette récursion peut, selon les cas, se ramifier en trois
  • En Python, ajouter functools.cache permet de réutiliser les résultats calculés pour les mêmes combinaisons de sous-chaînes
  • Une meilleure implémentation consiste à ne plus créer sans cesse de nouvelles chaînes, mais à ne transmettre que les chaînes d’origine A, B et les longueurs de sous-chaînes a, b
  • À l’étape suivante, on construit directement un tableau 2D cache et on le remplit dans l’ordre voulu de sorte que cache[a][b] = levenstein(A[:a], B[:b])
  • La version itérative parcourt a et b de 0 jusqu’à la longueur des chaînes, en réutilisant les valeurs déjà remplies sur la ligne précédente et la colonne précédente

Application à Advent of Code 2023 Day 12

  • Le problème du 12 décembre 2023 d’Advent of Code consiste à résoudre un nonogramme en une dimension
  • Un exemple d’entrée a la forme .??..??...?##. 1,1,3, où ? peut devenir . ou #
  • Une approche par force brute utilise le backtracking, mais avec n points d’interrogation il faut évaluer 2^n candidats, ce qui devient exponentiel
  • On y retrouve une structure avec répétition des mêmes sous-problèmes
    • ..#..??...?##. (1),1,3
    • .#...??...?##. (1),1,3
    • Si l’on écarte la partie déjà traitée, on obtient dans les deux cas des problèmes presque identiques, comme .??...?##. 1,3 et ..??...?##. 1,3
  • La fonction de backtracking de base prend conditions et rules et calcule le nombre de placements possibles
    • S’il ne reste plus de règles, elle vérifie s’il reste un # dans les conditions
    • S’il ne reste plus de conditions, elle vérifie s’il reste encore des règles
    • Si le caractère courant est . ou ?, elle avance d’une case
    • Si le caractère courant est # ou ?, elle vérifie la taille de la règle suivante et les conditions de séparation, puis passe à l’état suivant
  • En Python, il suffit d’ajouter @cache pour appliquer la mémoïsation
  • Pour passer à la programmation dynamique, on ne transmet plus des sous-chaînes ni des sous-listes de règles, mais on utilise comme état l’offset i dans la chaîne et l’offset j dans les règles
  • On construit ensuite directement cache[i][j] et on remplace la récursion par un calcul itératif en remplissant les indices en ordre inverse
  • Un exemple d’implémentation en Rust est fourni dans le lien Rust implementation

Ce qu’on voit en remplissant soi-même le cache

  • La version en programmation dynamique de l’Advent of Code Day 12 peut sembler plus lente que la version avec mémoïsation
  • Cette différence peut venir d’une implémentation Python non optimisée
  • Construire soi-même le cache permet de mieux voir quelles valeurs sont réellement nécessaires
  • Dans le problème Day 12, la version en programmation dynamique montre qu’on n’a besoin que de la colonne précédente
  • On peut donc remplacer le tableau 2D par deux tableaux 1D représentant la colonne précédente et la colonne courante

Problèmes pour s’entraîner et conclusion

  • La programmation dynamique n’est pas triviale, mais ce n’est pas non plus une technique inaccessible à la plupart des programmeurs
  • Une fois qu’on comprend comment découper un problème en petits problèmes, la seule mémoïsation permet déjà souvent de faire un grand bond par rapport à une implémentation naïve
  • Avec plus d’expérience, on comprend mieux toute une famille d’algorithmes, on cerne mieux les compromis et on repère plus facilement d’autres optimisations
  • Les problèmes suivants sont proposés comme exercices
  • Après l’implémentation, il ne faut pas oublier les benchmarks et le profiling

À lire aussi

1 commentaires

 
GN⁺ 2024-01-15
Commentaires sur Hacker News

  • J’ai apprécié que l’article souligne qu’un algorithme de programmation dynamique n’est souvent qu’une manière astucieuse de mettre en cache une récursion. D’après mon expérience, trouver d’abord une solution récursive est le meilleur point de départ pour trouver une solution en programmation dynamique, et une fois cette solution trouvée, la mémoïsation est facile à ajouter et peut apporter un gros gain de performances
    Cela peut même être plus rapide qu’une programmation dynamique ascendante, car on ne calcule que les solutions réellement nécessaires. Le point clé, c’est qu’il peut y avoir beaucoup de sous-problèmes dans l’arbre d’appels, mais que le nombre de sous-problèmes distincts doit rester relativement faible. Il n’y a aucune raison de mettre en cache un résultat dont on n’a besoin qu’une seule fois, et il est difficile de découper le problème d’origine en un nombre suffisamment réduit de sous-problèmes distincts

    • Le point essentiel, c’est bien que le nombre de sous-problèmes distincts doit rester relativement faible. Que l’algorithme global soit récursif ou itératif est secondaire, et la programmation dynamique apparaît souvent plus naturellement dans les algorithmes récursifs
    • La formule « la programmation dynamique, c’est une manière de mettre en cache la récursion » a été pour moi le vrai déclic. À l’université, comme la programmation procédurale dominait à l’époque, les exemples de remplissage de tableaux en bottom-up dans les manuels me semblaient relever de la magie
      En pratique, comme l’élimination des appels terminaux n’est pas toujours appliquée, cette approche se défend, mais j’aurais aimé commencer par la vision plus intuitive d’une récursion top-down avec cache
    • Quand je l’ai appris au début, je me suis dit que si c’était une technique aussi sophistiquée, on devrait plutôt l’appeler mémoïsation par tableau ou mémoïsation de pile d’appels. À mon avis, le nom « programmation dynamique » aurait dû être réservé à quelque chose de mieux
    • Je pense que voir la programmation dynamique comme une simple récursion mémoïsée est un malentendu très répandu. Si on l’apprend comme ça, il devient très difficile de comprendre les problèmes de programmation dynamique du type remplissage de tableau en 2D
      Par exemple, dans la série LeetCode « Best Time to Buy and Sell Stock », pour un problème comme https://leetcode.com/problems/best-time-to-buy-and-sell-stoc..., l’approche par remplissage de tableau ne paraît-elle pas beaucoup plus naturelle ? Je ne l’ai jamais résolu par récursion, et je ne sais même pas s’il existe une solution récursive naturelle
      Le lien ci-dessus pointe vers le III, mais pour quelqu’un qui débute, commencer par le premier problème https://leetcode.com/problems/best-time-to-buy-and-sell-stoc... est une bonne introduction à la programmation dynamique
    • Dire que « la programmation dynamique, c’est juste du cache / de la mémoïsation », c’est un peu comme dire que « l’investissement, c’est simplement acheter quelque chose puis le revendre plus tard ». C’est peut-être techniquement vrai dans une certaine mesure, mais cela passe tellement à côté de la complexité et de la difficulté du sujet que cela en devient plus risible qu’éclairant

  • L’origine du nom « programmation dynamique » vient de son inventeur, Richard Bellman. Dans les années 1950 à la RAND, il cherchait un nom pour un processus de décision multi-étapes, et le secrétaire à la Défense de l’époque, Wilson, détestait pathologiquement le mot « recherche », tandis que le mot « mathématiques » était encore plus à éviter
    Bellman avait besoin d’un nom qui cache à Wilson et à l’US Air Force le fait qu’il faisait en réalité des mathématiques à la RAND. Comme il s’agissait de planification, de prise de décision et de réflexion, mais que « planning » ne convenait pas pour diverses raisons, il a choisi « programming », puis lui a accolé « dynamic », un terme ayant un sens précis en physique classique, pour exprimer l’idée de multi-étapes et d’évolution dans le temps
    Il appréciait aussi le fait que « dynamic », en tant qu’adjectif, se prête difficilement à une interprétation négative, et que même un élu aurait du mal à s’y opposer ; il a donc utilisé dynamic programming comme nom englobant son activité
    Source : https://alliance.seas.upenn.edu/~cis520/dynamic/2021/wiki/in...

  • J’aime la manière dont cet article commence par faire émerger le problème récursivement, puis ajoute progressivement du cache, avant de finir par réduire la taille du cache au strict nécessaire
    J’ai souvent essayé de sauter directement à la solution de programmation dynamique et je me suis retrouvé bloqué, ou à forcer les choses pour que ça fonctionne. À l’avenir, je pense m’obliger à suivre les étapes dans l’ordre

    • D’après mon expérience, enseigner directement la programmation dynamique donne l’impression d’un puzzle. Quand on explique pourquoi on utilise un tableau en passant par des étapes intermédiaires, puis qu’on relie cela au cache, la compréhension est bien meilleure

  • L’une des applications les plus élégantes de la programmation dynamique est l’alignement pair à pair de séquences de nucléotides ou de protéines
    https://en.wikipedia.org/wiki/Sequence_alignment
    https://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algor...
    https://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorit...

    • Je considère que ces algorithmes font partie des plus importants en bioinformatique / biologie. Leur champ d’application est extrêmement vaste

  • Il y avait un excellent professeur d’algorithmique, qui avait étudié à UCLA. Son cours sur la programmation dynamique était remarquable : il commençait par un problème dont la solution naïve avait une complexité temporelle exponentielle, puis divisait le problème en sous-problèmes plus petits pour ramener la complexité à un niveau polynomial, avant d’appliquer la mémoïsation pour la faire tomber à un niveau linéaire
    J’aimerais bien me souvenir des problèmes utilisés à ce moment-là

    • Parmi les candidats possibles : la suite de Fibonacci, le problème du rendu de monnaie, le problème du sac à dos 0/1, la multiplication chaînée de matrices, la plus longue sous-séquence commune, la plus longue sous-séquence croissante, des problèmes de plus court chemin comme Floyd-Warshall, ou encore la distance d’édition (distance de Levenshtein)
      Ce sont tous des exemples classiques où la solution naïve est inefficace et où la programmation dynamique apporte une amélioration majeure
    • Quelques-uns sont aussi mentionnés dans l’article, et ce sont des problèmes qu’on voit souvent en cours ou en travaux pratiques. Par exemple : la plus longue sous-séquence commune, la plus longue sous-chaîne commune, line warp, la somme de sous-ensembles, le partitionnement et le problème du sac à dos
      Pour plus d’exemples, voir https://en.wikipedia.org/wiki/Dynamic_programming#Algorithms...
    • En plus des problèmes proposés par les autres, cela pouvait aussi être un problème d’ordonnancement. Par exemple, optimiser selon un critère comme le débit le traitement de N événements qui se chevauchent dans le temps, comme des emplois du temps de cours ou des processus CPU
      J’ai l’impression que si on ajoute des contraintes particulières, comme « ces deux cours doivent être suivis ensemble », cela devient bien plus complexe et difficile à traiter qu’une programmation dynamique ordinaire
    • C’était quelqu’un qui avait étudié à UCLA sous la direction de Kang ?

  • Le site d’origine semble ne pas tenir la charge, donc je laisse un lien d’archive
    https://web.archive.org/web/20240114111200/https://qsantos.f...

  • Grâce à la programmation dynamique, on a pu calculer le nombre de positions légales au go, et c’était un nombre de 171 chiffres
    Une approche naïve prend 3^(n^2) de temps, car elle examine toutes les positions possibles sur un goban n×n, mais la programmation dynamique élimine en pratique une dimension entière et ramène la complexité temporelle à O(n^5 * 5.4^n), avec une complexité spatiale de O(n * 5.4^n)
    https://tromp.github.io/go/legal.html
    https://tromp.github.io/go/gostate.pdf

  • Le nom « Dynamic Programming » peut paraître étrange, parce qu’ici programming ne renvoie pas au domaine de la programmation informatique. Dans ce cas, le sens est plus proche de la programmation linéaire, donc de l’optimisation
    On peut voir la programmation dynamique comme une méthode pour résoudre des problèmes de décision en temps discret, c’est-à-dire des problèmes où l’on choisit une séquence optimale {a_t} maximisant \sum_t u_t(a_t) sous contraintes. On définit alors une fonction de valeur V* par V*(t) = max_{a_t}{ u_t(a_t) + V*(t-1) }, ce qui permet de réduire fortement la dimension du problème d’optimisation

    • En réalité, l’origine officielle du nom https://en.wikipedia.org/wiki/Dynamic_programming#History est assez drôle. Bellman trouvait que « dynamic » était un adjectif qu’on ne pouvait pas utiliser avec une connotation négative, et pensait que même un élu ne pourrait pas s’y opposer
    • Quand d’autres personnes utilisent le terme « programmation dynamique », on a parfois l’impression qu’elles cherchent surtout à paraître intelligentes. En réalité, elles ont simplement adopté une approche naturelle et intuitive consistant à remarquer qu’on pouvait décomposer le problème en sous-problèmes de plus en plus petits, puis elles présentent cela comme si elles avaient « appliqué » une technique spéciale
    • Il est intéressant de voir qu’autrefois, calculer quelque chose, comme dans les problèmes d’optimisation, occupait une place bien plus centrale dans ce qu’on imaginait faire avec un ordinateur. Aujourd’hui, on fait surtout du stockage et de la récupération de données, ainsi que du réseau ; et même quand il y a du calcul dedans, il semble en général bien encapsulé
    • Le mot « optimisation » prête lui aussi à malentendu, d’une manière similaire. J’ai déjà suivi un cours d’informatique intitulé « optimization » en m’attendant à quelque chose de totalement différent
    • Si l’on remonte encore plus loin, le mot « programming » décrit en fait assez précisément le concept. Ce que nous appelons aujourd’hui « programmer », c’est en réalité écrire du code, et cela peut se répartir entre plusieurs branches de la programmation, comme le fonctionnel, le déclaratif ou le procédural. Il y a bien plus de choses encore sous cette grande bannière

  • Quand on entend « programmation dynamique », est-ce faux de simplement penser à la mémoïsation ? Ce qui manque, c’est peut-être le fait de découper intelligemment le problème pour pouvoir utiliser la mémoïsation

    • La mémoïsation est une technique plus générale. Souvent, elle consiste simplement à mettre en cache des résultats déjà calculés au cas où on en aurait de nouveau besoin plus tard
      La programmation dynamique se rapproche plutôt d’une mémoïsation systématique. On résout des sous-problèmes de plus en plus grands pour atteindre la solution du problème global. L’expression « algorithme inductif » conviendrait d’ailleurs assez bien, car un algorithme classique de programmation dynamique ressemble en pratique à une preuve par récurrence mathématique. Malheureusement, ce terme a déjà d’autres sens
    • C’est exactement comme cela que j’enseigne la programmation dynamique. On commence par résoudre le problème de façon récursive, puis on ajoute la mémoïsation. On appelle cela l’approche top-down
      Ensuite, on constate que la récursion et la mémoïsation ont un certain surcoût ; si l’on construit alors un tableau de bas en haut et qu’on élimine les appels récursifs, on obtient de la programmation dynamique
    • Dans mon approche, la mémoïsation est l’étape 2 sur 3 de la programmation dynamique. L’étape 1 consiste à trouver un algorithme récursif, l’étape 2 à ajouter la mémoïsation, et l’étape 3 à le transformer en version itérative / bottom-up, avec si possible une étape 3b d’optimisation de l’espace
      L’étape 3 est la partie la plus caractéristique de la programmation dynamique, mais on peut à mon avis tout de même parler de programmation dynamique si l’on s’arrête à l’étape 2. C’est simplement moins efficace que possible. Autrement dit, la mémoïsation est une forme de mise en cache ; l’étape 3 consiste à se demander s’il existe un moyen de remplir ce cache à l’avance
    • Il existe aussi des solutions de programmation dynamique qui ne reposent pas sur la mémoïsation. Par exemple, pour trouver la plus longue sous-chaîne commune entre deux chaînes, on n’a besoin qu’une seule fois de la case à gauche et de celle du dessus dans le tableau, donc la mémoïsation n’apporte pas grand-chose
      De façon générale, s’il y a beaucoup de chevauchement entre les sous-problèmes et que les sous-problèmes optimaux doivent faire partie de la solution optimale globale, il y a là une opportunité pour la programmation dynamique. Dire que seule la mémoïsation est de la programmation dynamique revient un peu à dire que seules les tables de hachage sont des types de données abstraits
    • Pour moi, oui, ce serait une erreur de le voir ainsi. D’abord, il existe un contre-exemple évident : la mémoïsation peut être utilisée en dehors de la programmation dynamique. À l’inverse, la plupart des algorithmes de programmation dynamique peuvent être implémentés en stockant les résultats dans un tableau, puis en recherchant ensuite la meilleure réponse dans ce tableau
      La mémoïsation est fondamentalement une stratégie pour accélérer un algorithme

  • C’était amusant de terminer l’Advent of Code cette année. Il est clair que le jour 1, en particulier la partie 2, était bien plus difficile que d’habitude, et j’en ai parlé ici : https://blog.singleton.io/posts/2024-01-02-advent-of-code-20..., mais comparer simplement les statistiques actuelles de 2022 à celles de 2023 ne permet pas de le voir clairement, puisque les énigmes de 2022 ont eu un an de plus pour être résolues par les participants
    J’ai donc récupéré les statistiques de 2022 au 14 janvier 2023 : https://web.archive.org/web/20230114172513/https://adventofc..., et l’écart était assez important. Si l’on trace les statistiques de complétion de la partie 2 : https://blog.singleton.io/static/imgs-aoc23/completion.png, la taille du groupe de départ au jour 1 est similaire, mais 2023 semble nettement plus difficile que 2022 jusqu’au jour 15
    Le ratio des personnes ayant résolu la partie 1 sans parvenir à résoudre la partie 2 : https://blog.singleton.io/static/imgs-aoc23/ratios.png est aussi bien plus élevé sur de nombreux jours en 2023, ce qui suggère notamment que les jours 5, 10, 12, et surtout la partie 2 du jour 22, étaient difficiles

    • L’Advent of Code des débuts était amusant, et jusqu’à la seconde moitié on pouvait s’en sortir sans techniques très avancées. Ensuite c’est devenu plus difficile et moins amusant, alors j’ai abandonné et je n’y ai plus touché
    • Je n’ai pas beaucoup avancé dans l’Advent of Code cette année faute de temps, mais il est possible que je m’y remette plus tard
      Cela dit, j’ai été surpris de voir à quel point la partie 2 du jour 5 était difficile. J’ai fini par la résoudre sans abandonner, mais je me demandais si je n’avais pas raté quelque chose d’évident et compliqué excessivement la solution ; apprendre qu’il s’agissait en fait d’un problème assez corsé m’a rassuré
    • Ce n’est qu’une expérience personnelle, et le fait d’avoir essayé dans une autre langue que celle que j’utilise habituellement a peut-être joué, mais je pense que la partie 2 du jour 1 n’était pas tant difficile que mal expliquée
      Par exemple, on donnait two1nine, eightwothree, abcone2threexyz, xtwone3four, 4nineeightseven2, zoneight234, 7pqrstsixteen, mais il manquait un exemple crucial comme oneight. Sans un tel exemple, il est difficile de déterminer précisément comment effectuer les substitutions de valeurs
    • Pour ajouter à cette discussion, j’ai un script qui suit la progression jour par jour. Si l’on regarde les deux dernières colonnes, on voit à quel point 2023 a été plus brutal que 2022, surtout au début
      En 2022, la plupart des participants ont continué pendant les premiers jours, avec des taux de rétention supérieurs à 80 % sur de nombreux jours, et presque tout le monde résolvait les deux parties. En revanche, en 2023, au jour 1, seuls 76 % de ceux qui avaient résolu la partie 1 sont allés jusqu’à la partie 2, et beaucoup ont abandonné aux jours 3 et 5
      Fait intéressant, les derniers jours ne sont pas si bas, ce qui peut s’expliquer par le fait que l’Advent of Code 2023 est plus récent que celui de 2022. Mon interprétation est que ce groupe rassemble des personnes qui, indépendamment de la difficulté, surmontent tous les défis jusqu’à un certain point, tandis que beaucoup d’autres arrêtent lorsqu’elles estiment que cela leur demande trop de temps