La programación dinámica, Historia, Ejemplo: Optimización Matemática, Ejemplos: algoritmos informáticos, Los algoritmos que utilizan la programación dinámica

En matemáticas, la informática y la economía, la programación dinámica es un método para la resolución de problemas complejos desglosándolos en subproblemas más simples. Es aplicable a los problemas que presentan las propiedades de subproblemas y subestructura óptima superposición. En su caso, el método toma mucho menos tiempo que los métodos ingenuos que no se aprovechan de la superposición subproblema.

La idea detrás de la programación dinámica es muy simple. En general, para resolver un problema dado, tenemos que resolver los diferentes aspectos del problema, a continuación, combinar las soluciones de los subproblemas para llegar a una solución global. A menudo, cuando se utiliza un método más ingenua, muchos de los subproblemas se generan y se resuelven muchas veces. El enfoque de programación dinámica busca resolver cada subproblema sólo una vez, lo que reduce el número de cálculos: una vez que la solución a un subproblema dado que se ha calculado, se almacena o "memo-zado": la próxima vez que se necesite la misma solución, se es simplemente miró hacia arriba. Este enfoque es especialmente útil cuando el número de subproblemas se repiten crece exponencialmente como una función del tamaño de la entrada.

Algoritmos de programación dinámica se utilizan para la optimización. Un algoritmo de programación dinámica examinará todas las formas posibles para resolver el problema y elegir la mejor solución. Por lo tanto, podemos pensar más o menos de la programación dinámica como un método inteligente de fuerza bruta que nos permite ir a través de todas las soluciones posibles para elegir la mejor. Si la magnitud del problema es tal que pasar por todas las soluciones posibles es posible y lo suficientemente rápido, garantías de programación dinámica para encontrar la solución óptima. Las alternativas son muchas, como el uso de un algoritmo voraz, que recoge la mejor opción posible "en cualquier posible rama en el camino". Mientras que un algoritmo voraz no garantiza la solución óptima, es más rápido. Afortunadamente, algunos algoritmos voraces son probados para dar lugar a la solución óptima.

Por ejemplo, digamos que usted tiene que ir del punto A al punto B lo más rápido posible, en una determinada ciudad, durante las horas pico. Un algoritmo de programación dinámica se verá en el informe de tráfico, mirando en todas las combinaciones posibles de vías que puede tomar, y sólo entonces dirá qué camino es el más rápido. Por supuesto, es posible que tenga que esperar un tiempo hasta que termine el algoritmo, y sólo entonces se puede empezar a conducir. El camino que tomará será el más rápido. Por otro lado, un algoritmo codicioso comenzará inmediatamente que la conducción y recogerá la carretera que parece el más rápido en cada intersección. Como se puede imaginar, esta estrategia no podría dar lugar a la hora de llegada más rápida, ya que podría tomar algunas calles "fáciles" y luego encuentras irremediablemente atrapado en un atasco de tráfico.

A veces, la aplicación de memoization a una solución recursiva básica ingenua ya se traduce en una solución de programación dinámica óptima, sin embargo muchos problemas requieren algoritmos de programación dinámica más sofisticados. Algunos de estos pueden ser recursivas, así parametrizada pero diferente de la solución ingenua. Otros pueden ser más complicado y no puede ser implementado como una función recursiva con memoization. Ejemplos de estos son las dos soluciones al huevo caída rompecabezas de abajo.

Historia

La programación dinámica término fue utilizado originalmente en la década de 1940 por Richard Bellman para describir el proceso de resolución de problemas en los que uno necesita para encontrar las mejores decisiones, una tras otra. Por 1953, refinó esto al significado moderno, refiriéndose específicamente a la anidación de los problemas de decisión más pequeños dentro de las decisiones más grandes, y el campo se reconoce a partir de entonces por el IEEE como un análisis de sistemas y tema de ingeniería. Contribución de Bellman es recordado en el nombre de la ecuación de Bellman, un resultado central de programación dinámica que reafirma un problema de optimización en forma recursiva.

Bellman explica el razonamiento detrás de la programación dinámica término en su autobiografía, El ojo del huracán: una autobiografía. Él explica:

 "Me pasé el trimestre de otoño en RAND. Mi primera tarea fue encontrar un nombre para los procesos de decisión de varias etapas. Una pregunta interesante es: ¿De dónde vino el nombre, programación dinámica, viene? La década de 1950 no fueron buenos años para la investigación matemática. Tuvimos .. un señor muy interesante en Washington llamado Wilson fue secretario de Defensa, y de hecho tenía un miedo patológico y el odio de la palabra, la investigación no im utilizando el término a la ligera, Im usando precisamente su rostro se inundan, se volvía. rojo, y se pondría violento si las personas utilizan el término, la investigación, en su presencia. Te puedes imaginar cómo se sentía, pues, sobre el término, matemático. The RAND Corporation fue empleado por la Fuerza Aérea y la Fuerza Aérea tenía Wilson como su jefe, esencialmente. Por lo tanto, me sentí que tenía que hacer algo para escudo Wilson y la Fuerza Aérea del hecho de que yo estaba haciendo en realidad las matemáticas dentro de la RAND Corporation. ¿Qué título, qué nombre, podía elegir? En primer lugar, Yo estaba interesado en la planificación, en la toma de decisiones, en el pensamiento de decisiones. Pero la planificación, no es una buena palabra por varias razones. Decidí por lo tanto, utilizar la palabra "programación" Yo quería transmitir la idea de que esto era dinámica, esto era varias etapas, esta fue variable en el tiempo pensé, vamos a matar dos pájaros de un tiro. Tomemos una palabra que tiene un significado absolutamente precisa, a saber dinámico, en el sentido físico clásico. Además tiene una propiedad muy interesante como un adjetivo, y es decir que es imposible usar la palabra, dinámica, en un sentido peyorativo. Intenta pensar en una combinación que posiblemente darle un sentido peyorativo. Es imposible. Por lo tanto, pensé programación dinámica era un buen nombre. Era algo que ni siquiera un El congresista podría objetar. Así que utilicé como un paraguas para mis actividades ".

La palabra dinámica fue elegido por Bellman para capturar el aspecto variable en el tiempo de los problemas, y porque sonaba impresionante. La programación de palabra se refiere a la utilización del método para encontrar un programa óptimo, en el sentido de un horario militar para la formación o la logística. Este uso es el mismo que en la programación lineal frases y programación matemática, un sinónimo de optimización matemática.

La programación dinámica es a la vez un método de optimización matemática y un método de programación de computadoras. En ambos contextos se refiere a la simplificación de un problema complicado dividiéndolo en subproblemas más simples de manera recursiva. Mientras que algunos problemas de decisión que no se pueden separar de esta manera, las decisiones que abarcan varios puntos en el tiempo qué frecuencia se rompen recurrentemente; Bellman llamó a esto el "Principio de optimalidad". Asimismo, en ciencias de la computación, se dice que un problema que se puede descomponer recursivamente tener subestructura óptima.

Si subproblemas se pueden anidar recursivamente dentro de los problemas más grandes, por lo que los métodos de programación dinámicos son aplicables, entonces hay una relación entre el valor de un problema mayor y los valores de los subproblemas. En la literatura de optimización esta relación se llama la ecuación de Bellman.

La programación dinámica en la optimización matemática

En términos de optimización matemática, programación dinámica general se refiere a la simplificación de la decisión de romper hacia abajo en una secuencia de pasos de decisión en el tiempo. Esto se hace mediante la definición de una secuencia de funciones de valor V1, V2, ..., Vn, con un argumento y que representa el estado del sistema a veces i de 1 a n. La definición de Vn es el valor obtenido en el estado y en el último momento n. El Vi valores en tiempos anteriores i = n -1, n - 2, ..., 2, 1 se puede encontrar mediante el trabajo hacia atrás, utilizando una relación recursiva llamada la ecuación de Bellman. Para i = 2, ..., n, Vi-1 en cualquier estado y se calcula a partir Vi al maximizar una función simple de la ganancia de la toma i - 1 y el Vi función en el nuevo estado del sistema si esta decisión es hecho. Desde Vi ya se ha calculado para los estados necesarios, los rendimientos de operación por encima de Vi-1 para los estados. Por último, V1 en el estado inicial del sistema es el valor de la solución óptima. Los valores óptimos de las variables de decisión pueden ser recuperados, uno por uno, mediante el seguimiento de nuevo los cálculos ya realizados.

Programación dinámica en programación de computadoras

Hay dos atributos clave que debe tener un problema con el fin de programación dinámica para ser aplicable: subestructura óptima y subproblemas superpuestos. Si un problema puede ser resuelto mediante la combinación de soluciones óptimas a subproblemas que no se solapan, la estrategia se llama "divide y vencerás" en su lugar. Esta es la razón por mergesort y quicksort no están clasificados como problemas de programación dinámicos.

Subestructura óptima significa que la solución a un problema de optimización dada puede ser obtenida por la combinación de soluciones óptimas a sus subproblemas. Por consiguiente, el primer paso hacia la elaboración de una solución de programación dinámica es comprobar si el problema exhibe tales subestructura óptima. Tales subestructuras óptimas se describen generalmente por medio de recursión. Por ejemplo, dado un grafo G =, el camino más corto p desde un vértice u a un vértice v exhibe subestructura óptima: tomar cualquier vértice w intermedio en esta ruta más corta p. Si p es verdaderamente el camino más corto, entonces se puede dividir en subtrazados de u a p1 y p2 w de W a V tal que estos, a su vez, son de hecho los caminos más cortos entre los vértices correspondientes. Por lo tanto, se puede formular fácilmente la solución para encontrar los caminos más cortos de manera recursiva, que es lo que el algoritmo de Bellman-Ford o el algoritmo de Floyd-Warshall hace.

Superposición de subproblemas significa que el espacio de subproblemas debe ser pequeño, es decir, cualquier algoritmo recursivo resolver el problema debe resolver los subproblemas mismas una y otra vez, en lugar de generar nuevos subproblemas. Por ejemplo, considere la formulación recursiva para generar la serie de Fibonacci: Fi = Fi-1 Fi-2, con el caso base F1 = F2 = 1 - A continuación, F43 = F42 F41 y F42 = F41 F40. Ahora F41 se está resolviendo en las sub-estructuras recursivas tanto de F43 y F42. A pesar de que el número total de subproblemas es realmente pequeña, terminamos la solución de los mismos problemas una y otra vez si se adopta una solución recursiva ingenuo como este. La programación dinámica tiene en cuenta este hecho y resuelve cada subproblema una sola vez.

Esto se puede lograr en una de dos maneras:

  • Enfoque de arriba hacia abajo: Esta es la directa lluvia radiactiva de la formulación recursiva de cualquier problema. Si la solución a cualquier problema se puede formular de forma recursiva utilizando la solución a sus subproblemas, y si sus subproblemas se superponen, entonces uno puede memoize o almacenar fácilmente las soluciones de los subproblemas en una tabla. Siempre que se intenta resolver un nuevo subproblema, primero revisamos la tabla para ver si ya está resuelto. Si ha guardado una solución, se puede utilizar directamente, si no se resuelve el subproblema y añadir su solución a la mesa.
  • Enfoque ascendente: Una vez que se formula la solución a un problema de forma recursiva como en términos de sus subproblemas, podemos tratar de reformular el problema de una manera ascendente: intentar resolver los subproblemas primero y utilizar sus soluciones para construir-en y llegar a soluciones a subproblemas más grandes. Esto también se hace generalmente en forma de tabla mediante la generación iterativa soluciones a subproblemas cada vez más grandes mediante el uso de las soluciones a los pequeños subproblemas. Por ejemplo, si ya sabemos los valores de F41 y F40, podemos calcular directamente el valor de F42.

Algunos lenguajes de programación pueden memoize automáticamente el resultado de una llamada a una función con un determinado conjunto de argumentos, con el fin de acelerar la evaluación de llamada por nombre. Algunos lenguajes permiten portable, algunos necesitan extensiones especiales. Algunos idiomas tienen memoization automático incorporado, como Prolog presentación y J, que apoya memoization con el M. adverbio. En cualquier caso, esto sólo es posible para una función referencial transparente.

Ejemplo: Optimización Matemática

Consumo óptimo y el ahorro

Un problema de optimización matemática que se utiliza a menudo en la enseñanza de programación dinámica para los economistas se refiere a un consumidor que vive en los períodos y debe decidir cuánto consumir y cuánto ahorrar en cada período.

 sujetos a para todos

Escrito esta manera, el problema se ve complicada, porque se trata de resolver para todas las variables de elección.

El enfoque de programación dinámica para la solución de este problema consiste en romperlo en una secuencia de decisiones más pequeñas. Para ello, se define una secuencia de funciones de valor, por lo que representa el valor de tener cualquier cantidad de capital en cada momento. Tenga en cuenta que, es decir, no hay ninguna utilidad de tener capital después de la muerte.

El valor de cualquier cantidad de capital en cualquier momento anterior se puede calcular por inducción hacia atrás usando la ecuación de Bellman. En este problema, para cada uno, la ecuación de Bellman es

Este problema es mucho más simple que la que anotamos antes, porque se trata de sólo dos variables de decisión, y. Intuitivamente, en lugar de elegir su plan de vida entera al nacer, el consumidor puede tomar las cosas un paso a la vez. Al tiempo, se da su capital actual, y que sólo necesita para elegir el consumo y el ahorro de corriente.

Para realmente resolver este problema, trabajamos hacia atrás. Para simplificar, el nivel actual del capital se denota como. que ya se conoce, por lo que el uso de la ecuación de Bellman una vez podemos calcular, y así sucesivamente hasta llegar a, que es el valor del problema de decisión inicial para toda la vida. En otras palabras, una vez que sabemos, podemos calcular, que es el máximo, ¿dónde está la variable de elección y.

Trabajando hacia atrás, se puede demostrar que la función de valor en el momento es

donde cada uno es una constante, y la cantidad óptima para consumir en el momento es

que se puede simplificar a

, Y, y, etc

Vemos que es óptimo para consumir una mayor proporción de la riqueza actual como uno envejece, finalmente, el consumo de toda la riqueza que queda en el periodo, el último período de la vida.

Ejemplos: algoritmos informáticos

El algoritmo de Dijkstra para el problema del camino más corto

Desde el punto de vista de programación dinámica, el algoritmo de Dijkstra para el problema del camino más corto es un esquema de aproximación sucesiva que resuelve la ecuación funcional de programación dinámica para el problema del camino más corto por el método de largo alcance.

De hecho, la explicación de Dijkstra de la lógica detrás del algoritmo, es decir,

Problema 2. Encontrar el camino de la longitud total mínima entre dos nodos dados y.

Utilizamos el hecho de que, si es un nodo en el camino de mínima a, el conocimiento de este último implica el conocimiento de la trayectoria mínima de a.

es una paráfrasis del famoso Principio de Bellman de optimalidad en el contexto del problema del camino más corto.

Secuencia de Fibonacci

He aquí una aplicación nave de una función para encontrar el miembro n de la secuencia de Fibonacci, basada directamente en la definición matemática:

 función fib si n = 0 devuelve 0 si n = 1 vuelta 1 vuelta fib fib

Nótese que si llamamos, por ejemplo, fib, producimos un árbol de llamadas que llama a la función en el mismo valor en muchas ocasiones diferentes:

  • mentira
  • fib fib
  • ) Fib)
  • Fib) ) fib)
  • En particular, fib se calcula tres veces a partir de cero. En los ejemplos más grandes, muchos más valores de fib o subproblemas, se vuelve a calcular, lo que lleva a un algoritmo de tiempo exponencial.

    Ahora, supongamos que tenemos un objeto simple mapa, m, que mapea cada valor de fib que ya ha sido calculada a su resultado, y modificar nuestra función de utilizarlo y actualizarlo. La función resultante sólo requiere tiempo O en lugar de tiempo exponencial:

     var m: = mapa de funciones fib mapa si m no contiene nm clave: = fib fib regreso m

    Esta técnica de ahorro de los valores que ya han sido calculados se llama memoization, este es el enfoque de arriba hacia abajo, desde que nos dividimos el problema en subproblemas y luego calcular y almacenar los valores.

    En el enfoque de abajo hacia arriba, calculamos los valores más pequeños de fib primero, y luego construir valores más grandes de ellos. Este método también utiliza el tiempo O, ya que contiene un bucle que se repite n - 1 veces, pero sólo ocupa un espacio constante, en contraste con el enfoque de arriba hacia abajo que requiere el espacio O para guardar el mapa.

     función fib si n = 0 return 0 previousFib var: = 0, currentFib: = 1 else repetir n - 1 veces// bucle se omite si n = 1 var newFib: = previousFib currentFib previousFib: = currentFib currentFib: = newFib regreso currentFib

    En ambos ejemplos, calculamos la fib una vez y, a continuación, utilizarlo para calcular tanto fib y la mentira, en vez de calcular cada vez que alguno de ellos se evalúa.

    Tenga en cuenta que el método anterior en realidad necesita tiempo para n grande debido a la adición de dos números enteros con bits cada uno lleva tiempo. Además, hay una forma cerrada para la secuencia de Fibonacci, conocida como la fórmula de Binet, de la que el-ésimo término se puede calcular en aproximadamente el tiempo, lo que es más eficiente que la técnica de programación dinámica anteriormente. Sin embargo, la simple repetición da directamente la forma de la matriz que conduce a un algoritmo de exponenciación aproximadamente por matriz rápido.

    Un tipo de matriz equilibrada 0-1

    Considere el problema de la asignación de valores, cero o uno, para las posiciones de una matriz nn, con n par, de modo que cada fila y cada columna contiene exactamente n/2 ceros y n/2 unidades. Pedimos a la cantidad de diferentes tareas que hay un dado. Por ejemplo, cuando n = 4, cuatro soluciones son posibles

    Hay por lo menos tres posibles enfoques: la fuerza bruta, vuelta hacia atrás, y la programación dinámica.

    La fuerza bruta consiste en comprobar todas las asignaciones de ceros y unos y contando los que tienen filas y columnas equilibradas. Como no son posibles asignaciones, esta estrategia no es práctico excepto tal vez hasta.

    Backtracking para este problema consiste en elegir un cierto orden de los elementos de la matriz y la colocación de forma recursiva unos o ceros, mientras que la comprobación de que en cada fila y columna del número de elementos que no se han asignado más el número de unos o ceros son ambos al menos n/2. Mientras más sofisticados que la fuerza bruta, este enfoque visitan cada solución una vez, por lo que es poco práctico para n mayor que seis, ya que el número de soluciones que ya es 116963796250 para n = 8, como veremos.

    La programación dinámica hace que sea posible contar el número de soluciones sin visitar todos ellos. Imaginemos retroceso valores de la primera fila - ¿Qué información se requiere por las filas restantes, a fin de poder contar con precisión las soluciones obtenidas para cada valor de la fila primera? Consideramos tableros kn, donde 1 = k = n, cuyas filas contener ceros y unos. La función f a la que se aplica memoization mapas de vectores de n pares de valores enteros a el número de consejos admisibles. Hay un par para cada columna, y sus dos componentes indican respectivamente el número de unos y ceros que aún tienen que ser colocados en esa columna. Buscamos el valor de. El proceso de creación subproblema implica iterar sobre cada una de las posibles asignaciones de la fila superior de la tabla, y pasando por cada columna, restando uno del elemento apropiado de la pareja para esa columna, dependiendo de si la asignación de la fila superior contiene un cero o un uno en esa posición. Si uno cualquiera de los resultados es negativa, entonces la tarea no es válido y no contribuye al conjunto de soluciones. Si no, tenemos una misión para la fila superior de la tabla kn y recursiva calculamos el número de soluciones a la tarjeta n restante, añadir el número de soluciones para cada asignación admisible de la fila superior y la devolución del importe, que se está memoized. El caso base es el subproblema trivial, que se produce por un tablero de n 1. El número de soluciones para esta placa es cero o uno, dependiendo de si el vector es una permutación de n/2 y n/2 pares o no.

    Por ejemplo, en las dos tablas que se muestran encima de las secuencias de vectores sería

       k = 4 0 1 0 1 0 0 1 1 k = 3 1 0 1 0 0 0 1 1 k = 2 0 1 0 1 1 1 0 0 k = 1 1 0 1 0 1 1 0 0

    El número de soluciones es

    Enlaces a la aplicación MAPLE del enfoque de programación dinámica se pueden encontrar entre los enlaces externos.

    Tablero de damas

    Considere la posibilidad de un tablero de ajedrez con cuadrados nn y un costo-c función que devuelve un costo asociado con plaza i, j. Por ejemplo,

    Por lo tanto c = 5

    Digamos que usted tenía un corrector que podrían comenzar en cualquier plaza en la primera fila y que quería conocer el camino más corto para llegar a la última fila, en el supuesto que el corrector podía moverse sólo en diagonal izquierda hacia adelante, en diagonal derecha hacia adelante o hacia adelante. Es decir, una ficha en que se puede mover, o.

    Este problema se presenta subestructura óptima. Es decir, la solución a todo el problema se basa en soluciones a subproblemas. Definamos una función q

     q = el costo mínimo para llegar a la plaza.

    Si podemos encontrar los valores de esta función para todas las plazas de rango n, tomamos el mínimo y seguimos ese camino hacia atrás para obtener la ruta más corta.

    Tenga en cuenta que q es igual al costo mínimo para llegar a cualquiera de los tres cuadrados por debajo de ella más c. Por ejemplo:

    Ahora, vamos a definir q en términos algo más generales:

    La primera línea de esta ecuación está ahí para hacer que la propiedad recursiva simple. La segunda línea dice que lo que sucede en la última fila, para proporcionar un caso base. La tercera línea, la recursividad, es la parte importante. Es similar a la A, B, C, D ejemplo. A partir de esta definición podemos hacer un código recursivo sencillo para q. En el pseudocódigo siguiente, n es el tamaño de la placa, c es el costo-función, y min devuelve el mínimo de una serie de valores:

     función minCost si j <1 o j> n regreso infinito else if i = 1 vuelta c else return min) c

    Cabe señalar que esta función sólo calcula la ruta de costo, no la ruta real. Vamos a llegar a la ruta pronto. Este, como el ejemplo de Fibonacci-números, es terriblemente lento ya que desperdicia tiempo recalcular los mismos caminos más cortos y otra vez. Sin embargo, podemos calcular que sea mucho más rápido de una manera ascendente si almacenamos la ruta costos en una matriz de dos dimensiones q en lugar de utilizar una función. Esto evita el recálculo, antes de calcular el costo de un camino, comprobamos la q matriz para ver si el coste de la ruta ya está ahí.

    También tenemos que saber cuál es el camino más corto es real. Para ello, se utiliza otra matriz p, una matriz predecesor. Esta matriz almacena implícitamente el camino a cualquier s plaza almacenando el nodo anterior en el camino más corto para s, es decir, el precursor. Para reconstruir el camino, buscar el precursor de s, el predecesor de esa plaza, el predecesor de esa plaza, y así sucesivamente, hasta llegar a la casilla de salida. Considere el siguiente código:

     computeShortestPathArrays función para x entre 1 y nq: = c para y desde 1 hasta nq: = infinito q: = infinito para y del 2 al n para x entre 1 nm: = min q: = m c si m = qp: = -1 else if m = qp: = 0 else p: = 1

    Lo demás es una simple cuestión de encontrar el mínimo e imprimirla.

     computeShortestPathArrays computeShortestPath función minindex: = 1 min: = q para i del 2 al n si q

    Secuencia de la alineación

    En genética, la alineación de secuencias es una aplicación importante en la programación dinámica es esencial. Por lo general, el problema consiste en la transformación de una secuencia a otra mediante las operaciones de edición que sustituyen, insertar o eliminar un elemento. Cada operación tiene un costo asociado, y el objetivo es encontrar la secuencia de ediciones con el menor costo total.

    El problema puede plantearse, naturalmente, como una recursión, una secuencia A es editada de manera óptima en una secuencia de B por cualquiera de:

  • insertar el primer carácter de B, y realizar un alineamiento óptimo de A y B de la cola
  • eliminar el primer carácter de la A, y la realización de la alineación óptima de la cola de A y B
  • reemplazando el primer carácter del A con el primer carácter de B, y la realización de alineamientos óptimos de las colas de A y B.
  • Las alineaciones parciales pueden ser tabulados en una matriz, donde la celda contiene el coste de la alineación óptima de A a B. El costo de la celda se puede calcular mediante la adición del coste de las operaciones relevantes para el costo de sus células vecinas, y la selección de la óptima.

    Existen diferentes variantes, véase el algoritmo de Smith-Waterman y el algoritmo de Needleman-Wunsch.

    Torre de Hanoi

    La Torre de Hanoi o Torres de Hanoi es un juego o un rompecabezas matemático. Se compone de tres barras, y un número de discos de diferentes tamaños que pueden deslizarse en cualquier varilla. El rompecabezas comienza con los discos en una pila ordenada en orden de tamaño creciente en una barra, el más pequeño en la parte superior, por lo que una forma cónica.

    El objetivo del rompecabezas es mover toda la pila a otra varilla, obedeciendo las siguientes reglas:

    • Sólo uno de los discos puede ser movido a la vez.
    • Cada movimiento consiste en tomar el disco superior de una de las varillas y deslizándolo sobre otra barra, en la parte superior de los otros discos que ya pueden estar presentes en esa varilla.
    • No hay ningún disco puede ser colocado en la parte superior de un disco más pequeño.

    La solución de programación dinámica consiste en resolver la ecuación funcional

     S = S, S, S

    donde n indica el número de discos que se desean mover, h denota la barra de casa, t denota la varilla de destino, no se indica la tercera vara "," denota la concatenación, y

     S: = solución a un problema que consiste en n discos que van a ser movido de varilla a varilla h t.

    Tenga en cuenta que para n = 1 el problema es trivial, es decir, S = "mover un disco de varilla a varilla h t".

    El número de movimientos requeridos por esta solución es 2n - 1 - Si el objetivo es maximizar el número de movimientos entonces la ecuación funcional de programación dinámica es un poco más complicado y 3n - 1 se requieren movimientos.

    Egg caer rompecabezas

    La siguiente es una descripción de la instancia de este famoso rompecabezas con n = 2 huevos y un edificio con H = 36 plantas:

     Supongamos que queremos saber qué plantas en un edificio de 36 plantas son seguros para dejar los huevos de, y que hará que los huevos se rompan en el aterrizaje. Hacemos algunas suposiciones:

    • Un huevo que sobrevive una caída puede ser utilizado de nuevo.
    • Un huevo roto debe ser desechado.
    • El efecto de una caída es el mismo para todos los huevos.
    • Si un huevo se rompe cuando se cae, entonces se rompería si se deja caer desde una ventana superior.
    • Si un huevo sobrevive una caída, entonces sería sobrevivir a una caída más corto.
    • No se descarta que las ventanas del primer piso huevos de descanso, ni tampoco es descartable que las ventanas del piso 36 no causan un huevo de romper.

     Si sólo hay un huevo está disponible y queremos estar seguros de obtener el resultado correcto, el experimento se puede realizar de una sola manera. Suelta el óvulo de la ventana del primer piso, y si sobrevive, la caída desde la ventana del segundo piso. Continuar hacia arriba hasta que se rompe. En el peor de los casos, este método puede requerir 36 excrementos. Supongamos 2 huevos están disponibles. ¿Cuál es el menor número de huevos excrementos que se garantiza que funcione en todos los casos?

    Para derivar una ecuación funcional de programación dinámica para este rompecabezas, dejar que el estado del modelo de programación dinámica sea un par s =, donde

     n = número de huevos de prueba disponibles, n = 0, 1, 2, 3, ..., N - 1. k = número de pisos aún para ser probado, k = 0, 1, 2, ..., H - 1.

    Por ejemplo, s = indica que dos huevos de prueba están disponibles y 6 plantas aún no se han probado. El estado inicial del proceso es s = donde N denota el número de huevos de ensayo disponibles al comienzo del experimento. El proceso termina ya sea cuando no hay más huevos de prueba o cuando k = 0, lo que ocurra primero. Si la terminación se produce en el estado s = yk> 0, entonces la prueba ha fallado.

    Ahora, vamos a

     W = número mínimo de ensayos requeridos para identificar el valor de la planta crítico bajo el peor de los casos, dado que el proceso está en el estado s =.

    Entonces se puede demostrar que

     W = 1 min {máx, W): x = 1, 2, ..., k, n = 2, ..., N; k = 2, 3, 4, ..., H

    con W = 1 para todo n> 0 y W = k para todo k. Es fácil de resolver esta ecuación iterativa mediante el aumento sistemáticamente los valores de n y k.

    Una instalación interactiva en línea está disponible para la experimentación con este modelo, así como con otras versiones de este rompecabezas

    Solución más rápida DP mediante una parametrización diferente

    Tenga en cuenta que la solución anterior lleva tiempo. Esto puede ser mejorado en tiempo por la búsqueda binaria en el óptimo en la recurrencia anteriormente, puesto que está aumentando en mientras que se disminuye en, por lo tanto un mínimo local es de un mínimo global. Sin embargo, no es una solución mucho más rápido que implica una parametrización diferente del problema:

    Vamos a ser el número total de plantas de tal manera que los huevos se rompen al caer desde el ª planta.

    Vamos a ser la base mínima de la que el huevo debe quitarse para ser rotos.

    Vamos a ser el número máximo de valores de la que son distinguibles con tries y huevos.

    A continuación, para todos.

    Vamos a ser el suelo de la que el primer huevo se cae en la estrategia óptima.

    Si el primer huevo se rompió, es a partir de y distinguible utilizando en la mayoría de los países y los huevos.

    Si el primer huevo no se rompe, es de a y distinguible mediante intentos y huevos.

    Por lo tanto.

    Entonces, el problema es equivalente a encontrar el mínimo tal que.

    Para ello, se podría calcular con el fin de aumentar, lo que llevará tiempo.

    Por lo tanto, si nos manejamos por separado el caso de, el algoritmo tomaría tiempo.

    Pero la relación de recurrencia puede de hecho ser resuelto, dando, que puede ser calculada en el tiempo utilizando la identidad para todos.

    Como para todos, podemos buscar binario en encontrar, dando un algoritmo.

    Cadena de multiplicación de matrices

    Cadena de multiplicación de matrices es un ejemplo bien conocido que demuestra la utilidad de la programación dinámica. Por ejemplo, aplicaciones de ingeniería a menudo tienen que multiplicar una cadena de matrices. No es sorprendente encontrar matrices de grandes dimensiones, por ejemplo 100100. Por lo tanto, nuestra tarea consiste en multiplicar matrices A1, A2, .... Una. Como sabemos de álgebra lineal básica, la multiplicación de matrices no es conmutativa, pero es asociativa, y que solo se pueden multiplicar dos matrices a la vez. Por lo tanto, podemos multiplicar esta cadena de matrices de muchas maneras diferentes, por ejemplo:

      A3) ... Un

    A1 ... ) Una)

      

    y así sucesivamente. Hay muchas maneras de multiplicar esta cadena de matrices. Todos ellos producen el mismo resultado final, sin embargo, van a tomar más o menos tiempo para calcular, basándose en que se multiplican las matrices particulares. Si la matriz A tiene unas dimensiones mn y la matriz B tiene dimensiones nq, entonces la matriz C = AB tendrá unas dimensiones mq, y requerirá m * n * multiplicaciones escalares q.

    Por ejemplo, vamos a multiplicar matrices A, B y C. Supongamos que sus dimensiones son mn, np, y ps, respectivamente. Matrix ABC tendrá un tamaño ms y se puede calcular de dos maneras que se muestran a continuación:

    1 - Ax Este orden de la multiplicación de matrices requerirá nps mns multiplicaciones escalares.

    2 - C Este orden de la multiplicación de matrices requerirá mnp cálculos escalares mps.

    Supongamos que m = 10, n = 100, p = 10 y s = 1,000. Así, la primera forma de multiplicar la cadena requerirá 1.000.000 1.000.000 cálculos. La segunda manera requerirá sólo 10.000 ,0000 cálculos. Obviamente, la segunda forma es más rápido, y debemos multiplicar las matrices que utilizan dicha disposición de paréntesis.

    Por lo tanto, nuestra conclusión es que el orden de los asuntos paréntesis, y que nuestra tarea es encontrar el orden óptimo de paréntesis.

    En este punto, tenemos varias opciones, una de ellas es el diseño de un algoritmo de programación dinámica que dividir el problema en problemas de superposición y calcular la disposición óptima de los paréntesis. La solución de programación dinámica se presenta a continuación.

    Vamos a llamar m el número mínimo de multiplicaciones escalares necesarias para multiplicar una cadena de matrices de matriz de i a j matriz. Dividimos la cadena en algún matriz k, tal que i <= k

    La fórmula es:

     si i = j, m = 0 si i

    cuando se cambia k de i a j - 1.

    p_ es la dimensión de las filas de la matriz i, p_k es la dimensión de las columnas de la matriz k, P_j es la dimensión de las columnas de la matriz j.

    Esta fórmula puede ser codificado como se muestra a continuación, donde el parámetro de entrada "cadena" es la cadena de matrices, es decir, A1, A2, ... An:

     función OptimalMatrixChainParenthesis n = longitud para i = 1, nm = 0// ya que no toma ningún cálculo para multiplicar una matriz para len = 2, n para i = 1, n - len 1 para j = i len -1 m = infinito// por lo que los primeros cambios de cálculo para k = i, j-1 q = m m p_ * p_k * P_j si q

    Hasta ahora, hemos calculado los valores de todas las posibles m, el número mínimo de cálculos para multiplicar una cadena de la matriz a la matriz i j, y hemos registrado el correspondiente "punto de división" s. Por ejemplo, si estamos multiplicando cadena A1A2A3A4, y resulta que m = 100 y s = 2, que significa que la colocación óptima de los paréntesis para matrices de 1 a 3 es A3 y para multiplicar estas matrices requerirán cálculo 100 escalar.

    Este algoritmo va a producir "mesas" y m s que tener entradas para todos los valores posibles de iy j. La solución final para toda la cadena es m, con división correspondiente al s. Desentrañar la solución será recursiva, a partir de la parte superior y siguiendo hasta llegar al caso base, es decir, la multiplicación de matrices individuales.

    Por lo tanto, el siguiente paso es la de dividir en realidad la cadena, es decir, para colocar el paréntesis donde pertenecen. Para ello podemos utilizar el siguiente algoritmo:

     función PrintOptimalParenthesis si i = j print "A" i otra impresión "PrintOptimalParenthesis") "

    Por supuesto, este algoritmo no es útil para la multiplicación real. Este algoritmo es sólo una manera fácil de ver lo que el resultado se parece.

    Para multiplicar realidad las matrices con el buen escisiones, tenemos el siguiente algoritmo:

     función MatrixChainMultiply// devuelve la matriz final, es decir, A1A2 ... Un OptimalMatrixChainParenthesis// esto producirá S y M "tablas" OptimalMatrixMultiplication// en realidad multiplica función OptimalMatrixMultiplication// devuelve el resultado de la multiplicación de una cadena de matrices de Ai a Aj de manera óptima si i

    Los algoritmos que utilizan la programación dinámica