Cómo utilizar la programación dinámica para encontrar el ancho máximo entre el valor máximo y el valor mínimo
La programación dinámica se ha utilizado ampliamente en la gestión económica, la programación de la producción, la ingeniería y el control de optimización, entre otros campos. Por ejemplo, problemas como el camino más corto, gestión de inventario, asignación de recursos, actualización de equipos, clasificación, carga, etc. son más fáciles de resolver con métodos de programación dinámica que con otros métodos.
Aunque la programación dinámica se utiliza principalmente para resolver el problema de optimización de procesos dinámicos en la etapa de división del tiempo, para algunas programación estática independiente del tiempo (como programación lineal, programación no lineal), siempre que el factor de tiempo se introduce artificialmente, considérelo como un proceso de toma de decisiones de varias etapas y también se puede resolver fácilmente utilizando métodos de programación dinámica.
La programación dinámica es una forma y un método para resolver problemas de optimización, más que un algoritmo especial. A diferencia de la búsqueda o los cálculos numéricos introducidos anteriormente, tiene una expresión matemática estándar y un método claro de resolución de problemas. La programación dinámica a menudo se diseña para un determinado problema de optimización. Dado que la naturaleza de varios problemas es diferente, las condiciones para determinar la solución óptima también son diferentes. Por lo tanto, el método de programación dinámica diseñado tiene su propia solución única para diferentes problemas y no existe. Un algoritmo de programación dinámica versátil que puede resolver todo tipo de problemas de optimización. Por lo tanto, cuando los lectores estudian, además de comprender correctamente los conceptos y métodos básicos, también deben analizar y abordar problemas específicos, utilizar una rica imaginación para construir modelos y utilizar habilidades creativas para resolver problemas. También podemos analizar y discutir algoritmos de programación dinámica para algunos problemas representativos y aprender y dominar gradualmente este método de diseño. Modelo básico
Problema de optimización con proceso de toma de decisiones en varias etapas.
En la vida real, existe un tipo de proceso de actividad. Debido a su particularidad, el proceso se puede dividir en varias etapas interconectadas. Es necesario tomar decisiones en cada etapa para que todo el proceso de actividad sea exitoso. para lograr los mejores resultados. Por supuesto, la elección de cada etapa de toma de decisiones no es arbitraria. No sólo depende del estado actual de las cosas, sino que también afecta el desarrollo futuro. Cuando cada etapa de toma de decisiones determina la composición de una secuencia de toma de decisiones. determina una ruta para todo el proceso de actividad, como se muestra en la figura: (ver imagen de texto)
Esto se considera un proceso de varias etapas con una estructura de cadena de un problema y se denomina proceso de múltiples etapas. etapa del proceso de toma de decisiones. La mejor manera de lidiar con este problema es simplemente lograr los mejores resultados. Proceso de toma de decisiones de múltiples etapas, este tipo de problema se denomina problema de toma de decisiones de múltiples etapas. Búsqueda de memoria Dado un triángulo de números de la forma:
1
2 3
4 5 6
7 8 9 10
Encuentre una ruta desde la primera capa hasta la última capa que minimice o maximice la suma de los pesos que la atraviesan.
Este es un problema familiar tanto para los usuarios nuevos como para los experimentados. Es fácil escribir la ecuación de transición de estado: f(i, j) = a[i, j] + min{f(i + 1, j), f(i + 1, j + 1)}
Para el algoritmo de programación dinámica que resuelve este problema, es fácil escribir una representación de bucle de programación dinámica basada en la ecuación de transición de estado y la dirección de transición de estado.
Sin embargo, cuando los estados y las transiciones son muy complejos, quizás escribir programación dinámica en bucle no sea tan simple.
Solución:
Intentemos analizar el problema desde una perspectiva positiva, al igual que en el ejemplo anterior, no nos resulta difícil encontrar un proceso recursivo muy simple:
f1:=f(i-1,j+1); f2:=f(i-1,j);
si f1>f2 entonces f:=f1+ a[i ,j] else f:= f2+a[i,j];
Obviamente, este algoritmo es el algoritmo de búsqueda más simple. Su complejidad temporal es 2 ^ n, lo que obviamente expirará. Analizando el proceso de búsqueda, de hecho muchas llamadas son innecesarias, es decir, se volverá a generar el estado óptimo que se ha generado. Para evitar desperdicios, obviamente necesitamos almacenar una matriz opt: Opt[i, j] - cada vez que se genera f(i,j), ponga el valor de f(i,j) en opt y llame a f( Más tarde), j), simplemente consíguelo directamente desde opt [i, j]. De esta manera, se visualiza la ecuación de transferencia de estado de la programación dinámica, lo que elimina la dificultad de pensar y reduce las habilidades de programación. El tiempo de ejecución es solo una diferencia de complejidad constante, lo que evita el problema de transferencia de estado secuencial de la programación dinámica. Dadas las circunstancias, el algoritmo recursivo puede evitar mejor el desperdicio y es muy práctico en los juegos. Decisión de Estado
Decisión:
El estado actual vuelve al estado anterior mediante una decisión. Las decisiones son el puente entre los estados. El estado anterior determina el cambio del estado actual. La toma de decisiones de un triángulo digital consiste en elegir el valor óptimo entre dos estados anteriores adyacentes.
Estado:
Algunos arrays que utilizamos habitualmente en programación dinámica también se utilizan para almacenar el valor óptimo de cada estado. Comencemos con la clave de la programación dinámica, que es la parte central "estado", y comprendamos gradualmente la programación dinámica. A veces, cuando se determina el estado actual, el estado anterior ya se ha determinado, por lo que no es necesaria ninguna enumeración adicional.
La aplicación de algoritmos de programación dinámica y el concepto de programación dinámica
En los últimos años, cada vez se ha involucrado más contenido relacionado con la programación dinámica en varios concursos. Cada año, hay casi. al menos un tema en el NOI utiliza métodos de programación dinámica para resolver el problema; y las competiciones requieren que los jugadores utilicen cada vez más conocimientos de programación dinámica, y ya no se limitan a la simple recursividad y el modelado.
Para comprender el concepto de programación dinámica, primero debemos saber qué es un problema de toma de decisiones en varias etapas.
1. Problema de toma de decisiones en varias etapas
Si un tipo de actividad se puede dividir en varias etapas interrelacionadas y es necesario tomar decisiones (medidas) en cada etapa, se etapa Una vez determinada la decisión, a menudo afectará la toma de decisiones en la siguiente etapa, determinando así completamente la ruta de actividad de un proceso. Esto se denomina problema de toma de decisiones de varias etapas.
Las decisiones en cada etapa constituyen una secuencia de decisiones, llamada estrategia. Cada etapa tiene varias decisiones para elegir y, por lo tanto, varias estrategias para elegir. En correspondencia con una estrategia, se puede determinar el efecto de la actividad y el efecto de la actividad se puede determinar cuantitativamente. Diferentes estrategias tienen diferentes efectos. El problema de la toma de decisiones en múltiples etapas consiste en elegir una estrategia óptima entre las estrategias disponibles para lograr los mejores resultados bajo estándares predeterminados.
2. Terminología en problemas de programación dinámica
Fase: Dividir adecuadamente el proceso de solución de un problema determinado en una serie de etapas interrelacionadas para facilitar la solución. de etapas es También puede ser diferente. Las variables que describen una etapa se denominan variables de etapa. En la mayoría de los casos, la variable de etapa es discreta y se denota por k. Una variable de etapa es continua si el proceso puede tomar una decisión en cualquier momento y permite tomar un número infinito de decisiones entre dos momentos diferentes.
En el ejemplo anterior, la primera etapa es el punto A, la segunda etapa es del punto A al punto B, la tercera etapa es del punto B al punto C, y la cuarta etapa es del punto C al punto punto D.
Estado: Estado se refiere al estado natural o condiciones objetivas que se enfrentan al inicio de cada etapa, no está sujeto a la voluntad subjetiva humana y también se le llama factores incontrolables. En el ejemplo anterior, el estado es la posición inicial de una etapa, que es tanto el punto inicial de una ruta en esta etapa como el punto final de una rama en la etapa anterior.
En el ejemplo anterior, la primera etapa tiene un solo estado, es decir, A, mientras que la segunda etapa tiene dos estados B1 y B2, la tercera etapa tiene tres estados C1, C2 y C3, y la cuarta etapa es otro estado D.
El estado de un proceso normalmente puede describirse mediante un número o un grupo de números llamados variables de estado. En términos generales, los estados son discretos, pero a veces se los trata como continuos por conveniencia. Por supuesto, en la vida real, todos los estados son discretos debido a restricciones en la forma variable, pero desde una perspectiva analítica, a veces resulta muy beneficioso tratar los estados como continuos. Además, el estado puede tener múltiples componentes (caso multidimensional) y por lo tanto puede representarse mediante vectores y las dimensiones del estado de cada etapa pueden ser diferentes;
A medida que el proceso evoluciona en todas las diferentes formas posibles, las variables de estado en cada parte del proceso tomarán valores dentro de un rango determinado. El conjunto de valores de variables de estado se denomina conjunto de estados.
No a posteriori: Requerimos que el estado tenga las siguientes propiedades: si se da el estado de una determinada etapa, entonces el desarrollo del proceso después de esta etapa no se verá afectado por los estados de las etapas anteriores a esta. etapa, y Cuando se identifican todas las etapas, se identifica todo el proceso. En otras palabras, cada implementación del proceso se puede representar mediante una serie de estados; en el ejemplo anterior, el estado de cada etapa es el punto inicial de la línea. Cuando se determina la secuencia de estos puntos, toda la línea es completa. determinado. . Cuando se proporciona un punto inicial de un segmento de línea, un segmento de línea que comienza después de una determinada etapa no se ve afectado por los segmentos de línea anteriores (puntos por los que se pasa). Esta propiedad de los estados significa que la historia de un proceso sólo puede verse afectada por su desarrollo futuro a través del estado actual, propiedad conocida como no secuencialidad.
Decisión: Después de que se da un estado en una etapa, la elección (acción) para desarrollarse desde ese estado a la siguiente etapa se llama toma de decisiones. En control óptimo, también se le llama control. En muchos subtítulos, las decisiones se pueden representar naturalmente como un número o un conjunto de números. Diferentes decisiones corresponden a diferentes valores. Las variables que describen la decisión se denominan variables de decisión. Dado que el estado no satisface la propiedad a posteriori, solo se debe considerar el estado actual al seleccionar una decisión en cada etapa sin considerar la historia del proceso.
El rango de variables de decisión se denomina conjunto de decisión permitido.
Estrategia: La secuencia de decisiones en cada etapa se denomina estrategia. Para cada proceso práctico de toma de decisiones de múltiples etapas, existe un límite en el rango de estrategias alternativas, que se denomina conjunto de estrategias permitidas. La estrategia que logra el mejor resultado entre el conjunto de estrategias permitidas se denomina estrategia óptima.
Dado el valor de la variable de estado x(k) en la etapa k, si se determina la variable de decisión de esta etapa, la variable de estado x(k+1) en la etapa k+1 también se determina completamente , es decir, x El valor de (k + 1) cambia con el cambio de x (k) en la etapa k y el valor de la decisión u (k). Esta relación se puede considerar como (x (k), u (k). )) y x(k+ La relación de correspondencia determinada de 1) se expresa por x(k+1)=Tk(x(k),u(k)). Esta es la ley de transición de estado de la etapa k a la etapa k+1, que se denomina ecuación de transición de estado.
Principio óptimo: Como estrategia óptima de todo el proceso, satisface: en relación con el estado formado por la decisión anterior, las subestrategias restantes deben constituir la "subestrategia óptima".
El principio de optimización en realidad requiere que la subestrategia de la estrategia óptima del problema también sea óptima. Volvamos a analizar el ejemplo anterior para ilustrar este punto: de A a D, sabemos que el camino más corto es A?B1?C2?D. La selección de estos puntos constituye la estrategia óptima en este ejemplo. Según el principio de optimización, cada subestrategia de esta estrategia debe ser óptima: A?B1?C2 es el camino más corto de A a C2, B1?C2? ¡Es el camino más corto de B1 a D! ...──Este es el caso, por lo que creemos que este ejemplo cumple con los requisitos del principio de optimización.