Quiero aprender sobre programación dinámica
Para dominar las habilidades de aplicación de la programación dinámica, debemos comprender sus características en todos los aspectos. Primero, debes tener un conocimiento profundo de 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 y se utiliza 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
Hablando de problemas de toma de decisiones en varias etapas, podemos dar fácilmente los siguientes ejemplos.
[Ejemplo 1] Problema de ruta más corta en un gráfico de varias etapas: encuentre la ruta más corta de A1 a D1 en el siguiente gráfico.
Mirando atentamente esta imagen, no es difícil descubrir que tiene una característica. Dividimos los puntos del gráfico en cuatro categorías (A, B, C y 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 el siguiente. Por lo tanto, las aristas del gráfico se dividen en tres categorías (A?8?1B, B?8?1C, C?8?1D). Necesitamos elegir una arista de cada categoría que forme un camino de A1 a D1 que sea 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 es un tipo especial de proceso proactivo que descompone cronológicamente un problema en una serie de etapas interrelacionadas, en las que se debe tomar una decisión. y la toma de decisiones de todo el proceso es una serie de decisiones [1]. El problema de optimizar el efecto general de toda la actividad se denomina problema de toma de decisiones en varias etapas.
Como se desprende de la definición anterior, este tipo de problema tiene dos elementos. Una es una etapa y la otra es una decisión.
§1.2 Fases y Estados
Fase: Dividir el procesamiento de un problema determinado en una serie de etapas interconectadas, caracterizadas por el tiempo o el espacio, de modo que cada etapa pueda resolverse en girar la pregunta. Las variables de fase suelen estar representadas por la letra k. [1]
Las etapas son propiedades del problema. En términos generales, las fases están relacionadas con el tiempo, pero en muchos problemas (en mi opinión, especialmente los problemas informáticos), las fases no están relacionadas con el tiempo. De la definición de etapas, podemos ver dos características de las etapas, una es "interrelación" y la otra es "orden".
¿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 y sk generalmente se usa para representar la variable de estado de la etapa k. El conjunto de valores de la variable de estado sk se denomina conjunto de estados y está representado por Sk. [1]
El estado es una propiedad de una etapa. Cada etapa suele contener varios estados, que describen la situación objetiva cuando el problema llega a esa etapa. En el ejemplo anterior, después de partir desde el punto de partida A1 y pasar por dos etapas, el peatón tiene tres situaciones posibles, concretamente en el punto C1, C2 o C3. En la tercera etapa, hay tres estados S3={C1,C2,C3}.
El estado de cada etapa tiene algún tipo de "cambio" respecto al estado de la etapa anterior. Este "cambio" se denomina transición de estado (aún no definido). En el ejemplo anterior, el punto C3 puede provenir del punto B1 o del punto B2, y pasar del estado B1 o B2 en la etapa 2 al estado C3 en la etapa 3 es una transición de estado. Las transiciones de estado son una forma de derivar estados y fases de conexión.
Dicho esto, se puede plantear una condición importante para aplicar 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 la etapa anterior no puede afectar directamente su desarrollo futuro, solo puede verse afectado por el estado actual. En otras palabras, cada estado es "un resumen completo de la historia pasada[1]". Esto significa que no hay a posteriori. Esta característica también se explica 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, y el siguiente contenido es otro aspecto, es decir , los elementos de la toma de decisiones.
Toma de decisiones: Luego de obtener el estado de cada segmento, se pueden tomar diferentes decisiones para determinar el estado de la siguiente etapa. Las variables que representan la toma de decisiones se denominan variables de decisión, y uk (sk) se usa comúnmente para representar la variable de decisión cuando el estado de la k-ésima etapa es sk. En problemas prácticos, los valores de las variables de decisión suelen estar limitados a un cierto rango, al que llamamos conjunto de decisión permitido. Es común utilizar Dk(sk) para representar el conjunto de decisiones permitidas en la k-ésima etapa a partir del estado sk. Obviamente, existen uk(sk) ?8?3Dk(sk).[1]
La toma de decisiones es una propiedad de la resolución de problemas. El propósito de la toma de decisiones es "determinar el próximo estado del problema". Volviendo al ejemplo anterior, hay tres caminos o tres decisiones desde el estado B1 en la etapa 2 hasta los estados C1, C2 y C3 en la etapa 3, a saber, D2(B1)={C1,C2,C3}.
Con la toma de decisiones, podemos definir la transición de estado: el estado de la etapa actual en la programación dinámica es a menudo el resultado de la etapa anterior y la decisión de la etapa anterior, que consiste en el estado sk del etapa k+1 y etapa actual El proceso mediante el cual la decisión uk determina el estado sk+1 de la etapa k+1 se llama transición 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.
De esta manera, parece haber cierta conexión entre la toma de decisiones y la transición estatal. Según tengo entendido, 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.
Después de determinar la toma de decisiones de cada enlace, la secuencia de toma de decisiones de todo el problema constituye una estrategia, utilizando p1,n={u1(s1),u2(s2),..., un(sn )} expreso. Para cada problema práctico, existe una gama de políticas disponibles, denominada conjunto de políticas permitidas, denotado por P1,n. La estrategia que tiene el mayor impacto en todo el problema es la estrategia óptima. [1]
En resumen, se puede extraer otra premisa para aplicar la programación dinámica. Es decir, la estrategia óptima de este proceso debe tener las siguientes características: 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 pocas palabras, significa que "las subpolíticas de una política óptima también son políticas óptimas".
§1.4 Principio de optimización y ninguna propiedad a posteriori
Aquí posiciono el principio de optimización como "un requisito previo para utilizar la programación dinámica". Esto se debe a que el cumplimiento o no del principio de optimización es la característica esencial del 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 nada que ver con la decisión uk de cualquier etapa k o la subpolítica pk1,k2 de cualquier etapa k1. .k2. Si tuviéramos que realizar una programación dinámica sobre un problema de este tipo, nuestros esfuerzos por prepararlo desde el principio serían en vano.
La razón por la que uso "no a posteriori" como "condición para aplicar la programación dinámica" es porque la programación dinámica resolverá los problemas en cada etapa en secuencia, y si el problema es a posteriori, entonces esto El orden no es razonable. Sin embargo, podemos hacer que el problema satisfaga la condición de no a posteriori volviendo a dividir las etapas, volviendo a seleccionar el estado o aumentando el número de variables de estado. En última instancia, todavía se trata de determinar la "secuencia".
La informática para problemas de toma de decisiones de múltiples etapas, la mayoría de ellos pueden satisfacer el principio de optimización, pero a menudo presentan obstáculos en el punto posterior. Por tanto, en el proceso de resolución del problema, prestaremos especial atención al problema "ordenado". Para problemas ordenados, consideraremos la programación dinámica; para problemas desordenados, intentaremos 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 expresado como fk(sk), que representa el valor de beneficio óptimo desde el k-ésimo estado sk utilizando la estrategia óptima p*k,n hasta el proceso de terminación [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).
La función de índice óptima suele ser una fórmula recursiva que comienza desde el estado objetivo, llamada ecuación de planificación:
Donde sk es un determinado estado en el segmento de carretera k, uk es el valor permitido de sk Una decisión en el conjunto de decisiones Dk(sk), Tk(sk,uk) es un cierto estado sk+1 en el segmento de carretera k+1 derivado de sk y uk, g(x, uk) se define en el valor x y la función de decisión en el Reino Unido, la función opt representa la optimización y está representada por max o min según el problema específico.
, llamadas condiciones de contorno.
La ecuación de planificación en el ejemplo anterior es:
La condición de contorno es
Aquí hay un método de solución de orden inverso desde el estado objetivo al estado objetivo, que es aplicable El problema de determinar el estado objetivo. En nuestros problemas informáticos, también hay muchos problemas en los que se determina el estado inicial. Por supuesto, para el problema de determinar el estado inicial, también podemos utilizar un método de solución secuencial para avanzar desde el estado inicial. De hecho, este enfoque nos resulta más intuitivo y fácil de diseñar, por lo que aparece con más frecuencia en nuestros procesos de resolución de problemas.
Las teorías que comentamos en esta sección, aunque no son el foco principal de este artículo, juegan un papel fundamental a la hora de describir las características de la programación dinámica, como veremos a continuación.
§2 Diseño e implementación de programación dinámica
Arriba analizamos algunas teorías de la programación dinámica. En esta sección aprenderemos sobre la dinámica a través de varios ejemplos de diseño e implementación de programación dinámica. Características de la programación.
§2.1 Diversidad de programación dinámica
[Ejemplo 2] Problema de diseño de escaparate de floristería (IOI99) Las preguntas del examen se encuentran en el apéndice
Este problema está en IOI de este año Una de las preguntas más simples, pero con mucho que ofrecer. Se dice simple porque está organizado, por lo que podemos ver de un vistazo que se debe resolver mediante programación dinámica. ¿Pero cómo hacer 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 i-ésimo ramo de flores insertado en el j -ésimo jarrón Valor estético)
Condiciones de límite (V es el número total de jarrones, que en realidad 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
Los métodos de división en dos etapas conducen a dos estados representaciones y dos métodos de planificación, pero todos resolvieron con éxito el problema. Es solo que la complejidad temporal del algoritmo es diferente porque hay cada vez menos opciones para tomar decisiones. [2]
Este ejemplo es muy común. Muchos problemas de decisión de múltiples etapas tienen más de una forma de dividir las etapas y, por lo tanto, a menudo más de un método de planificación. A veces, estos métodos producen resultados similares, pero más a menudo, como en nuestro ejemplo, los dos métodos difieren de alguna manera.
Entonces, cuando utilices la programación dinámica para resolver un problema, considera si existen otras soluciones. Para diferentes soluciones, es importante comparar qué hace que un buen algoritmo sea mejor y qué empeora un mal algoritmo. A partir de la comparación de diferentes algoritmos, podemos obtener una comprensión más profunda de las técnicas de conceptualización de la programación dinámica.
§2.2 El modelo 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. Existen ciertas reglas para el diseño de programación dinámica, que generalmente pasan por los siguientes pasos.
División de fases: Divide el problema en varias etapas en función de las características temporales o espaciales del problema. Es importante tener en cuenta que las etapas deben ordenarse o clasificarse, de lo contrario el problema no se podrá resolver.
Selección de estado: Colocar la situación objetiva del problema en diferentes estados en diferentes etapas. Por supuesto, la elección del Estado no debería satisfacer propiedades a posteriori.
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. etapa anterior. Entonces, si determinamos la decisión, se escribe la ecuación de transición de estado. Pero, de hecho, a menudo hacemos lo contrario y tomamos decisiones basadas en la relación entre los respectivos estados de dos segmentos adyacentes.
Escribir la ecuación de planificación (incluidas las condiciones de contorno): En la primera parte, dimos la 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 teórico, la parte de implementación es muy sencilla. El marco general es el siguiente:
Inicializar f1(s1) (condición de límite)
Para k?3Sk
fk(sk)?8?0 an valor extremo ( ∞ o -∞)
Para cada A uk(sk)?8?3Dk(sk)
sk-1?8?0Tk(sk,uk)
t??0g(fk-1(sk-1),uk)
y t es mejor que fk(sk) n
fk(sk)?8 ?0t
Salida fn(sn)
Este diagrama N-S no representa todo, pero es suficiente para resumir la mayoría de ellos. Podemos hacer una analogía con alguna programación dinámica especial, que se implementa de manera similar. Hasta ahora, nuestro análisis de la programación dinámica se ha centrado principalmente en la teoría y el diseño, y este es el motivo.
Después de dominar las reglas de la programación dinámica, cuando utilizamos la programación dinámica para resolver problemas, podemos centrarnos en el diseño teórico. Una vez que el diseño madura, el problema básicamente se resuelve. El diseño del algoritmo también se puede realizar paso a paso.
Sin embargo, "todo lo que se gana debe venir acompañado de una pérdida". Ser demasiado rígido en un modelo limitará nuestro pensamiento y sofocará el buen pensamiento algorítmico. Cuando resolvemos problemas, también podemos usar nuestra creatividad y romper con el modelo de programación dinámica, que a menudo produce resultados inesperados. [3]
§2.3 Las habilidades de la programación dinámica
El modelo de programación dinámica que mencionamos anteriormente se refiere principalmente al aspecto de implementación. En cuanto al diseño, aunque sus pasos son relativamente estrictos, sus ideas de diseño no siguen un patrón determinado. Esto requiere que dominemos continuamente las habilidades de programación dinámica en la práctica. Lo siguiente solo utiliza mi propia experiencia como 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, y cada paso solo puede ir hacia la derecha o hacia arriba.
Este es un problema de programación dinámica simple y típico. Muchos libros y artículos que presentan la programación dinámica lo utilizan como ejemplo. 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 qué punto de la etapa se está alcanzando actualmente (la etapa y el estado correspondientes a cada punto están marcados con ks en la figura). En este punto, el modelo se ha transformado en un mapa especial de varias etapas. Usar la variable de decisión uk=0 significa ir hacia la derecha, uk=1 significa subir, la ecuación de transición de estado es la siguiente:
(El número de filas aquí es el número de filas en la dirección vertical de la map)
Vemos que dependiendo del valor de k, esta ecuación de transición de estado debe discutirse en dos casos, lo que parece muy problemático. En consecuencia, si este algoritmo se sustituye en la ecuación de planificación para la práctica, también será muy engorroso.
Por lo tanto, cuando lo implementamos, generalmente no hacemos esto, sino que utilizamos el siguiente método:
Los puntos en el mapa se numeran regularmente de acuerdo con el método anterior y la ecuación de planificación es la siguiente:
(La distancia aquí se refiere a la longitud del lado entre dos puntos adyacentes)
Este método es de hecho mucho más simple que el método anterior, pero destruye la cara original de la programación dinámica y tiene sin características escénicas claras. Si este enfoque dividiera las etapas por filas en el mapa (A, B, C, D), entonces no todo serían "transiciones de estado" entre etapas.
Quizás esto no sea gran cosa porque la práctica es mejor que la teoría. Pero ampliemos un poco el problema: busque dos caminos en el mapa desde la esquina inferior izquierda hasta la esquina superior derecha, sin bordes superpuestos y con la longitud total más corta de los dos caminos. En este punto, este método "simple" no funciona tan bien.
Si debemos utilizar este método, la función indicadora óptima requiere un subíndice de cuatro dimensiones y es difícil abordar el problema de que las dos rutas "no se pueden superponer".
Volviendo al enfoque de programación dinámica "estándar" original, descubrimos que este problema podría resolverse fácilmente simplemente agregando una variable de estado unidimensional. Es decir, sk = (ak, bk) representa respectivamente los dos caminos que conducen a la posición de la etapa k. En consecuencia, la variable de decisión también agrega una dimensión, y uk = (xk, yk) representa la dirección de viaje del. dos caminos respectivamente.
Al escribir la ecuación de planificación, solo necesitamos abordar ligeramente los dos caminos hasta el mismo punto para reducir el número de decisiones opcionales:
De este ejemplo, podemos concluir A Técnica para diseñar algoritmos de programación dinámica: las transferencias de estado generalmente se realizan entre dos etapas adyacentes (y a veces entre dos etapas no adyacentes), pero trate de no hacerlo dentro de la misma etapa. Pero intenta no hacerlo dentro de la misma etapa.
La programación dinámica es un método muy flexible para resolver problemas y 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 comenzamos a explorar su esencia, la otra es practicar más, no solo para resolver más problemas, sino también para resolver más problemas; aprender a aprender de la resolución de problemas Explorar patrones y resumir técnicas.
§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
Debido a la gran "fama" de la programación dinámica, muchas personas e incluso Algunos libros tienden a referirse a 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 resolver problemas, las preguntas del examen de informática se pueden dividir en cuatro categorías: problemas deterministas, problemas constructivos, problemas de conteo y problemas 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 que el estado de la programación dinámica en las competiciones aumenta día a día. Los métodos recursivos también son un arma poderosa para abordar problemas deterministas y de conteo. Aquí hay dos ejemplos para ilustrar la conexión entre la recursividad y la programación dinámica en estos dos campos.
[Ejemplo 4] Problema de ruta óptima del módulo 4: encuentre una ruta desde el punto 1 al punto 4 en la figura siguiente que minimice el resto de la longitud de la ruta módulo 4.
Esta imagen es una imagen de múltiples segmentos y es una imagen especial de múltiples segmentos. Aunque la forma del gráfico es más simple que la de un gráfico multisegmento ordinario, este problema de ruta óptima no puede resolverse mediante programación dinámica. La razón es que la ruta óptima desde el punto 1 al punto 4 no necesariamente minimiza el resto de la longitud de la ruta mod 4 al pasar por los puntos 2 y 3, lo que significa que la subpolítica de la política óptima no es necesariamente la óptima. - Este problema no cumple con el principio de optimización.
Pero podemos convertirlo en un problema determinista y resolverlo de forma recursiva.
Para determinar si existe un camino sk con longitud mod 4 desde el punto 1 hasta el punto k, representado por fk(sk), la fórmula recursiva es la siguiente:
(condición de contorno)
(aquí lenk,i representa la longitud del i-ésimo borde entre el punto k-1 y el punto k, y los corchetes representan la operación "o (o)")
El resultado final es que es posible hacer que el valor de f4(s4) se convierta en el verdadero valor mínimo de s4.
La fórmula recursiva de este método recursivo es muy similar a la ecuación de planificación de la programación dinámica. Aquí tomamos prestada la notación de programación dinámica solo para ilustrar este punto más claramente. De hecho, sus ideas son muy similares. Se puede decir que el método recursivo toma prestadas las ideas de la programación dinámica para resolver problemas que no pueden resolverse mediante la programación dinámica.
Algunos problemas de toma de decisiones de múltiples etapas (por ejemplo, las características de la etapa de esta pregunta son muy obvias), porque no se pueden cumplir los requisitos previos para usar la programación dinámica, como el principio de optimización, y la programación dinámica no ser aplicado. En este caso, el valor de la función indicadora óptima se puede poner en el subíndice como "estado", convirtiendo así el problema de optimización en un problema determinista y luego tomando prestada la idea de programación dinámica para resolver el problema utilizando el método recursivo.
[Ejemplo 5] Nails and Balls (NOI99) Consulte el apéndice para las preguntas del examen
Esta pregunta recuerda a los problemas clásicos de programación dinámica. Primero revisemos las siguientes preguntas.
Triángulos digitales (IOI94) En la siguiente figura, encuentre una ruta de arriba a abajo de manera que la suma de los números pasados por la ruta sea la más grande y cada paso solo vaya hacia la parte inferior izquierda. esquina o la esquina inferior derecha.
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
En este problema, dividimos el número de etapas por el número de filas recorridas y usamos la posición al viajar a cada fila como estado para decidir si ir a la parte inferior izquierda (representada por 0) o hacia la derecha debajo (indicado 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 podemos transformar esto en un problema de estadística entera más simple: encuentre el número total de caminos desde un vértice hasta cada punto. Al expresar este total como fk(sk), la fórmula de recursión es:
Aquí, aunque la fórmula de suma tiene solo dos términos, todavía la expresamos en la forma de ∑, solo para resaltar esta similitud entre la recurrencia fórmula y la ecuación de planificación anterior. Las condiciones de contorno de estas dos fórmulas son exactamente las mismas.
Volviendo al problema anterior de "clavos y bolas", este es un problema de probabilidad y estadística. Continuamos siguiendo 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:
(The. La función Existk(sk) aquí representa si el sk-ésimo clavo en la k-ésima fila existe o no, si existe, toma 1, si no existe, toma 0)
Condiciones de contorno
Se puede ver que esta fórmula es consistente con lo anterior. Hay ligeros cambios entre las dos fórmulas, pero la idea básica sigue siendo similar. Al 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, expandirnos más, hacer inferencias de un ejemplo y profundizar nuestra comprensión de las ideas de programación dinámica a través de la comparación.
De hecho, las ideas de recursividad y programación dinámica son muy similares. No hace falta decir quién tomó prestadas las ideas de quién. La clave es dominar esta idea, de modo que cuando usemos programación dinámica para resolver problemas de optimización, o usemos métodos recursivos para resolver problemas de determinación y conteo de tipos, podamos hacerlo con facilidad.
§3.2 Búsqueda y programación dinámica
--La programación dinámica es un algoritmo eficiente y de alto costo
También se utiliza para resolver problemas de optimización. preguntas, usamos programación dinámica y necesitamos usar la búsqueda para algunas preguntas. ¿Hay alguna regla para esto?
Sabemos que, independientemente de los factores de eficiencia de espacio y tiempo, se puede decir que la búsqueda es "universal" en los algoritmos para resolver problemas de optimización. Entonces, si la programación dinámica resuelve el problema, la búsqueda también debe resolver el problema.
Es muy conveniente reescribir el algoritmo de programación dinámica en 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 (la búsqueda en profundidad y la búsqueda en ancho aquí son similares).
A su vez, podemos reescribir el algoritmo de búsqueda como 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 invierte el orden de la enumeración y lo hace de abajo hacia arriba, 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).
Es precisamente porque los órdenes de solución de la programación dinámica y la búsqueda son diferentes, lo que también resulta en diferencias en su eficiencia de tiempo. Durante la búsqueda, suelen ocurrir las siguientes situaciones:
Para un gráfico implícito compuesto de múltiples estados, como se muestra en (a) arriba, el algoritmo de búsqueda se repetirá, como se muestra en (b) arriba, estado C2 Se busca dos veces. En una búsqueda profunda, esta duplicación hará que todo el árbol de subbúsqueda con raíz en C2 se busque repetidamente en una búsqueda amplia. Aunque esta duplicación se puede 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, los algoritmos de programación dinámica tienen ventajas sobre la búsqueda en términos de eficiencia de tiempo. (Por supuesto, para algunos temas, la duplicación de estados no ocurre en absoluto, por lo que no hay diferencia en la velocidad entre la búsqueda y la programación dinámica). Y, en teoría, 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) puede reescribirse como programación dinámica. Pero, de hecho, en muchos casos todavía tenemos que utilizar algoritmos de búsqueda. Entonces, ¿existen otros obstáculos para implementar 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, como se muestra en (b) arriba, no es necesario considerar estos dos estados. Sin embargo, la programación dinámica no puede estimar esto porque se resuelve de abajo hacia arriba y, por lo tanto, atravesará 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 eliminará algunos estados no válidos. Más importante aún, la búsqueda también se puede podar, eliminando potencialmente 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 alta eficiencia y el alto costo de la programación dinámica? Un compromiso es el algoritmo de memorización. El algoritmo de memoria todavía procede en orden de arriba hacia abajo al resolver, pero cada vez que se resuelve un estado, su solución se guardará y, cuando se vuelva a encontrar el estado en el futuro, no es necesario resolverlo nuevamente. Este enfoque combina las ventajas de la búsqueda y la programación dinámica, por lo que sigue siendo muy útil.
§3.3 Programación dinámica y flujo de red
--La programación dinámica es fácil de diseñar e implementar algoritmos
Debido a que los gráficos tienen relaciones complejas y desordenadas, generalmente es Es difícil presentar características de fase (a excepción de gráficos especiales, como gráficos de particiones múltiples o métodos de partición especiales como Floyd), por lo que la programación dinámica no tiene muchas aplicaciones en la teoría de grafos. Sin embargo, 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 reflejen el orden y dividir las etapas en consecuencia. El algoritmo para encontrar el camino más corto en un gráfico acíclico dirigido [4] ya incorpora la idea simple de programación dinámica. Pero la programación dinámica tiene muchas más aplicaciones valiosas en la teoría de grafos. He aquí 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, es necesario para maximizar la longitud total. Por supuesto, todo el mundo sólo puede ir hacia la derecha o hacia arriba. Aquí hay un ejemplo. La imagen de la izquierda son los tres caminos desde el punto inicial hasta el punto final. La imagen de la derecha son los bordes por los que caminaron. La longitud total de estos bordes es 5 + 4 + 3 + 6 + 3 + 3 + 5. + 8 + 8 + 8. + 7 + 4 + 5 + 9 + 5 + 3 = 78 (no necesariamente el máximo).
Esta pregunta es otra extensión del problema de la calle. Tras la solución al problema de la calle, todavía 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 también deben representarse en N dimensiones.
Por lo tanto, la variable de decisión debe volverse N-dimensional, es decir, uk=(uk,1,uk,2,...,uk,N). La ecuación de transición de estado no requiere ningún cambio:
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. gk(sk,uk):
La condición de contorno es
Se puede ver que es teóricamente factible trasplantar el algoritmo de programación dinámica original a este problema. Sin embargo, la complejidad temporal y espacial de este algoritmo de programación dinámica es ahora una función exponencial relacionada con N. Mientras N sea un poco mayor, este algoritmo es imposible de implementar.
Aquí cambiamos nuestra forma de pensar y consideramos N caminos como un N flujo en la red, de modo que el objetivo de la solución es maximizar el costo de este flujo. Pero este problema es diferente del problema de flujo de costos habitual. El costo de 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 hacer. El algoritmo de flujo de costo clásico es adecuado para este problema y necesitamos modificar ligeramente el modelo:
Como se muestra en la figura, cada borde se divide en dos. Después de dividir, 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 fluyendo a través de este borde. De esta manera, transformamos el problema en un problema de flujo fijo de costo máximo estándar.
Este algoritmo se puede aplicar al algoritmo clásico de flujo máximo de costo mínimo y no se presentará en detalle aquí. (Consulte el programa fuente en el apéndice).
Este ejemplo se basa en el problema del "detector de obstáculos" [6] en IOI97. "Detector de obstáculos