Diferencia entre revisiones de «Estructuras de datos dinámicas/Algoritmos de optimización»

Contenido eliminado Contenido añadido
Nueva página: == Programación dinámica == Es aplicable cuando los subproblemas (obtenidos a partir de la técnica “dividir y conquistar”) no son independientes, sino que comparten subsubprob...
 
Rgfernan (discusión | contribs.)
Sin resumen de edición
Línea 1:
== Programación dinámica ==
 
Es aplicable cuando los subproblemas (obtenidos a partir de la técnica “dividir y conquistar”) no son independientes, sino que comparten subsubproblemas, cuyas soluciones óptimas sean parte de la solución óptima global.
 
cuyas soluciones óptimas sean parte de la solución óptima global.
 
Pasos a seguir:
Línea 9 ⟶ 7:
#Caracterizar la estructura de una solución óptima.
#Definir recursivamente el valor de una solución.
#Computar el valor de una solución óptima de la forma down-upordenada.
#Construir una solución óptima a partir de la información computada (este paso puede ser omitido si sólo se requiere el valor y no la solución; de ser realizado, generalmente debe guardarse información adicional).
 
realizado, generalmente debe guardarse información adicional).
 
; Ejemplo: Multiplicación de cadena de matrices.
Línea 22 ⟶ 18:
<math>n \times m \times p</math>
 
; Caracterizar la estructura de una solución óptima: Una solución óptima divide la cadena <math>[A_1, A_2,\ldots, A_n]</math> en dos subcadenas <math>[A_1, A_2,\ldots, A_k];[A_{k+1}, A_{k+2},\ldots, A_n]</math>. Su costo será el costo de obtener <math>A_1\times A_2\times \ldots \times A_k</math> más el costo de obtener <math>A_{k+1} \times A_{k+2} \times \ldots \times A_n</math> más el de multiplicar los resultados entre sí. La solución óptima para la multiplicación de estas particiones es la solución óptima de cada una de las particiones. Habrá un <math>k</math> para el cual la solución sea la solución global del problema, de manera que resolver el problema consistirá en encontrar ese <math>k</math>.
; Definir recursivamente el valor de una solución: La función <math>m(i, j)</math>, que devuelve la mínima cantidad de operaciones para obtener el producto <math>A_i\times A_2\times \ldots \times A_j</math> será:
 
<math>m(i, j) = </math>
si <math>i == j</math>
<math>0</math>
sino
<math>m(i,k)+ m(k+1,j)+ cantidadFilas(A_i).cantidadColumnas(A_j).cantidadColumnas(A_k)</math>
 
Con esta definición se puede escribir un algoritmo recursivo que resuelve el problema.
 
private Resultado m(int i, int j)
{
Resultado resultado = new Resultado();
if(i == j)
{
resultado.setValor(0);
resultado.setK(i);
}
else
{
for(k=i, mayor = 0, mejorK = 0; k<j;k++)
{
valorActual = mayor,m(i, k)+m(k+1, j) + cantidadFilas(i)*cantidadColumnas(j)*cantidadColumnas(k);
if(mayor<valorActual)
{
mayor = valorActual;
mejorK = k;
}
}
resultado.setValor(mayor);
resultado.setK(mejorK);
}
return resultado;
}
Como se ve, este método solamente devuelve la cantidad mínima de operaciones y el k para la última multiplicación. Para devolver toda la secuencia de operaciones que deben realizarse, debe guardarse la información obtenida en cada paso.
 
Si se analiza la complejidad computacional de esta función, se verá que es igual de ineficiente que el método de fuerza bruta. La función será llamada muchas veces con los mismos valores, y deberá recalcularse cada una de esas veces. Una mejora del algoritmo podría valerse de una estructura auxiliar para guardar estos datos.
 
private Resultado m(int i, int j)
{
if(calculados.contains(i, j)) return calculados.get(i, j);
Resultado resultado = new Resultado();
if(i == j)
{
resultado.setValor(0);
resultado.setK(i);
}
else
{
for(k=i, mayor = 0, mejorK = 0; k<j;k++)
{
valorActual = mayor,m(i, k)+m(k+1, j) + cantidadFilas(i)*cantidadColumnas(j)*cantidadColumnas(k);
if(mayor<valorActual)
{
mayor = valorActual;
mejorK = k;
}
}
resultado.setValor(mayor);
resultado.setK(mejorK);
}
return resultado;
}
 
; Computar el valor de una solución óptima de forma ordenada: En este punto tenemos una solución del problema que utiliza una estrategia de dividir y conquistar, de manera que la resolución del problema global consiste en resolver cada uno de los subproblemas, y además, utilizamos toda la información disponible para no repetir cálculos, entonces, ¿qué le falta a esta solución para ser "dinámica"?
La respuesta se encuentra en el orden en el cual se obtiene la información. Una solución como esta necesita de esa pregunta en la primera línea del método, acerca de si se ha calculado previamente el dato, porque no toma en cuenta para nada el orden en el cual se obtiene cada dato. Si podemos determinar qué datos se necesitan para obtener cuales otros, podríamos procurar obtener antes los primeros, y así poder evitar quedar en espera de que los datos necesarios se obtengan.
 
¿Cómo podemos hacer esto para este problema en particular? Puede servir de guía tratar de responder algunas preguntas:
 
* ¿Con qué información se cuenta al comienzo?
* ¿Qué información se puede generar directamente a partir de la información inicial?
* ¿Puede hallarse una regla para generar sucesivamente la información necesaria, desde la información inicial hasta la solución del problema?