Si pudieras renombrar la programación dinámica ...

Si pudieras cambiar el nombre de la programación dinámica, ¿cómo lo llamarías?

La autobiografía de Richard Bellman sugiere que eligió el término "programación dinámica" para distraer intencionalmente.

La década de 1950 no fueron buenos años para la investigación matemática. Tuvimos un caballero muy interesante en Washington llamado Wilson. Era secretario de Defensa, y en realidad tenía un miedo patológico y odio a la palabra 'investigación'. No estoy usando el término a la ligera; Lo estoy usando con precisión. Su rostro se ensuciaría, se volvería rojo y se volvería violento si la gente usara el término 'investigación' en su presencia. Puedes imaginar cómo se sintió, entonces, sobre el término 'matemático'. La Corporación RAND fue empleada por la Fuerza Aérea, y la Fuerza Aérea tenía a Wilson como su jefe, esencialmente. Por lo tanto, sentí que tenía que hacer algo para proteger a Wilson y a la Fuerza Aérea del hecho de que realmente estaba haciendo matemáticas dentro de la Corporación RAND.

¿Qué título, qué nombre podría elegir? En primer lugar, me interesaba planificar, tomar decisiones y pensar. Pero planificar no es una buena palabra por varias razones. Por lo tanto, decidí usar la palabra 'programación'. Quería transmitir la idea de que esto era dinámico, que era de varias etapas, que variaba en el tiempo. Pensé, matemos dos pájaros de un tiro. Tomemos una palabra que tenga un significado absolutamente preciso, a saber, "dinámico", en el sentido físico clásico. También tiene una propiedad muy interesante como adjetivo, y es que es imposible usar la palabra 'dinámico' en un sentido peyorativo. Intenta pensar en alguna combinación que posiblemente le dé un significado peyorativo. Es imposible. Por lo tanto, pensé que "programación dinámica" era un buen nombre. Era algo a lo que ni siquiera un congresista podría oponerse.

(Sin embargo, como Russell y Norvig señalan en su libro de texto de IA, esta historia debe ser un adorno creativo de la verdad. Bellman utilizó por primera vez la frase "programación dinámica" en 1952 , y Charles Erwin Wilson no se convirtió en Secretario de Defensa hasta 1953. )

De todos modos, la motivación original de Bellman sugiere una planificación de varias etapas , pero al menos para fines algorítmicos, preferiría algo como la recursión frugal de abajo hacia arriba , solo con menos sílabas.

Hay dos aspectos importantes de DP: (1) definir los subproblemas (es decir, configurar una "tabla", que podría ser una matriz multidimensional indexada tal vez por enteros, vértices, subconjuntos de vértices, etc.) y (2) resolver recursivamente subproblemas Propongo "recursión tabular / tabulada" como un nombre que se refiere a ambos aspectos.

La memorización es una variante bastante común.

Para ir con divide y vencerás , yo diría empalmar y combinar.

Usualmente uso ambas palabras, empalmar y combinar mientras enseño / explico DP; pero no se usa empalmar y combinar explícitamente. A veces he usado la superposición de dividir y conquistar para contrastar los dos paradigmas.

Después de mi reciente conferencia sobre programación dinámica en diseño de algoritmos, les pedí a los estudiantes que sugirieran un nuevo nombre para esta técnica. Aunque me divertía la "programación difícil", quería algo que pudiera hacer que la técnica fuera más memorable. Después de la discusión aquí, puedo proponer dos nombres, uno para arriba hacia abajo y otro para abajo:
Multiway-Divide y Memoized-Conquer (también conocido como Divide ^ M & Conquer ^ M), y
Merge all subproblems (también conocido como Merge_all)

Este documento ( paywalled doi ) llama a los problemas que pueden ser atacados usando DP "descomponible".

Discutí esto con algunos colegas recientemente, y después de una acalorada discusión surgió el almacenamiento en caché de llamadas tabulares .

Sugeriría el nombre de Programación inductiva , como una especie de puente desde nuestros tiempos hasta los buenos tiempos de Euler, Kepler et al. O tal vez incluso la programación inductiva inversa . Y sí, para mí DP está fuertemente asociado con la inducción, en el viejo sentido de la noción. La memorización, el almacenamiento en caché, las tablas, etc. son solo elementos de la técnica, no del núcleo del enfoque para descifrar cosas.

Probablemente sea algo que incluya las palabras tabla y relleno , ya que esto es lo que sucede.

Vista recursiva u horizonte recursivo

Lo llamaría "Reenvío hacia adelante con memorización".