Cuéntame sobre la programación dinámica
Características y aplicaciones de la programación dinámica
Anhui Zhang Chen
Tabla de contenidos
(Haga clic para ingresar)
Palabras clave
Resumen
Texto
§1 La esencia de la programación dinámica
§1.1 Problema de toma de decisiones en varias etapas
§1.2 Etapas y estados
§1.3 Decisiones y estrategias
§1.4 Principios de optimización y sin efectos secundarios
§1.5 Funciones y indicadores óptimos Ecuaciones de planificación
§2 Diseño e implementación de programación dinámica
§2.1 Diversidad de programación dinámica
§2.2 Patrones de programación dinámica
§2.3 Habilidades de programación dinámica
§3 Comparación de programación dinámica y algunos algoritmos
§3.1 Programación dinámica y recursividad
§3.2 Programación dinámica y búsqueda
§3.2 Programación dinámica y búsqueda
§3 p>
§3.3 Programación dinámica y flujo de red
§4 Conclusión
Apéndice: algunas preguntas del examen y programas fuente
1. pregunta "Problema de diseño de escaparate"
2. Pregunta de prueba "Clavos y bolas"
3. Programa fuente del método 1 del Ejemplo 2 "Problema de diseño de escaparate de floristería"<. /p>
4. Programa fuente del método 2 del Ejemplo 2 "Problema de diseño de escaparate de floristería"
5. Extensión del Ejemplo 3 "Problema de la calle"
6. 4 "Mod 4 Most El programa fuente del ejemplo 5, "Nail and Ball"
8. El programa fuente del ejemplo 6, "N-Person Street Problem"
Referencias
Palabras clave Etapa de programación dinámica
Resumen
La programación dinámica es un algoritmo común en las competencias de informática. El contenido principal de este artículo solo analiza sus características.
La primera parte del artículo explora primero la esencia de la programación dinámica, porque las características de la programación dinámica están determinadas por su esencia. La segunda parte analiza las tres características de la programación dinámica: diversidad, patrón y habilidad desde las dos perspectivas del diseño e implementación de la programación dinámica. La tercera parte compara la programación dinámica con tres algoritmos relacionados: recursividad, búsqueda y flujo de red, y explora algunas características más profundas de la programación dinámica.
Mientras analiza las características de la programación dinámica, el artículo también analiza cómo debemos usar estas características en la resolución de problemas y cómo usar la programación dinámica basada en estas características. Esto tiene cierta importancia orientadora para nuestra práctica de resolución de problemas.
Texto
La programación dinámica es un medio importante para resolver problemas de programación y se utiliza cada vez más en las competiciones de informática actuales. En los últimos años, los concursos de ciencias de la información, independientemente de su tamaño, tienen que examinar este aspecto casi siempre. Por lo tanto, cómo comprender la programación dinámica más profundamente y utilizar esta poderosa arma para resolver problemas de manera más efectiva es una cuestión que merece un estudio en profundidad.
Para dominar las habilidades de aplicación de la programación dinámica, debes comprender sus diversas características. En primer lugar, es necesario conocer en profundidad la naturaleza de la programación dinámica.
§1 La esencia de la programación dinámica
La programación dinámica nació a principios de la década de 1950 para resolver un tipo de problemas de toma de decisiones de varias etapas. Entonces, ¿qué tipo de problema se llama problema de toma de decisiones en varias etapas?
§1.1 Problema de toma de decisiones en varias etapas
Cuando se trata de problemas de toma de decisiones en varias etapas, las personas pueden dar fácilmente el siguiente ejemplo.
[Ejemplo 1] Problema de ruta más corta en un gráfico de múltiples segmentos: encuentre la ruta más corta de A1 a D1 en el siguiente gráfico.
Si te fijas bien en esta imagen, no es difícil comprobar que tiene una característica. Dividimos los puntos del gráfico en cuatro categorías (A, B, C, D en el gráfico), luego todos los bordes del gráfico están entre las dos categorías de puntos adyacentes y todos apuntan desde la categoría de puntos anterior a este último punto. De esta forma, las aristas del gráfico se dividen en tres categorías (A?B, B?C, C?D). Necesitamos seleccionar un borde de cada categoría para formar un camino de A1 a D1, y este camino es el más corto de todos esos caminos.
A partir del ejemplo anterior, podemos entender aproximadamente qué es un problema de toma de decisiones de varias etapas.
Una definición más precisa es la siguiente:
Un proceso de toma de decisiones de múltiples etapas se refiere a un tipo especial de proceso de actividad en el que el problema se puede descomponer en una serie de etapas interconectadas en orden cronológico, y una Se deben tomar decisiones en cada etapa de la toma de decisiones. Todo el proceso de toma de decisiones es una secuencia de toma de decisiones [1]. El problema de optimizar el efecto general de toda la actividad se denomina problema de toma de decisiones en varias etapas.
De la definición anterior podemos ver claramente que este tipo de problema tiene dos elementos. Una es una etapa y la otra es una decisión.
§1.2 Etapas y Estados
Etapa: descomponer el proceso del problema dado en varias etapas interconectadas según las características de tiempo o espacio, para encontrar la solución de cada etapa. en orden. La letra k se usa comúnmente para representar variables de etapa. [1]
La etapa es un atributo del problema. Por lo general, hay varias etapas en los problemas de toma de decisiones de varias etapas. Por ejemplo, en el ejemplo anterior, hay cuatro etapas: A, B, C y D. En general, las etapas están relacionadas con el tiempo; pero en muchos problemas (en mi opinión, especialmente los problemas informáticos), las etapas y el tiempo son irrelevantes. De la definición de etapas, podemos ver dos características de las etapas, una es "interconexión" y la otra es "secuencia".
¿Cómo se relacionan las etapas entre sí? Esto es a través de estados y transiciones estatales.
Estado: Las condiciones objetivas al inicio de cada etapa se denominan estados. Las variables que describen el estado de cada etapa se denominan variables de estado. Sk se usa comúnmente para representar las variables de estado de la k-ésima etapa. El conjunto de valores de la variable de estado sk se denomina conjunto de estado, representado por Sk. [1]
El estado es un atributo del escenario. Cada etapa suele contener varios estados para describir una situación objetiva cuando el problema se desarrolla hasta esta etapa. En el ejemplo anterior, después de que el peatón recorre dos etapas desde el punto de partida A1, hay tres situaciones posibles, a saber, en el punto C1, C2 o C3. Luego hay tres estados S3={C1, C2, C3} en la tercera etapa.
El estado de cada etapa "cambia" de alguna manera con respecto al estado de la etapa anterior. Este "cambio" se llama transición de estado (aún no definido). En el ejemplo anterior, el punto C3 puede provenir del punto B1 o del punto B2. Pasar del estado B1 o B2 en la etapa 2 al estado C3 en la etapa 3 es una transición de estado. La transición de estado es la forma de derivar el estado y la forma de conectar cada etapa.
Dicho esto, se puede plantear una condición importante para la aplicación de la programación dinámica. Es decir, después de organizar las etapas en un orden determinado, para un estado de etapa determinado, el estado de sus etapas anteriores no puede afectar directamente su desarrollo futuro, sino que solo puede pasar por el estado actual. En otras palabras, cada estado es "un resumen completo de la historia pasada[1]". Esto no es una consecuencia. Esta propiedad se explicará a continuación.
§1.3 Toma de decisiones y estrategia
Las etapas y estados anteriores son solo un aspecto del problema de toma de decisiones de múltiples etapas. El siguiente es otro aspecto del elemento: decisión. -haciendo.
Toma de decisiones: Una vez determinado el estado de cada segmento, se pueden tomar diferentes decisiones para determinar el estado de la siguiente etapa. Esta decisión se denomina toma de decisiones. Las variables que representan la toma de decisiones se denominan variables de decisión. El uk (sk) de uso común representa la variable de decisión en la k-ésima etapa cuando el estado es sk. En problemas prácticos, los valores de las variables de decisión suelen estar limitados a un rango determinado. A este rango lo llamamos conjunto de decisión permitido. Dk(sk) se usa comúnmente para representar el conjunto de decisiones permitidas a partir del estado sk en la k-ésima etapa. Obviamente hay uk(sk) ?Dk(sk). [1]
La toma de decisiones es una propiedad de la solución a un problema. El propósito de la toma de decisiones es "determinar el estado de la siguiente etapa". Volviendo al ejemplo anterior, hay tres caminos que comienzan desde el estado B1 de la etapa 2, es decir, tres decisiones que conducen a los tres estados. de C1, C2 y C3 de la etapa 3 respectivamente, es decir, D2(B1)={C1,C2,C3}.
Con la toma de decisiones, podemos definir la transición de estado: en la programación dinámica, el estado de esta etapa es a menudo la etapa anterior y el resultado de la decisión de la etapa anterior, que consiste en el estado sk del k-ésimo párrafo y la decisión uk de esta etapa. El proceso de determinar el estado sk+1 del segmento k+1 se llama transferencia de estado. La expresión formal de la ley de transición de estados sk+1=Tk(sk,uk) se llama ecuación de transición de estados.
Parece que existe cierta conexión entre la toma de decisiones y la transición estatal. Tengo entendido que la transición estatal es el propósito de la toma de decisiones, y la toma de decisiones es el camino hacia la transición estatal.
Una vez determinadas las decisiones de cada sección, la secuencia de decisiones de todo el problema constituye una estrategia, representada por p1,n={u1(s1),u2(s2),…, un(sn) }. Para cada problema práctico, existe un cierto rango de estrategias disponibles para su selección, que se denomina conjunto de estrategias permitidas, denotado como P1,n. La estrategia que hace que todo el problema sea más efectivo es la estrategia óptima. [1]
Dicho esto, se puede plantear otra premisa para utilizar la programación dinámica. Es decir, la estrategia óptima de este proceso debe tener las siguientes propiedades: independientemente del estado inicial y la decisión inicial, para el estado formado por la decisión anterior, todas las decisiones posteriores deben constituir la estrategia óptima [1]. Este es el principio de optimización. En resumen, es "la subestrategia de la estrategia óptima es también la estrategia óptima".
§1.4 Principio de optimización y sin efectos secundarios
Aquí posiciono el principio de optimización como el "requisito previo para utilizar la programación dinámica". Esto se debe a que si se ajusta al principio de optimización es una característica esencial de un problema. Para un problema de toma de decisiones de múltiples etapas que no satisface el principio de optimización, la estrategia óptima general p1, n no tiene ninguna diferencia con la decisión uk en cualquier etapa k o la subpolítica pk1, k2 en cualquier grupo de etapas. relación k1...k2. Si queremos planificar dinámicamente un problema de este tipo, nuestros esfuerzos por dividir las etapas desde el principio serán en vano.
Y posicioné la falta de efectos secundarios como la "condición para aplicar la programación dinámica" porque la programación dinámica busca soluciones para cada etapa en orden. Si un problema tiene efectos secundarios, entonces ese orden no es razonable. Sin embargo, podemos hacer que el problema cumpla con la condición de no tener efectos secundarios volviendo a dividir las etapas, volviendo a seleccionar el estado o aumentando el número de variables de estado. En última instancia, aún nos falta determinar un “orden”.
La mayoría de los problemas de toma de decisiones de múltiples etapas en informática pueden satisfacer el principio de optimización, pero a menudo crean obstáculos en términos de efectos secundarios. Por lo tanto, en el proceso de resolución de problemas, prestaremos especial atención al "orden". Para problemas ordenados, se considerará la programación dinámica; para problemas desordenados, también encontraremos formas de hacerlos ordenados.
§1.5 Función de indicador óptima y ecuación de planificación
Función de indicador óptima: el indicador cuantitativo utilizado para medir la calidad de la estrategia seleccionada se denomina función de indicador, y la función de indicador óptima es denotado es fk(sk), que representa el mejor valor de beneficio desde el estado k-ésima etapa sk usando la estrategia óptima p*k,n hasta el final del proceso [1].
La función de índice óptima es en realidad la solución al problema que realmente nos importa. En el ejemplo anterior, f2(B1) representa la longitud del camino más corto desde el punto B1 hasta el punto final D1. El objetivo final de nuestra solución es f1(A1).
El método para encontrar la función de índice óptima es generalmente una fórmula recursiva que comienza desde el estado objetivo, que se denomina ecuación de planificación:
donde sk es un determinado estado en el k-ésimo segmento , y uk es una decisión en el conjunto de decisiones permitido Dk(sk) a partir de sk, Tk(sk,uk) es un cierto estado sk+1 en el segmento k+1 derivado de sk y uk, g(x,uk) es una función definida sobre el valor x y la decisión uk, y la función opt representa la optimización, que se expresa como máximo o mínimo según el problema específico.
, llamadas condiciones de contorno.
La ecuación de planificación en el ejemplo anterior es:
La condición límite es
Este es un método de orden inverso para retroceder desde el estado objetivo, que es adecuado para el estado objetivo Problema definido. Muchos de nuestros problemas informáticos tienen estados iniciales definidos. Por supuesto, para el problema de determinar el estado inicial, también podemos utilizar el método secuencial para comenzar desde el estado inicial y avanzar. De hecho, este método es más intuitivo y fácil de diseñar para nosotros, por lo que aparece con más frecuencia en nuestro proceso de resolución de problemas.
Aunque las teorías que discutimos en esta sección no son el propósito principal de este artículo, juegan un papel fundamental en las características de la programación dinámica que se analizan a continuación.
§2 Diseño e implementación de programación dinámica
Hemos discutido algunas teorías de programación dinámica anteriormente. En esta sección, usaremos varios ejemplos para aprender sobre el diseño y la implementación de programación dinámica. Comprender algunas características de la programación dinámica.
§2.1 Diversidad de programación dinámica
[Ejemplo 2] Las preguntas de la prueba sobre el problema de diseño de escaparates de florería (IOI99) se encuentran en el apéndice
Aunque esta pregunta está en IOI de este año Una pregunta relativamente simple, pero hay mucho sobre qué escribir.
Se dice que es simple porque es ordenado, por lo que podemos ver de un vistazo que este problema debe resolverse mediante programación dinámica. Pero ¿qué pasa con la programación dinámica? ¿Cómo dividir las etapas y cómo elegir el estado?
La ecuación de transición de estado es
La ecuación de planificación es
(donde A(i,j) es el valor estético del ramo i colocado en el jarrón j)
p>
Condiciones de límite (V es el número total de jarrones, de hecho, este es un límite virtual)
La ecuación de transición de estados es
La ecuación de planificación es
La condición de contorno es
Dos métodos de dividir etapas conducen a dos estados Notación, dos métodos de planificación, pero ambos resolvieron el problema con éxito. Es solo que debido a que hay cada vez menos opciones para tomar decisiones, la complejidad temporal del algoritmo también es diferente. [2]
Este ejemplo es muy general. Hay muchos problemas de toma de decisiones de múltiples etapas que tienen más de un método de división de etapas y, por lo tanto, a menudo tienen más de un método de planificación. A veces los efectos producidos por varios métodos son similares, pero más a menudo, como en nuestro ejemplo, los dos métodos serán algo diferentes en algunos aspectos.
Entonces, al utilizar la programación dinámica para resolver problemas, puedes pensar más en si existen otras soluciones. Para diferentes métodos de solución, debemos prestar atención a la comparación de cuáles son las ventajas de los buenos algoritmos y las desventajas de los algoritmos inferiores. A partir de la comparación de varios algoritmos, podemos tener una comprensión más profunda de las habilidades creativas de la programación dinámica.
§2.2 El patrón de programación dinámica
Todos los que han realizado programación dinámica pueden haber experimentado esto, y también se puede ver en nuestro análisis de programación dinámica anterior. El diseño de la programación dinámica tiene un patrón determinado, que generalmente implica los siguientes pasos.
Dividir en etapas: Dividir el problema en varias etapas según las características temporales o espaciales del problema. Tenga en cuenta que estas etapas deben ordenarse o clasificarse; de lo contrario, el problema no se podrá resolver.
Selección de estado: Utilice diferentes estados para representar varias situaciones objetivas cuando el problema se desarrolla en varias etapas. Por supuesto, la elección del Estado no debe dejar secuelas.
Determine la decisión y escriba la ecuación de transición de estado: la razón por la que estos dos pasos se combinan es porque la toma de decisiones y la transición de estado están naturalmente relacionadas. La transición de estado se deriva en función del estado y la decisión del estado. estado anterior en esta etapa. Entonces, si determinamos la decisión, se escribe la ecuación de transición de estado. Pero, de hecho, a menudo hacemos lo contrario: tomamos decisiones basadas en la relación entre los estados de dos segmentos adyacentes.
Escriba la ecuación de planificación (incluidas las condiciones de contorno): en la primera parte, hemos dado una expresión formal general de la ecuación de planificación. En términos generales, siempre que se determinen las etapas, estados, decisiones y transiciones de estado, este paso es relativamente simple.
La principal dificultad de la programación dinámica radica en el diseño teórico. Una vez completado el diseño, la parte de implementación será muy sencilla.
El marco general es el siguiente:
Inicializar f1(s1) (condiciones de contorno)
para k?2 an (aquí, la solución secuencial se toma como ejemplo)
Para cada sk?Sk
fk(sk)?Un valor extremo (∞ o -∞)
Para cada uk(sk)?Dk(sk)
sk-1?Tk(sk,uk)
t?g(fk-1(sk-1),uk)
y t es más valioso que fk (sk) Excelente n
fk(sk)?t
Salida fn(sn)
Aunque este diagrama N-S no puede representarlo todo, puede resumir la mayor parte de a ellos. Los principios de implementación de algunas programación dinámica especial también son similares y pueden compararse por analogía. Nuestro análisis de la programación dinámica hasta ahora se ha realizado principalmente en teoría y diseño, y esta es la razón.
Después de dominar el patrón de programación dinámica, podemos centrarnos en el diseño teórico cuando utilizamos la programación dinámica para resolver problemas. Una vez que el diseño madura, el problema básicamente se resuelve. Y también puedes hacerlo paso a paso a la hora de diseñar el algoritmo.
Sin embargo, "todo debe invertirse en su extremo". Ser demasiado rígido en los patrones limitará nuestro pensamiento y sofocará el surgimiento de excelentes ideas algorítmicas. Cuando resolvemos problemas, también podemos usar nuestra creatividad para romper el modo de implementación de la programación dinámica, que a menudo produce resultados inesperados. [3]
§2.3 Las habilidades de programación dinámica
El patrón de programación dinámica que mencionamos anteriormente se refiere principalmente al aspecto de implementación. En términos de diseño, aunque tiene procedimientos estrictos, sus ideas de diseño no tienen ciertas reglas a seguir. Esto requiere que dominemos continuamente las habilidades de programación dinámica en la práctica. Hablemos de mi propia experiencia con un ejemplo.
[Ejemplo 3] Problema de la calle: encuentre el camino más corto desde la esquina inferior izquierda hasta la esquina superior derecha en la imagen de abajo. Cada paso solo puede ir hacia la derecha o hacia arriba.
Esta es una pregunta de programación dinámica simple y típica. Se utiliza como ejemplo en muchos libros y artículos que presentan la programación dinámica. Por lo general, la respuesta en el libro es la siguiente:
Las etapas se dividen según las líneas de puntos en la figura, es decir, la variable de etapa k representa el número de pasos dados y la variable de estado sk representa dónde se encuentra actualmente en esta etapa Un punto (las etapas y estados correspondientes a cada punto han sido marcados en el mapa con ks). En este momento, el modelo se ha transformado en un gráfico especial de múltiples segmentos. Usando la variable de decisión uk=0 para indicar ir hacia la derecha y uk=1 para indicar subir, la ecuación de transición de estado es la siguiente:
(la fila aquí es el número de filas en la dirección vertical del mapa )
Vemos que esta ecuación de transición de estado debe discutirse en dos situaciones en función del valor de k, lo cual es muy problemático. En consecuencia, cuando se sustituye en la ecuación de planificación y se implementa, el algoritmo también es muy complicado. Por lo tanto, generalmente no hacemos esto durante la implementación, sino que utilizamos el siguiente método:
Numere los puntos en el mapa regularmente como se indica arriba, y la ecuación de planificación resultante será la siguiente:
(La distancia aquí representa la longitud del lado entre dos puntos adyacentes)
Esto es de hecho mucho más simple que el método anterior, pero ha destruido la cara original de la programación dinámica y no hay una etapa clara. Si este método divide las etapas por filas (A, B, C, D) en el mapa, entonces su "transferencia de estado" no se realiza toda entre las dos etapas.
Tal vez no sea gran cosa porque la práctica habla más que la teoría. Sin embargo, si ampliamos la pregunta: encontramos dos caminos desde la esquina inferior izquierda hasta la esquina superior derecha en el mapa, ninguno de los lados de los dos caminos puede superponerse y la longitud total de los dos caminos debe ser la más corta. En este momento, no es fácil utilizar este método "simple".
Si se debe aplicar este método, la función de índice óptima debe tener un subíndice de cuatro dimensiones, y será difícil resolver el problema de que las dos rutas "no se pueden superponer".
Cuando volvamos al método de programación dinámica "estándar" original, encontraremos que este problema es fácil de resolver y solo necesitamos agregar una variable de estado unidimensional. Es decir, sk = (ak, bk) se usa para representar las posiciones de las dos rutas cuando alcanzan la etapa k. En consecuencia, la variable de decisión también aumenta en una dimensión, y uk = (xk, yk) se usa para representar la. Indicaciones para caminar de los dos senderos.
Considere las dos rutas por separado durante la transición de estado:
Al escribir la ecuación de planificación, solo necesita manejar ligeramente la situación en la que las dos rutas llegan al mismo punto para reducir la cantidad de decisiones opcionales:
A partir de este ejemplo, podemos resumir una técnica para diseñar algoritmos de programación dinámica: la transición de estado generalmente se realiza entre dos etapas adyacentes (a veces también puede ser entre dos etapas no adyacentes), pero trate de no realizarse dentro de la misma etapa.
La programación dinámica es un método de resolución de problemas muy flexible. Existen muchas técnicas similares en el diseño de algoritmos de programación dinámica. Hay dos formas de dominar las habilidades de la programación dinámica: una es comprender profundamente la esencia de la programación dinámica, razón por la cual discutimos su esencia desde el principio, la otra es practicar más, no solo para resolver más problemas, sino también para resolver más problemas; Aprender a explorar patrones y resumir habilidades de resolución de problemas.
§3 Comparación entre programación dinámica y algunos algoritmos
La programación dinámica, como uno de los muchos métodos de resolución de problemas, debe tener muchas conexiones con otros algoritmos. A partir de estas conexiones, también podemos ver algunas características de la programación dinámica.
§3.1 Programación dinámica y recursividad
——La programación dinámica es un algoritmo de optimización
Porque lo "famoso" de la programación dinámica es tan grande que muchas personas y Incluso algunos libros de información a menudo consideran un algoritmo que es muy similar a la programación dinámica como programación dinámica. Este algoritmo es recursivo. De hecho, los dos algoritmos son fáciles de distinguir.
Según el objetivo de la resolución de problemas, las preguntas de la prueba de informática se dividen principalmente en cuatro categorías: preguntas de juicio, preguntas estructurales, preguntas de conteo y preguntas de optimización. La mayoría de los problemas que encontramos en las competiciones son problemas de optimización y la programación dinámica es un arma poderosa para resolver problemas de optimización. Por lo tanto, el estado de la programación dinámica en las competiciones aumenta día a día. El método recursivo también es una herramienta poderosa para abordar problemas de decisión y problemas de conteo. Tomemos dos ejemplos para hablar sobre la conexión entre el método recursivo y la programación dinámica en estos dos aspectos.
[Ejemplo 4] Problema de ruta óptima Mod 4: encuentre una ruta desde el punto 1 al punto 4 en la siguiente figura. Se requiere que el resto de la longitud de la ruta mod 4 sea el más pequeño.
Esta imagen es una imagen de múltiples segmentos y es una imagen especial de múltiples segmentos. Aunque la forma de este gráfico es más simple que un gráfico general de múltiples segmentos, este problema de ruta óptima no se puede resolver mediante programación dinámica. Debido a que un camino óptimo del punto 1 al punto 4, cuando llega al punto 2 y al punto 3, el resto de la longitud del camino mod 4 no es necesariamente el más pequeño, es decir, la subestrategia de la estrategia óptima no es necesariamente el más pequeño. Óptimo: este problema no satisface el principio de optimización.
Pero podemos convertirlo en un problema de decisión y utilizar la recursividad para resolverlo. Determine si existe una ruta con una longitud mod 4 de sk desde el primer punto hasta el k-ésimo punto, representada por fk(sk), la fórmula de recursividad es la siguiente:
(condición de límite)
(Aquí lenk, i representa la longitud del i-ésimo lado desde el punto k-1 hasta el k-ésimo punto, y los corchetes representan la operación "o")
El final El resultado es el valor más pequeño de s4 que puede hacer que el valor de f4(s4) sea verdadero.
La fórmula de recursividad de este método de recursividad es muy similar a la ecuación de planificación de la programación dinámica. Aquí tomamos prestado el símbolo de la programación dinámica para mostrar este punto más claramente. De hecho, sus ideas son muy similares. Se puede decir que el método recursivo toma prestada la idea de la programación dinámica para resolver problemas que la programación dinámica no puede resolver.
Para algunos problemas de toma de decisiones de múltiples etapas (las características de la etapa de este problema son obvias), la programación dinámica no se puede aplicar porque no se pueden cumplir los requisitos previos para usar la programación dinámica, como los principios de optimización. En este momento, el valor de la función de índice óptima puede considerarse como un "estado" y colocarse en el subíndice, convirtiendo así el problema de optimización en un problema de juicio y luego tomando prestada la idea de programación dinámica y utilizando el método recursivo. para resolver el problema.
[Ejemplo 5] Consulte el apéndice de las preguntas del examen Nail and Ball (NOI99).
Esta pregunta recuerda inmediatamente a la gente una pregunta clásica de programación dinámica. Repasemos primero esta cuestión.
Triángulo digital (IOI94) En la figura siguiente, encuentre una ruta desde la parte superior hasta algún lugar bajo, de modo que la suma de los números pasados por la ruta sea la más grande. Cada paso solo puede ir a la parte inferior. izquierda o abajo a la derecha.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
En este problema, dividimos las etapas según el número de filas que hemos caminado, y usamos la posición cuando llegamos a cada fila como estado. La decisión es bajar a la izquierda (representada por 0). o abajo a la derecha Ir (representado por 1).
Ecuación de transición de estado:
Ecuación de planificación:
Condiciones de contorno:
Este es un problema de optimización relativamente simple. También tenemos este problema. se puede convertir en un problema de estadística entera más simple: encuentre el número total de caminos desde el vértice hasta cada punto. Representa este total como fk(sk), entonces la fórmula recursiva es:
Aquí, aunque la fórmula de suma solo tiene dos términos, todavía la expresamos en la forma de ∑ solo para resaltar esta fórmula recursiva. Similitud con la ecuación de planificación anterior. Las condiciones de contorno de estas dos fórmulas son exactamente las mismas.
Volviendo a nuestro problema anterior de "clavo y bola", este es un problema de probabilidad y estadística. Continuamos usando la idea anterior y usamos fk (sk) para representar la probabilidad de que la bola caiga en el sk-ésimo clavo en la k-ésima fila. La fórmula recursiva es la siguiente:
(Aquí. la función Existk(sk) representa el sk-ésimo clavo. Si el sk-ésimo clavo en la fila k existe, tome 1 si existe y 0 si no existe)
Condiciones de contorno
Se puede ver que hay ligeros cambios en comparación con las dos fórmulas anteriores, pero la idea básica sigue siendo similar. En el proceso de resolver este problema, utilizamos una vez más la idea de programación dinámica.
En términos generales, muchos problemas de optimización tienen problemas de conteo correspondientes; por el contrario, muchos problemas de conteo también tienen problemas de optimización correspondientes. Por lo tanto, cuando nos encontramos con estos dos tipos de problemas, también podemos hacer más conexiones, desarrollar más, hacer inferencias de un ejemplo y obtener una comprensión más profunda de la idea de programación dinámica a partir de la comparación.
De hecho, las ideas de los dos métodos de recursividad y programación dinámica son muy similares, y no es necesario decir quién tomó prestada la idea de quién. La clave es que debemos dominar esta idea, para que podamos estar tranquilos ya sea que usemos programación dinámica para resolver problemas de optimización o usemos métodos recursivos para resolver problemas de determinación y conteo.
§3.2 Programación y búsqueda dinámicas
——La programación dinámica es un algoritmo de alta eficiencia y alto consumo
También resuelve problemas de optimización. Problemas de programación dinámica y, para algunas preguntas, necesitamos utilizar la búsqueda. ¿Hay alguna regla para esto?
Sabemos que, independientemente de los factores de eficiencia espacio-temporal, se puede decir que la búsqueda es "universal" en algoritmos para la resolución de problemas de optimización. Por tanto, los problemas que la programación dinámica puede resolver también se pueden resolver mediante la búsqueda.
Es muy conveniente reescribir un algoritmo de programación dinámica en una búsqueda. La ecuación de transición de estado, la ecuación de planificación y las condiciones de contorno se pueden "trasplantar" directamente. La programación dinámica es una solución recursiva de abajo hacia arriba, mientras que la búsqueda es una solución recursiva de arriba hacia abajo (aquí se refiere a la búsqueda en profundidad, la búsqueda de ancho es similar).
A su vez, también podemos reescribir el algoritmo de búsqueda en programación dinámica. La búsqueda en el espacio de estados es en realidad una enumeración de puntos en el gráfico implícito, y esta enumeración es de arriba hacia abajo. Si el orden de enumeración se invierte y se vuelve de abajo hacia arriba, entonces se convierte en programación dinámica. (Por supuesto, aquí hay una condición, es decir, los puntos en el gráfico implícito se pueden ordenar; consulte la siguiente sección para obtener más detalles).
Debido a que la programación dinámica y la búsqueda tienen diferentes órdenes de solución, esto también causa diferencias en su eficiencia del tiempo. Durante la búsqueda, a menudo ocurre la siguiente situación:
Para un gráfico implícito compuesto por varios estados como (a) arriba, se producirá duplicación cuando se utiliza el algoritmo de búsqueda, como se muestra en (b) arriba, estado C2 Se busca dos veces. En la búsqueda en profundidad, dichas repeticiones provocarán búsquedas repetidas en todo el árbol de subbúsqueda con C2 como raíz; aunque dichas repeticiones se pueden eliminar de inmediato, el costo de tiempo no es pequeño; La programación dinámica no tiene este problema, como se muestra en (c) arriba.
En términos generales, la ventaja del algoritmo de programación dinámica en cuanto a eficiencia del tiempo no tiene comparación con la búsqueda. (Por supuesto, para algunas preguntas, no habrá ninguna duplicación de estados, por lo que no habrá diferencia en la velocidad de búsqueda y programación dinámica.
) Teóricamente, cualquier algoritmo de búsqueda en un gráfico implícito que esté ordenado topológicamente (esta condición a menudo se cumple en la realidad) se puede reescribir como programación dinámica. Pero, de hecho, en muchos casos todavía tenemos que utilizar algoritmos de búsqueda. Entonces, ¿existen obstáculos en la implementación de algoritmos de programación dinámica?
Considere el gráfico implícito que se muestra en (a) arriba, donde hay dos estados que son inalcanzables desde el estado inicial. En el algoritmo de búsqueda, estos dos estados no se consideran, como se muestra en (b) arriba. Sin embargo, dado que la programación dinámica se resuelve de abajo hacia arriba, no puede estimar este punto, por lo que atraviesa todos los estados, como se muestra en (c) arriba.
En términos generales, la programación dinámica siempre atraviesa todos los estados y la búsqueda puede excluir algunos estados no válidos. Más importante aún, la búsqueda también se puede podar, lo que puede eliminar una gran cantidad de estados innecesarios, por lo que la sobrecarga de espacio suele ser mucho menor que la programación dinámica.
¿Cómo coordinar la contradicción entre la alta eficiencia y el alto consumo de la programación dinámica? Un compromiso es el algoritmo memorizado. El algoritmo de memorización todavía sigue un orden de arriba hacia abajo al resolver, pero cada vez que se resuelve un estado, su solución se guarda, de modo que cuando se vuelva a encontrar el estado en el futuro, no hay necesidad de resolverlo nuevamente. Este método combina las ventajas de la búsqueda y la programación dinámica, por lo que sigue siendo muy práctico.
§3.3 Programación dinámica y flujo de red
——La programación dinámica es un algoritmo que es fácil de diseñar e implementar
Debido a que la relación entre gráficos es compleja y desordenado, generalmente es difícil presentar características de fase (a excepción de gráficos especiales como gráficos de múltiples segmentos o métodos de segmentación especiales como Floyd), por lo que la programación dinámica tiene pocas aplicaciones en la teoría de grafos. Pero existe un tipo de gráfico cuyos puntos están ordenados, que es un gráfico acíclico dirigido.
En un gráfico acíclico dirigido, podemos ordenar topológicamente los puntos para que exhiban características ordenadas y luego dividir las etapas en consecuencia. El algoritmo para encontrar el camino más corto en un gráfico dirigido sin retorno [4] ha reflejado la idea simple de programación dinámica. Pero la programación dinámica tiene aplicaciones más valiosas en la teoría de grafos. Veamos primero un ejemplo.
[Ejemplo 6] Problema de la calle de N personas: en el problema de la calle (ver Ejemplo 3), si hay N personas que quieren ir desde la esquina inferior izquierda a la esquina superior derecha, la longitud total de los lados por los que caminan debe ser el más grande. Por supuesto, aquí todos sólo pueden ir hacia la derecha o hacia arriba. La siguiente es un ejemplo. La imagen de la izquierda muestra los tres caminos desde el punto de partida hasta el destino. La imagen de la derecha muestra los bordes que han recorrido. La longitud total de estos bordes es 5 + 4 + 3 + 6 + 3 + 3 +. 5 + 8. + 8 + 7 + 4 + 5 + 9 + 5 + 3 = 78 (no necesariamente el máximo).
Este tema es otra ampliación del problema de la calle. Siguiendo el método de solución del problema de la calle, aún podemos utilizar la programación dinámica para resolver este problema. Pero esta vez, N personas caminan al mismo tiempo y las variables de estado deben representarse en N dimensiones. En consecuencia, la variable de decisión también debe volverse N-dimensional, uk=(uk,1,uk,2,…,uk,N). No es necesario cambiar la ecuación de transición de estado:
Al escribir la ecuación de planificación, debe prestar atención al cálculo de la longitud total de los bordes recorridos por los N caminos en la k-ésima etapa. Utilizo gk (sk, uk) para expresar:
La condición de contorno es
Se puede ver que, en teoría, es completamente factible trasplantar el algoritmo de programación dinámica original a este problema. . Sin embargo, la complejidad espacio-temporal del algoritmo de programación dinámica actual ya es una función exponencial de N. Mientras N sea un poco mayor, este algoritmo será imposible de implementar.
Cambiemos nuestra forma de pensar y consideremos N caminos como un flujo con un caudal de N en la red. El objetivo de resolver este problema es maximizar el costo de este flujo. Sin embargo, este problema es diferente del problema general del flujo de costos. El costo del flujo en cada borde e no es el producto del flujo y el peso del borde, sino que se calcula mediante la siguiente fórmula:
Para Para hacer que el algoritmo clásico de flujo de costos sea aplicable a esta pregunta, necesitamos transformar ligeramente el modelo:
Como se muestra en la figura, divida cada borde en dos. Después de la división, un borde tiene derechos, pero la capacidad está limitada a 1; el otro borde no tiene límite de capacidad, pero el costo no se puede calcular si fluye a través de este borde. De esta manera transformamos el problema en un problema estándar de flujo fijo de costo máximo.
Este algoritmo se puede aplicar al clásico algoritmo de flujo máximo de costo mínimo, que no se describirá en detalle aquí.
(Consulte el programa fuente en el apéndice)
Esta pregunta de ejemplo se basa en la pregunta "Detector de obstáculos" de IOI97 [6]. "Detección de obstáculos