Estructuras de datos dinámicas/Algoritmos de optimización

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.

Pasos a seguir:

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 forma ordenada.
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).

Ejemplo: Multiplicación de cadena de matrices

Dada una cadena de matrices $[A_{1},A_{2},\ldots ,A_{n}]$ , la tarea es obtener el producto $A_{1}\times A_{2}\times \ldots \times A_{n}$ .

La cantidad de multiplicaciones necesarias para obtener el resultado de cada una de las multiplicaciones entre una matriz de $n\times m$ y otra de $m\times p$ está dada por:

$n\times m\times p$

Caracterizar la estructura de una solución óptima: Una solución óptima divide la cadena $[A_{1},A_{2},\ldots ,A_{n}]$ en dos subcadenas $[A_{1},A_{2},\ldots ,A_{k}];[A_{k+1},A_{k+2},\ldots ,A_{n}]$ . Su costo será el costo de obtener $A_{1}\times A_{2}\times \ldots \times A_{k}$ más el costo de obtener $A_{k+1}\times A_{k+2}\times \ldots \times A_{n}$ 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 $k$ para el cual la solución sea la solución global del problema, de manera que resolver el problema consistirá en encontrar ese $k$ .
Definir recursivamente el valor de una solución: La función $m(i,j)$ , que devuelve la mínima cantidad de operaciones para obtener el producto $A_{i}\times A_{2}\times \ldots \times A_{j}$ será:

 $m(i,j)=$ 
 si  $i==j$ 
   $0$ 
 sino
   $m(i,k)+m(k+1,j)+cantidadFilas(A_{i}).cantidadColumnas(A_{j}).cantidadColumnas(A_{k})$

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, menor =  $\infty$ , mejorK = 0; k<j;k++)
    {
      valorActual = m(i, k) + m(k+1, j) + cantidadFilas(i)*cantidadColumnas(j)*cantidadColumnas(k);
      if(menor > valorActual)
      {
        menor = valorActual;
        mejorK = k;
      }
    }
    resultado.setValor(menor);
    resultado.setK(mejorK);
  }
  return resultado;
}

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, menor =  $\infty$ , mejorK = 0; k<j;k++)
    {
      valorActual = m(i, k) + m(k+1, j) + cantidadFilas(i)*cantidadColumnas(j)*cantidadColumnas(k);
      if(menor > valorActual)
      {
        menor = valorActual;
        mejorK = k;
      }
    }
    resultado.setValor(menor);
    resultado.setK(mejorK);
  }
  calculados.set(i, j, resultado);
  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?

Si se presta atención a la función que definimos en el primer punto:

 $m(i,j)=$ 
 si  $i==j$ 
   $0$ 
 sino
   $m(i,k)+m(k+1,j)+cantidadFilas(A_{i}).cantidadColumnas(A_{j}).cantidadColumnas(A_{k})$

Se puede ver que se cuenta con el resultado de la función cuando la posición de la matriz de inicio de la cadena es igual a la de fin, que es 0. Para calcular la cantidad de operaciones que requerirá una cadena de dos matrices, se usarán los datos iniciales y las dimensiones de las matrices, que también son datos:

$m(i,k)+m(k+1,j)+cantidadFilas(A_{i}).cantidadColumnas(A_{j}).cantidadColumnas(A_{k})=0+0+cantidadFilas(A_{i}).cantidadColumnas(A_{j}).cantidadColumnas(A_{k})$

Para calcular la cantidad de operaciones que requerirá una cadena de tres matrices $A$ , $B$ y $C$ , $k$ puede estar en dos posiciones: $A\times (B\times C)$ ó $(A\times B)\times C$ . Para calcular cualquiera de las dos opciones, deberá utilizarse un valor referente a una cadena de multiplicación de una matriz, uno referente a una cadena de dos matrices, y las dimensiones de las matrices. Sucesivamente, para optimizar cada una de las cadenas de multiplicación, se deberán utilizar los valores óptimos de todas las subcadenas, y esto define un orden posible para los cálculos:

Si calculamos sucesivamente los valores óptimos para las cadenas de $d$ matrices, comenzando desde $d=1$ hasta llegar a $d=n$ , en cada uno de los pasos se deberá utilizar información previamente obtenida, es decir que ninguno de los cálculos deberá esperar por el resultado de otro.

//inicialización en 0 para i == j
for(i = 0; i < n; i++)
  calculados.set(i, i, new Resultado(i,0));

for(d = 1; d < n; d++)
//largo de la cadena de matrices
{
  for(i = 0, resultado = new Resultado(); i <= (n - d); i++)
  //inicio de cada una de las cadenas
  {
    for(k = i, j = (i + d), menor =  $\infty$ ; k < (i + d); k++)
    //todos los k posibles, desde el principio hasta el fin de la cadena
    {
      valorActual = calculados.get(i, k).getValor() + calculados.get(k + 1, j).getValor() + cantidadFilas(i)*cantidadColumnas(j)*cantidadColumnas(k);
      if (menor > valorActual)
      {
        menor = valorActual;
        resultado = new Resultado(k, valorActual);
      }
    }
    calculados.set(i, (i + d), resultado);
  }
}

Construir una solución óptima a partir de la información computada: en este punto podría parecer que sólo contamos con parte de la información que necesitamos para construir una respuesta completa: la cantidad mínima de operaciones y el $k$ para la última operación. Sin embargo, debe notarse que los $k$ para las subcadenas $[A_{1},A_{2},\ldots ,A_{k}]$ y $[A_{k+1},A_{k+2},\ldots ,A_{n}]$ se pueden obtener mediante:

calculados.get(i, k).getK()

y

calculados.get(k + 1, n).getK()

Y así sucesivamente se pueden encontrar los valores de $k$ que constituirán la solución completa, recorriendo el denominado 'camino hacia atrás'. Esto se puede hacer, porque en cada paso guardamos el valor de $k$ correspondiente.

Ejemplo: El problema del cambio mínimo

Dado un conjunto de valores de monedas, debe obtenerse la mínima cantidad de monedas que forme determinado monto.

Caracterizar la estructura de una solución óptima

Sea el monto $m$ de monedas, y suponer que uno de los tipos de monedas susceptibles de usar es la unidad, la solución óptima del problema debe ser alguna de las siguientes:

Juntar por un lado una moneda, y por el otro $m-1$ .
Juntar por un lado dos monedas, y por el otro $m-2$ .
...
Juntar por un lado ${\frac {m}{2}}$ monedas, y por el otro ${\frac {m}{2}}$ .

Entonces, habrá nuevamente un $k$ tal que juntar por un lado $k$ y por el otro $m-k$ sea la solución óptima del problema, y resolver el problema consistirá en encontrar sucesivamente ese $k$ .

Definir recursivamente el valor de una solución: La función $m(t)$ , que devuelve la mínima cantidad de monedas para obtener el monto $t$ será:

 $m(t)=$ 
 si  $t\in M$ 
   $1$ 
 sino
   $m(k)+m(t-k)$

Siendo $M$ el conjunto de monedas posibles.

Con esta definición se puede escribir un algoritmo recursivo que resuelve el problema.

private Resultado m(Integer t)
{
  Resultado resultado = new Resultado();
  if(monedas.contains(t))
  {
    resultado.setValor(1);
    resultado.setK(t);
  }
  else
  {
    for(k=1, menor =  $\infty$ , mejorK = 0; k < t; k++)
    {
      valorActual = m(k) + m(t-k);
      if(menor > valorActual)
      {
        menor = valorActual;
        mejorK = k;
      }
    }
    resultado.setValor(menor);
    resultado.setK(mejorK);
  }
  return resultado;
}

Obviaremos el paso trivial de utilizar una estructura auxiliar para guardar los datos ya obtenidos.

Computar el valor de una solución óptima de forma ordenada

Para calcular la cantidad de monedas que hacen falta para obtener el monto $t$ , deberá contarse con el valor óptimo para todas las combinaciones de valores que suman $t$ , que serán combinaciones de valores menores que $t$ :

Si calculamos sucesivamente los valores óptimos para los montos menores que $t$ , comenzando desde la unidad, en cada uno de los pasos se deberá utilizar información previamente obtenida.

//inicialización en 1 para los valores que tienen cambio exacto
for(Integer i: monedas)
  calculados.set(i.intValue(), new Resultado(i,1));

for(x = 1,resultado = new Resultado(); x < m; x++)
//monto a obtener
{
  for(k = 1, menor = x ; k < x; k++)
  //divisiones posibles de x
  {
    valorActual = calculados.get(k).getValor() + calculados.get(x-k).getValor();
    if (menor > valorActual)
    {
      menor = valorActual;
      resultado = new Resultado(k, valorActual);
    }
  }
  calculados.set(x, resultado);
}

Construir una solución óptima a partir de la información computada

Para construir la solución a partir de la información obtenida, se puede obtener el $k$ de l primer monto:

calculados.get(m).getK()

Y esto significará que la solución será dividir el monto en k y m - k. Luego tendremos que buscar el k óptimo para esos montos:

calculados.get(k).getK()

calculados.get(m - k).getK()

Y así sucesivamente, hasta obtener una a una las unidades necesarias, que irán incrementando la cuenta de cada uno de los tipos de moneda necesarios.