Programación dinámica

En comparación con los algoritmos codiciosos que buscan soluciones óptimas locales, la programación dinámica busca soluciones óptimas globales (pero no todos los problemas tienen una solución óptima, por ejemplo, los problemas NP-completos no tienen una solución óptima).

Ejemplo: solución de programación dinámica para el problema de la mochila

Descripción del problema:

Ahora hay una mochila que puede contener 4 libras de artículos. Ahora saca los artículos más valiosos del centro comercial y ponlos en tu bolso.

Los artículos en el centro comercial son los siguientes

Cada programación dinámica comienza con una cuadrícula (que se muestra a continuación)

Ahora complete la cuadrícula fila por fila.

Fórmula de cálculo para cada grilla:

El valor máximo actual para líneas de guitarra rellenas es 1500 (guitarra).

Altavoces llenos: el valor máximo actual es 3000 (altavoces)

Cuaderno lleno: el valor máximo actual es 3500 (cuaderno de guitarra)

El principio de programación dinámica es a Un problema grande se descompone en muchos problemas pequeños. Primero se encuentra la solución óptima al problema pequeño y luego se obtiene la solución óptima al problema final en función de la solución óptima al problema pequeño.

En este ejemplo del problema de la mochila, primero encontramos la solución óptima cuando solo hay un tipo de guitarra, luego agregamos elementos gradualmente y finalmente encontramos la solución óptima.

Suplemento a la fórmula de cálculo de la cuadrícula;

En todo el proceso de resolución de programación dinámica, los problemas se resuelven paso a paso desde niveles de problemas pequeños hasta problemas grandes. Naturalmente, el primer punto a considerar para cada cuadrícula es el valor máximo de la cuadrícula anterior. Los nuevos elementos se agregan a la nueva capa, por lo que el valor de los nuevos elementos y las libras máximas restantes disponibles (obtenidas de la capa superior) también deben ser. ser considerado.

Pregunta sobre la mochila agregada:

Si agrega otro artículo: collar {'valor': $1000, 'peso': 0.5 lbs}

En este momento, si se utiliza la malla anterior.

Si los elementos a envasar son avena, dal y arroz, puedes sacarlos parte por parte.

La programación dinámica no puede resolver esta situación, pero la codicia sí.

Problema de ruta de viaje

Por supuesto, podemos utilizar el método de cuadrícula de programación dinámica para obtener la ruta de viaje más valiosa.

Si se añaden las siguientes atracciones,

En el tiempo para ir a las atracciones de París, 0,5 días es el tiempo de Londres a París.

Así, si vas primero a la Torre Eiffel, el tiempo para ir a las otras dos atracciones de París también se reducirá en 2 horas.

En este caso no se puede utilizar el algoritmo de programación dinámica anterior.

Cada subproblema manejado por un algoritmo dinámico es discreto.

Veamos otro caso

Si desea ejecutar un sitio web, la tarea principal del sitio web es: traducción de palabras en inglés. Es decir, el usuario introduce una palabra en inglés y le das la traducción correspondiente. Por ejemplo, el usuario ingresa pescado y el sitio web genera pescado.

Si el usuario ingresa hish, pero la palabra no está en el diccionario, se debe proporcionar una palabra similar.

¿Cuáles son las palabras similares? ¿Determinar la longitud máxima de una subcadena?

Utilice el método de programación dinámica para encontrar la longitud máxima de dos cadenas (fish y hish)

La programación dinámica siempre necesita conocer los elementos de la cuadrícula antes de resolver el problema: < / p>

¿Cuáles son los dos ejes de coordenadas? ¿Cuáles son los valores en la cuadrícula (generalmente los indicadores que se van a optimizar)?

1. Problema de descomposición: si necesita la subcadena más grande de fish y hish, primero puede encontrar la subcadena común más grande de ellos. cuerdas (como fis y his). Teniendo en cuenta que los dos ejes son dos palabras, el valor en la cuadrícula es la longitud de la subcadena más grande.

A continuación, rellena la cuadrícula. Verifique continuamente la fórmula de la celda:

Explicación de la fórmula de la celda:

1) son iguales, la cadena máxima local se expandirá, es decir, diagonal (celda [i] La valor superior a [j]) se incrementará en 1 (donde los valores del índice se acumulan diagonalmente).

2) Si son diferentes, la cadena máxima local es 0.

La longitud máxima de cadena para ambas cadenas es el valor máximo 3 en la cuadrícula.

Si el usuario entra a fosh, ¿debería volver a fish o fort?

Si juzgas en función de la subcadena más grande, se devolverá fuerte, ¡pero de hecho fish y fosh son más similares!

Por lo tanto, consideramos hacer un juicio basado en la longitud máxima de subsecuencia * * * común de las dos cadenas (es decir, el número de caracteres * * * comunes entre las dos cadenas).

La fórmula de celda para encontrar la subsecuencia del máximo común divisor * * * es:

La subsecuencia común más larga de fosh y fort es 2.

La subsecuencia más larga de fosh y pescado es 3.

En este punto, puedes devolver el resultado correcto pescado en lugar de fuerte.

1. La programación dinámica se utiliza generalmente para optimizar el valor de un indicador bajo restricciones determinadas.

2. El principio de la programación dinámica es descomponer grandes problemas en pequeños problemas y resolver gradualmente grandes problemas en las condiciones de resolver pequeños problemas. Una forma de resolver un problema es reducir gradualmente las condiciones, empezando por el caso más simple.

3. Una condición necesaria para utilizar la programación dinámica es que cada pequeño problema descompuesto sea discreto.

4. Cada solución de programación dinámica está diseñada con una grilla.

4.1, cada cuadrícula es un pequeño problema.

4.2. El valor de cada grilla es el valor del indicador.

4.3. Las fórmulas de cálculo de celdas requieren un análisis detallado de cuestiones específicas.