Programación dinámica
La programación dinámica se utiliza para resolver muchos problemas que surgen de la investigación de operaciones, por lo que no enumeraremos los tutoriales relacionados con este método.
La programación dinámica es un método exacto de resolución de problemas
optimización, principalmente debido a R. botones (1957).
Más precisamente, la programación dinámica es un paradigma para diseñar algoritmos que se pueden aplicar para resolver un problema si cumple con la optimización de Bellman.
La programación dinámica es similar en idea al método divide y vencerás. La diferencia significativa entre estos dos métodos es que la programación dinámica permite que los subproblemas se superpongan. En otras palabras, un subproblema puede usarse en la solución de dos subproblemas diferentes. Mientras que el enfoque divide y vencerás crea subproblemas separados que pueden resolverse independientemente unos de otros.
Por lo tanto, la diferencia fundamental entre estos dos métodos es: los subproblemas en la programación dinámica pueden estar interactuando, mientras que en el método de dividir y gobernar no es así.
Una segunda diferencia entre estos dos métodos es, como lo ilustra la figura anterior, es que el método de dividir y reinar es recursivo, la recursividad toma el problema global para dividirlo en un problema elemental. La programación dinámica es un método cuyos cálculos se realizan de abajo hacia arriba: comenzamos resolviendo los subproblemas más pequeños. Combinando su solución, obtenemos las soluciones de subproblemas cada vez más grandes.
Principio
El paradigma se divide en cuatro cuestiones:
- Caracterización de la estructura de una solución óptima.
- Definición recursiva del valor de la solución óptima.
- Cálculo ascendente de la solución.
- Construcción de la solución a partir del cálculo ascendente.
Construimos una tabla para memorizar los cálculos ya realizados: a cada elemento le corresponderá la solución de uno y solo un problema intermedio, y otro para la solución final. Por tanto, es necesario que se puedan determinar los subproblemas que se tratarán durante el cálculo.
Hay dos enfoques para completar la tabla:
- Iterativo: Inicializamos las “casillas” correspondientes a los casos base.
Luego se llena la tabla según un orden muy preciso a determinar: se parte de los problemas de “tamaño” lo más pequeños posible, se termina con la solución del problema principal: es necesario que para cada cálculo, se utilice solo las soluciones ya calculadas. - Recursivo: mismo principio que el enfoque iterativo, este método solo calculará lo estrictamente necesario para lograr el objetivo dado.
Ejemplo: producto de matrices
Sean no matrices M1,…, Mno, cada matriz tiene un número mI de líneas ymyo + 1 columnas, las entradas son números reales (problema lineal). Buscamos calcular M1*… * Mno para minimizar el número de operaciones.
Denotamos por cij el número de operaciones para calcular MI*… * Mj. Entonces tenemos cii= 0 y cyo (yo + 1)= m(i-1)* mI* m(yo + 1) operaciones. Dividamos este subproblema calculando la mejor cij con MI*… * Mk y M(k + 1)*… * Mj. Entoncesij = min [cik + c(k + 1) j + mI* m(k + 1)* m(d + 1)] con k de I Para d-1, el último término equivale a multiplicar los resultados del producto de matrices de I Para k con el de k + 1 Para j.
Entonces tenemos el siguiente programa:
- vsij = 0 si i = j;
- vsyo (yo + 1)= m(i-1)* mI* m(yo + 1);
- vsij = min [cik + c(k + 1) j + mI* m(k + 1)* m(d + 1)] de lo contrario.
La tabla de programa dinámico toma como entrada el número de operaciones realizadas según las matrices elegidas. Considere el siguiente ejemplo:
I | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
metroI | 30 | 35 | 15 | 5 | 10 | 20 | 25 |
La tabla inicial es la siguiente:
vsij | 1 | 2 | 3 | 4 | 5 | 6 |
1 | 0 | – | – | – | – | – |
2 | – | 0 | – | – | – | – |
3 | – | – | 0 | – | – | – |
4 | – | – | – | 0 | – | – |
5 | – | – | – | – | 0 | – |
6 | – | – | – | – | – | 0 |
Entonces podemos calcular cij con dos matrices (sin principio de subestructura):
vsij | 1 | 2 | 3 | 4 | 5 | 6 |
1 | 0 | 15750 | – | – | – | – |
2 | – | 0 | 2625 | – | – | – |
3 | – | – | 0 | 750 | – | – |
4 | – | – | – | 0 | 1000 | – |
5 | – | – | – | – | 0 | 5000 |
6 | – | – | – | – | 0 |
El resto de la tabla se rellena diagonal a diagonal de acuerdo con la regla descrita anteriormente:
vsij | 1 | 2 | 3 | 4 | 5 | 6 |
1 | 0 | 15750 | 7875 | 9375 | 11875 | 15125 |
2 | – | 0 | 2625 | 4375 | 7125 | 10500 |
3 | – | – | 0 | 750 | 2500 | 5375 |
4 | – | – | – | 0 | 1000 | 3500 |
5 | – | – | – | – | 0 | 5000 |
6 | – | – | – | – | – | 0 |
El resultado se obtiene para i = 1 y j = 6, es decir, el cuadro de la parte superior derecha de la tabla. Por tanto, el coste mínimo es de 15125 operaciones. Surge entonces una nueva pregunta: ¿cómo se procedió a tener un número mínimo de cálculos?
Cuando calculamos el costo mínimo de cada caja, elegimos entre dos configuraciones. Por ejemplo para calcular c13, tomamos el mínimo entre c12* M3 y M1* vs23. Basta señalar la elección realizada para conocer el orden de cálculo del producto matricial.
Kij | 1 | 2 | 3 | 4 | 5 | 6 |
1 | – | – | 1 | 3 | 3 | 3 |
2 | – | – | – | 3 | 3 | 3 |
3 | – | – | – | – | 3 | 3 |
4 | – | – | – | – | – | 5 |
5 | – | – | – | – | – | – |
6 | – | – | – | – | – | – |
La tabla dice lo siguiente: para calcular MI* Mj, establecemos k = Kij dado por la tabla, entonces calculamos MI*… * Mk y M(k + 1)*… * Mj que luego multiplicamos entre ellos.
En nuestro ejemplo, para calcular vs16, calculamos c13* vs46; calcular vs13, calculamos M1* vs23; calcular vs46 calculamos c45* M6.
La mayoría de algoritmo basado en la programación dinámica retiene en la memoria la elección realizada para cada cálculo. A menudo, el resultado no es importante, el viaje para lograrlo sí lo es.
Ejemplo: cambio de moneda
Queremos cambiar el cambio en £ 67. Para ello queremos utilizar el número mínimo de piezas de tipo: 1, 5, 10, 25.
Aquí es fácil adivinar la solución óptima 67=2*25+10+5+2*1. Escogiendo siempre la moneda de mayor valor posible, obtenemos una solución (por algoritmo codicioso).
El problema se escribe de la siguiente manera: Sea D = {d1, .., Dk} un número finito de valor de moneda. Se supone que cada dI es un número entero y que el conjunto se ordena aumentando el valor. Cada valor de la moneda está disponible de forma ilimitada. El problema es realizar el cambio en un valor de n £ con un número mínimo de monedas, si dk = 1 entonces siempre hay una solución.
El método codicioso no siempre da una solución óptima. Por ejemplo, D = {25,10,1} yn = 30. El método óptimo dará la siguiente solución: 25 + 5 * 1, que es peor que 3 * 10.
Paso 1: Caracterizar la subestructura óptima. Definamos C [j] como la solución óptima para la suma j £. Por tanto, podemos eliminar una parte y encontrar una solución óptima para C [j] = 1 + C [j-di].
Paso 2: Valor de la solución óptima. Podemos definir de forma recursiva la solución óptima a partir de la subestructura.
Paso 3: algoritmo.
Cambio de moneda (n, d, k) C [0] = 0; Para j de 1 an C [j] = inf; Para i de 1 a k Si j> = di y C [j-di] <C[j] then
C[j]=1+C[j-di]
Denom[j]=di
Return C
Usamos una matriz adicional llamada Denom, tal que Denom [j] representa la parte a usar para obtener una solución óptima para una suma j £. Si subimos Denom por el valor de la moneda hasta llegar a j = 1, entonces conocemos la selección de moneda que se ha realizado. Tomemos el ejemplo con las siguientes piezas: 1, 5, 10, 25:
| j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| C [j] | 0 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 5 | 1 | 2 | 3 | 4 | 5 | 2 |
| Denom [j] | 0 | 1 | 1 | 1 | 1 | 5 | 1 | 1 | 1 | 1 | 10 | 1 | 1 | 1 | 1 | 5 |
A partir de una suma n £, podemos encontrar todas las combinaciones de monedas que permitan realizar el cambio. Considere los mismos valores de moneda: 1, 5, 10, 25. Por ejemplo, para N = 4, D = {1,2,3} hay cuatro soluciones: {1,1,1,1}, {1, 1.2 }, {2.2} y {1.3}.
Etapa 1: La subestructura óptima, C (N, m) se puede dividir en dos conjuntos:
- Soluciones que no contienen partesmetro
- soluciones que contienen al menos una pieza demetro
Si una solución no contiene parte demetro, entonces podemos resolver el subproblema de N con D = {d1, .., Dm-1}, es decir las soluciones de C (N, m-1).
Si una solución contiene dmetro, luego vamos a quitar un trozo demetro, por lo tanto, debemos resolver el subproblema N- dmetro , con D = {d1, .., Dmetro}. Resolvamos el siguiente problema C (N- dmetro, m).
2do paso: La regla es: C (Nm) = + C (N- dmetro, m) con las condiciones básicas:
- C (N, m) = 1, N = 0
- C (N, m) = 0, N <0
- C (N, m) = 0, N> = 1, m <= 0
Paso 3: Las soluciones de los algoritmos se informan en una tabla de la forma
| n / A | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 5 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 3 | 4 |
| 10 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 4 | 4 | 6 |
| 25 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 4 | 4 | 4 | 4 | 4 | 6 |
ES 
FR 
EN