Si vous pouviez renommer la programmation dynamique…

Si vous pouviez renommer la programmation dynamique, comment l'appelleriez-vous?

L'autobiographie de Richard Bellman suggère qu'il a choisi le terme «programmation dynamique» pour distraire intentionnellement.

Les années 1950 n'étaient pas de bonnes années pour la recherche mathématique. Nous avons eu un homme très intéressant à Washington nommé Wilson. Il était secrétaire à la Défense et 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 suffoquait, il rougissait et il devenait violent si les gens utilisaient le terme «recherche» en sa présence. Vous pouvez imaginer comment il se sentait alors à propos du terme «mathématique». La RAND Corporation était employée par l'armée de l'air et l'armée de l'air avait essentiellement Wilson pour patron. Par conséquent, j’ai senti que je devais faire quelque chose pour protéger Wilson et l’armée de l’air du fait que je pratiquais réellement les mathématiques au sein de 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 planifier n'est pas un bon mot pour diverses raisons. J'ai donc décidé d'utiliser le mot "programmation". Je voulais faire comprendre que cela était dynamique, multi-étapes, variable dans le temps - je pensais, faisons d'une pierre deux coups. Prenons un mot qui a une signification absolument précise, à savoir «dynamique», au sens physique classique. Il possède également une propriété très intéressante en tant qu'adjectif: il est impossible d'utiliser le mot "dynamique" dans un sens péjoratif. Essayez de penser à une combinaison qui lui donnera éventuellement un sens péjoratif. C'est impossible. Ainsi, je pensais que «programmation dynamique» était un bon nom. C’était quelque chose que même un membre du Congrès ne pouvait objecter.

(Comme le soulignent Russell et Norvig dans leur manuel d’IA, cette histoire doit être un embellissement créatif de la vérité. Bellman a utilisé pour la première fois l’expression "programmation dynamique" en 1952 , et Charles Erwin Wilson n’a été nommé secrétaire à la Défense en 1953. )

Quoi qu'il en soit, la motivation initiale de Bellman suggère une planification en plusieurs étapes , mais du moins pour des raisons algorithmiques, je préférerais quelque chose comme une récursion ascendante frugale , seulement avec moins de syllabes.

DP présente deux aspects importants: (1) la définition des sous-problèmes (c’est-à-dire la création d’une "table", qui pourrait être un tableau multidimensionnel indexé peut-être par des entiers, des sommets, des sous-ensembles de sommets, etc.) et (2) résolvant récursivement le sous-problèmes. Je propose "récursion tabulaire / tabulée" comme un nom faisant référence aux deux aspects.

La mémorisation est une variante assez commune.

Pour aller avec diviser pour régner , je dirais épisser et combiner.

J'utilise habituellement les deux mots, joignant et combinant tout en enseignant / expliquant le DP; mais pas utilisé splice-and-combine explicitement. Parfois, j'ai utilisé le chevauchement des divisions et des conquêtes pour contraster les deux paradigmes.

Après ma récente conférence sur la programmation dynamique dans la conception d'algorithmes, j'avais demandé aux étudiants de proposer un nouveau nom pour cette technique. Bien que la "programmation difficile" m'amuse, je voulais quelque chose qui rende la technique plus mémorable. Après la discussion ici, je peux proposer deux noms, un pour top-down et un pour bottom-up:
Multiway-Divide et Memoized-Conquer (aka Divide ^ M & Conquer ^ M), et
Fusionner tous les sous-problèmes (aka Merge_all)

Ce papier ( paywalled doi ) appelle des problèmes qui peuvent être attaqués en utilisant DP "decomposable".

J'ai récemment discuté de cette question avec des collègues et, après une discussion animée, nous avons proposé la mise en cache des appels sous forme de tableau .

Je suggérerais de nommer Programmation inductive - comme une sorte de pont semblable à celui de notre époque aux bons vieux temps de Euler, Kepler et al. Ou peut-être même la programmation inductive inversée . Et oui, pour moi, le DP est fortement associé à l’induction, au sens ancien du terme. La mémorisation, la mise en cache, les tables, etc. ne sont que des éléments de technique, et non pas le cœur de l’approche.

Probablement quelque chose qui inclut le tableau de mots et le remplissage , comme c'est ce qui se passe.

Vue récursive ou horizon récursif

Je l'appellerais "Récursion avec mémoization".