Qu'est-ce qui est «dynamique» dans la programmation dynamique?

Un de mes aînés a eu un entretien d'embauche et on lui a demandé pourquoi cela s'appelait dynamique. Il n'a pas pu répondre et après avoir abandonné, l'intervieweur a dit qu'il n'y avait rien de dynamique, ça s'appelait juste comme ça. C'est difficile à croire pour moi.

Fait-il référence au fait que les sous-problèmes sont résolus pendant l'exécution et utilisés pour atteindre l'objectif final? Comme l'allocation dynamique de mémoire qui se produit pendant l'exécution?

[RÉPONSE]

J'aurais dû lire cet article wiki avant de poser la question, désolé.

J'ai toujours eu l'intuition que cela signifiait que les algorithmes utilisant la programmation dynamique semblaient éditer l'espace du problème " dynamiquement " jusqu'à ce que le problème puisse être résolu avec un algorithme gourmand.

Par exemple, avec le problème Checkerboard , l'algorithme de programmation dynamique modifie la carte entière au fur et à mesure, et enfin, un algorithme gourmand peut être utilisé (de même, avec l'algorithme de chemin le plus court de Dijkstra, etc.).

Je ne sais pas si cela se généralise à chaque problème de programmation dynamique.

En fait, il n'y a rien de spécial dans le nom de "programmation dynamique"; la technique elle-même consiste à dérouler intelligemment la récursivité. Voir cette question et regardez la réponse @Jeffe, dans laquelle il est rapporté que Belman a choisi ce nom pour distraire intentionnellement.

Il y a une histoire intéressante ici .. Bellman a lancé ce paradigme. Mais c'était en fait une recherche mathématique. À l'époque, le secrétaire à la défense de l'époque était paranoïaque à propos des mots Recherche et Maths (fou, non!). Bellman avait peur que le secretart soit furieux de son travail et finisse par lui causer des ennuis. Donc, pour brouiller un peu les choses, il l'a appelé la programmation dynamique , mais il n'y a rien de «dynamique» à ce sujet.

Richard Bellman a appelé la programmation dynamique dans les mots de Bellman

J'ai passé le trimestre d'automne (de 1950) à RAND. Ma première tâche a été de trouver un nom pour les processus de décision en plusieurs étapes.

Une question intéressante est: D'où vient le nom, la programmation dynamique? Les années 1950 n'étaient pas de bonnes années pour la recherche mathématique. Nous avons eu à Washington un monsieur très intéressant nommé Wilson. Il était secrétaire à la défense, et il avait en fait une peur pathologique et une haine du mot recherche. Je n'utilise pas le terme à la légère; Je l'utilise précisément. Son visage se répandrait, il deviendrait rouge et il deviendrait violent si les gens utilisaient le terme recherche en sa présence. Vous pouvez alors imaginer ce qu'il ressentait à propos du terme mathématique. La RAND Corporation était employée par l'Air Force, et l'Armée de l'Air avait essentiellement Wilson comme patron. Par conséquent, je sentais que je devais faire quelque chose pour protéger Wilson et l'Air Force du fait que je faisais vraiment des mathématiques au sein de la RAND Corporation. Quel titre, quel nom, pourrais-je choisir? En premier lieu, je m'intéressais à la planification, à la prise de décision, à la réflexion. Mais la planification n'est pas un bon mot pour diverses raisons. J'ai donc décidé d'utiliser le mot "programmation". Je voulais faire passer l'idée que c'était dynamique, que c'était en plusieurs étapes, que ça variait dans le temps. J'ai pensé, tuons deux oiseaux avec une pierre. Prenons un mot qui a une signification absolument précise, à savoir dynamique, au sens physique classique. Il a également une propriété très intéressante en tant qu'adjectif, et qu'il est impossible d'utiliser le mot dynamique dans un sens péjoratif. Essayez de penser à une combinaison qui pourrait éventuellement lui donner un sens péjoratif. C'est impossible. Ainsi, je pensais que la programmation dynamique était un bon nom. C'était quelque chose auquel même un membre du Congrès ne pouvait s'opposer.

Source: Eye of the Hurricane, Richard Bellman (Autobiographie)