Bellman Richard

En 1953, Richard Bellman publie son premier travail sur une manière nouvelle de résoudre certains problèmes d’optimisation. Au lieu de recommencer les mêmes calculs à chaque choix possible, il découpe le problème en étapes, conserve les meilleurs résultats intermédiaires et les réutilise.

Cette programmation dynamique est devenue son apport le plus célèbre. Elle ramène une décision complexe à une suite de sous-problèmes liés, par exemple pour organiser une production, gérer un trafic ou chercher un trajet minimal.

Richard Ernest Bellman (1920–1984) est un mathématicien américain, principalement connu pour avoir inventé la programmation dynamique. Cette méthode algorithmique traite des problèmes d’optimisation en les décomposant récursivement en sous-problèmes. Les solutions intermédiaires sont mémorisées, puis réutilisées au lieu d’être recalculées. Bellman publie un premier travail dans ce domaine en 1953 et en systématise les fondements dans Dynamic Programming, paru en 1957.

Après des études aux universités de Brooklyn et du Wisconsin, il travaille en physique théorique au Laboratoire national de Los Alamos pendant la Seconde Guerre mondiale. En 1946, il soutient à Princeton une thèse sur les équations différentielles sous la direction de Solomon Lefschetz. Il passe ensuite plusieurs années à la RAND Corporation, institution de recherche appliquée et d’analyse stratégique.

L’équation de Bellman, aussi appelée équation d’Hamilton-Jacobi-Bellman, prolonge en temps continu les travaux de Hamilton et Jacobi et conduit à une équation aux dérivées partielles. Les idées de Bellman interviennent dans l’ordonnancement industriel, la gestion du trafic, les algorithmes de plus court chemin, le sac à dos et le voyageur de commerce. Entré à l’université de Californie du Sud en 1965, il y poursuit ses recherches jusqu’à sa mort, malgré une grave tumeur cérébrale diagnostiquée en 1973.

Un réseau orienté relie un départ A à une arrivée D. Les coûts sont : A→B vaut 4, A→C vaut 2, C→B vaut 1, B→D vaut 3 et C→D vaut 7. La figure matérialise ces cinq choix et leurs coûts.

Pour chaque sommet X, la valeur V(X) désigne le coût minimal restant jusqu’à D. Le coût d’une liaison de X vers Y est noté c(X,Y). La relation de Bellman choisit le meilleur prochain sommet Y :

1. À l’arrivée, aucun coût ne reste : V(D) = 0.

2. Depuis B, la liaison vers D coûte 3 : V(B) = 3.

3. Depuis C, aller directement à D coûte 7, tandis que passer par B coûte 1 + 3 = 4. Donc V(C) = 4.

4. Depuis A, passer par B coûte 4 + 3 = 7. Passer par C coûte 2 + 4 = 6. Donc V(A) = 6.

Le trajet minimal est A–C–B–D, de coût total 6. Le calcul réutilise V(B) pour déterminer V(C), puis V(C) pour déterminer V(A).

Le contrôle consiste à additionner chaque autre trajet complet : A–B–D coûte 7 et A–C–D coûte 9. Aucun n’est inférieur à 6.

Dans un réseau de circulation, la programmation dynamique compare les coûts restants depuis chaque carrefour. Elle devient utile lorsque plusieurs trajets partagent les mêmes portions ; une comparaison directe suffit si les possibilités sont très peu nombreuses.

Pour un ordonnancement industriel, chaque état décrit ce qui a déjà été réalisé et les décisions encore possibles. On mémorise le meilleur résultat par état ; une règle locale isolée ne convient pas lorsque son choix modifie les étapes suivantes.

Dans un problème de sac à dos ou de voyageur de commerce, le même sous-problème peut réapparaître dans plusieurs branches. Le bon geste est de définir précisément l’état à mémoriser avant de calculer, afin que deux états déclarés identiques aient réellement les mêmes choix futurs.

Programmation dynamique et équation d’Hamilton-Jacobi-Bellman. La première est une méthode algorithmique qui mémorise des solutions de sous-problèmes. La seconde est une équation aux dérivées partielles pour le temps continu. Un calcul par étapes discrètes relève de la méthode ; une formulation continue relève de l’équation.

Décomposition et programmation dynamique. Découper un problème ne suffit pas. La programmation dynamique repose sur le principe d’optimalité et sur des sous-problèmes définis par un état suffisamment complet. La mémorisation et la réutilisation de leurs solutions sont une stratégie d’implémentation efficace ; une récursion naïve peut les recalculer sans changer la formulation du problème.

Un mauvais état fausse la réutilisation. Deux situations ne peuvent partager une valeur mémorisée que si elles offrent les mêmes choix futurs pertinents. Si une information nécessaire manque, il faut enrichir la description de l’état avant d’appliquer la récurrence.

La version continue change de cadre. L’équation d’Hamilton-Jacobi-Bellman n’est pas la simple écriture du tableau discret de l’exemple. Elle conduit à une équation aux dérivées partielles ; il faut donc annoncer le cadre continu au lieu de transposer sans précaution les étapes du graphe.

Les dates ne se remplacent pas. 1953 correspond à la première publication de Bellman sur la programmation dynamique, 1957 au livre qui en systématise les fondements, et 1965 à son arrivée à l’université de Californie du Sud. Les fusionner effacerait trois jalons distincts.

Programmation dynamique : approfondir la méthode de décomposition, de mémorisation et de réutilisation dont Bellman a systématisé les fondements.

Problème du sac à dos : observer la programmation dynamique sur un problème combinatoire classique cité parmi ses applications.

Problème du voyageur de commerce : relier l’héritage de Bellman à un autre problème combinatoire de la définition source.