¿Qué es "dinámico" acerca de la programación dinámica?

Uno de mis mayores tuvo una entrevista de trabajo y le preguntaron por qué se llama dinámico. No pudo responder y, después de darse por vencido, el entrevistador dijo que no había nada dinámico al respecto, simplemente se llama así. Eso me cuesta creerlo.

¿Se refiere al hecho de que los subproblemas se resuelven durante el tiempo de ejecución y se utilizan para alcanzar el objetivo final? ¿Te gusta la asignación dinámica de memoria que ocurre durante el tiempo de ejecución?

[RESPONDER]

Debería haber leído este artículo wiki antes de hacer la pregunta, lo siento.

Siempre intuí que significaba que los algoritmos que usaban programación dinámica parecían editar el espacio del problema " dinámicamente " hasta que el problema pudiera resolverse con un algoritmo codicioso.

Por ejemplo, con el problema del tablero de ajedrez , el algoritmo de programación dinámica edita todo el tablero a medida que lo atraviesa, y finalmente, se puede usar un algoritmo codicioso (de manera similar, con el algoritmo de ruta más corta de Dijkstra, etc.).

Sin embargo, no estoy seguro de si esto se generaliza a todos los problemas de programación dinámica.

En realidad, no hay nada especial en el nombre "programación dinámica"; La técnica en sí misma se trata de una recursión de desenrollado inteligente. Vea esta pregunta y mire la respuesta de @Jeffe, en la que se informa que Belman elige ese nombre para distraer intencionalmente.

Hay una historia interesante aquí ... Bellman fue pionero en este paradigma. Pero, esto fue en realidad una investigación matemática. En su día, el entonces secretario de defensa estaba paranoico de las palabras Investigación y Matemáticas (¡loco, cierto!). Bellman tenía miedo de que el secretario se enfureciera con su trabajo y eventualmente lo metiera en problemas. Entonces, para desdibujar un poco las cosas, lo llamó Programación dinámica , sin embargo, no tiene nada de "dinámico".

Richard Bellman lo llamó programación dinámica en las palabras en Bellman

Pasé el trimestre de otoño (de 1950) en RAND. Mi primera tarea fue encontrar un nombre para los procesos de decisión en varias etapas.

Una pregunta interesante es: ¿De dónde viene el nombre, programación dinámica? 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. Fue 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 imposible usar la palabra dinámica en un sentido peyorativo. Intenta pensar en alguna combinación que posiblemente le dé un significado peyorativo. Es imposible. Por lo tanto, pensé que la programación dinámica era un buen nombre. Era algo a lo que ni siquiera un congresista podría oponerse.

Fuente: Ojo del huracán, Richard Bellman (Autobiografía)