¿Qué es la programación dinámica?

Cuando se trata de programación de computadoras, la programación dinámica es tan versátil como matemática. Richard Bellman creó la técnica en los años 50, y desde entonces ha encontrado uso en todo, desde la ingeniería aeronáutica hasta la economía.

En ambos contextos, la palabra se refiere a dividir un tema complicado en partes manejables. Las decisiones de varios años generalmente se separan recursivamente. En informática, un problema tiene una subestructura óptima si se puede abordar de manera óptima dividiéndolo en subproblemas y encontrando recursivamente las mejores soluciones.

Existe una relación entre el valor del problema principal y los valores de los subproblemas si los subproblemas se pueden anidar recursivamente dentro del problema principal y se pueden usar técnicas de programación dinámica para resolver el problema principal. En el campo de la optimización, la ecuación de Bellman es una forma bien conocida de hablar sobre este enlace particular para una mejor estrategia.

Puede aprender ingeniería de software con la ayuda de cursos en línea.

Optimización Matemática

Al descomponer una elección compleja en una serie de opciones incrementales, como se hace en la programación dinámica, un problema de optimización matemática puede volverse mucho más manejable para las operaciones. Para lograr esto, definimos un conjunto de funciones de valor V1, V2,…, Vn que toman y como argumento para describir el estado del sistema en un cierto instante en el tiempo I de 0 a n. Vn(y) es el valor en el momento n que se adquirió del estado y. Mediante el uso de una conexión recursiva conocida como ecuación de Bellman, podemos determinar los valores de Vi en períodos anteriores I = n1, n2,…, 2, 1. Maximizando una función simple (a menudo la suma) del beneficio de una elección en tiempo I 1 y la función Vi en el nuevo estado del sistema, podemos derivar Vi1 en cualquier estado y de Vi, donde I = 2,…, n. Este procedimiento devuelve Vi1 para los estados requeridos ya que Vi ya se calculó para ellos. Y por último, el valor de la solución óptima, V1, se encuentra en la condición inicial del sistema. Al volver sobre los pasos de cálculos anteriores, los valores óptimos de las variables elegidas pueden recuperarse uno a la vez.

Para que la programación dinámica sea útil, un problema debe tener dos características: una subestructura óptima y subproblemas superpuestos. El término "divide y vencerás" se usa para referirse a una técnica en la que una dificultad se divide en problemas más pequeños e independientes y luego se resuelve combinando las mejores respuestas para cada uno. Esta es la razón por la que no consideramos que la ordenación por fusión y la ordenación rápida sean dificultades de programación dinámica.

Un programa de certificado de ingeniería de software puede mejorar sus habilidades.

Un problema de optimización con una subestructura óptima puede resolverse combinando las soluciones de sus subproblemas. Las subestructuras ideales generalmente se definen a través de la recursividad. Cada vértice intermedio ganó el camino más corto p desde un vértice u hasta un vértice v en el gráfico G=(V,E) es un ejemplo de subestructura óptima. Si el camino p es el más corto, se puede dividir en dos caminos, p1 de u a w y p2 de w a v, que también son los más cortos entre sus respectivos pares de vértices. Por lo tanto, los algoritmos de Bellman-Ford y Floyd-Warshall utilizan la recursividad para encontrar los caminos más cortos.

¿Cuál es la lógica detrás del uso de un método de programación dinámica?

El procedimiento de programación dinámica es el siguiente:

1. Al hacerlo, reduce la complejidad de todos los aspectos del problema original.
2. Para resolver estos pequeños problemas, determina la mejor respuesta posible.
3. Realiza un seguimiento de las soluciones a los desafíos más pequeños (memoización). La memorización es el acto de recordar las soluciones a problemas más pequeños.
4. Los recicla de tal manera que la misma parte del problema puede resolverse varias veces.
5. Después de todo eso, debe encontrar la respuesta al problema difícil.

1. Subestructuras óptimas y problemas con subproblemas superpuestos. En este contexto, el término "subestructura óptima" se refiere a un método mediante el cual los problemas de optimización pueden resolverse integrando las mejores soluciones a sus subproblemas constituyentes.
2. Dado que los resultados intermedios deben almacenarse, la complejidad espacial de la programación dinámica aumenta incluso cuando la complejidad temporal disminuye.