Programación Dinámica: Problema de la Soga, Weighted Interval Scheduling, Cambio Mínimo, Seam Carving

Question 1

¿Qué es la programación dinámica?

Answer 1

• Es una metodología de resolución para problemas de optimización (minimización o maximización).
• Divide el problema en subproblemas con una jerarquía entre ellos de menor a mayor tamaño.
• Cada subproblema puede ser utilizado y reutilizado en diferentes subproblemas mayores.

Question 2

¿Qué propiedades debe tener un problema para poder resolverse de forma óptima con programación dinámica?

Answer 2

Para poder resolverse de forma óptima con programación dinámica, el problema debe contener las siguientes propiedades:

• Subestructura óptima: la solución óptima global contiene en su interior las soluciones óptimas de sus subproblemas.
• Subproblemas superpuestos: en la resolución de sus subproblemas, vuelven a aparecer subproblemas previamente calculados.

Question 3

¿Por qué se usa una relación de recurrencia con programación dinámica?

Answer 3

Se usa una relación de recurrencia porque cada problema se ramifica en un conjunto de subproblemas.

Question 4

¿Qué es la memorización? ¿Qué se reduce con ella?

Answer 4

La memorización es la técnica fundamental para la resolución en forma eficiente de los problemas, mediante programación dinámica: consiste en almacenar los resultados de los subproblemas previamente calculados; para evitar repetir su resolución.

Se reduce la cantidad de problemas a calcular, por lo que se reduce la complejidad temporal de la solución.

Question 5

Problema del Corte de la Soga: Explique

Answer 5

Se tiene una soga de longitud L y una tabla de precios por longitud de la soga.
Queremos saber qué cortes realizar para maximizar la ganancia.

Cada corte realizado de longitud li nos deja con una ganancia pi y un largo de soga L-li.

Question 6

Problema del corte de la soga: explique la solución por programación dinámica.

Answer 6

Lo que vamos a hacer es armar un árbol de decisión representando todas las posibilidades. El óptimo será el máximo elegido entre todas las posibles ramas de subproblemas y opciones:

• OPT(X) = MAX { pi + OPT(X-i) } si X >0.
• OPT(X) = 0 si X <= 0.

Como en el árbol de decision ciertos problemas se repiten, podemos calcular una sola vez el resultado, y luego reutilizarlo almacenando en una tabla los subproblemas resueltos.

Ahora sólo se deben calcular L subproblemas, y la ganancia óptima va a estar en la última fila de nuestra tabla de memorización.

Question 7

Problema de la Soga: Explique el pseudocódigo de la solución iterativa. ¿Cuál es la complejidad?

Answer 7

1. OPT es el vector de óptimos, OPT[0] = 0

2. Recorro con i desde 0 a L:
         a. OPT[i] = 0 (lo inicializo en cero)

         b. Con j desde 0 a i:
                  valor = precio[j] + OPT(i-j)
                  si valor > OPT[i]:
                           OPT[i] = valor

3. Retornar OPT[L]

1. Inicializamos un vector donde se guardan las ganancias con (0,0).
2. Recorremos todos los posibles cortes i del 0 a L. Para cada uno, inicializamos el óptimo en 0. Luego, recorremos todos los posibles subcortes de 0 a i, guardando el precio del corte + el óptimo del restante (i-j). Si el valor es mayor al óptimo, mejoramos el caso previo y cambiamos el valor.
3. Retornamos el valor óptimo de L.

La complejidad espacial es O(L), y la temporal es O(L^2).

Question 8

Problema de la Soga: ¿Cómo podemos actualizar el pseudocódigo anterior para permitir la reconstrucción de decisiones?

Answer 8

Para permitir la reconstrucción de decisiones, además de actualizar el óptimo cuando el valor es mayor, guardamos la elección de j que dió ese óptimo.
Lo hacemos en otro vector: eleccion[i] = j.

Al finalizar, además de retornar el OPT de L, recorremos de L a 0 el vector eleccion, restando cada uno de los valores que encontramos de eleccion[L] hasta eleccion[0] (no van a ser números secuenciales).

Question 9

Problema de la Soga: Resolver

L = 4

long, precio:
0 , 0
1 , 2
2 , 5
3 , 7
4 , 8

Answer 9

[2,2] con ganancia 10

Question 10

Weighted Interval Scheduling: explique el problema

Answer 10

Es un Interval Scheduling donde ahora cada pedido tiene un valor vi.

Queremos seleccionar el conjunto P con tareas compatibles entre sí y que la suma de sus valores sea la mayor posible (ya no buscamos la mayor cantidad de pedidos compatibles, sino la mayor ganancia).

Question 11

Weighted Interval Scheduling: explique la implementación

Answer 11

• El orden se mantiene: ordenamos las tareas en orden creciente de tiempo de finalización.
• Para cada tarea i, queremos saber cuál es la primer tarea anterior con la que es compatible el evento P(i).
  Sabemos que por cómo están ordenadas, todos los compatibles de un evento i van a tener un valor menor a i ( x < i, x tiene tiempo de finalización previo a i).

Question 12

Weighted Interval Scheduling: ¿Cómo se define la pertenencia de una tarea al óptimo? ¿Qué pasa si un pedido no pertenece al óptimo?

Answer 12

• Si un pedido i pertenece al óptimo, ningún pedido incompatible con i pertenece. El primero en aparecer después de i es P(i), el primer anterior compatible.
• Si el pedido no pertenece al óptimo, la tarea i-1 podría hacerlo.

Question 13

Weighted Interval Scheduling: Explique el uso del árbol de decisión

Answer 13

El arbol, para cada elemento, tiene dos ramas: una si el elemento pertenece al óptimo, la otra sino pertenece.

Si un pedido está en el óptimo, se abre la pregunta de si su anterior compatible está. Si no lo está, seguimos con el siguiente anterior compatible.

Vemos que hay problemas que se repiten.

Question 14

Weighted Interval Scheduling: Explique la solución iterativa

Answer 14

1. Si x =0, el óptimo es 0.
2. Si x > 0, el óptimo se calcula como:
   a. Obtenemos el valor de x
   b. Obtenemos el valor del óptimo para el inmediatamente compatible de x
   c. Los sumamos
   d. Obtenemos el óptimo del anterior en orden de finalización: OPT(x-1).
   e. Nos quedamos con el máximo de esos dos valores (la suma, o el óptimo del anterior en finalización) y lo guardamos como óptimo del evento actual.
3. El resultado va a estar en OPT(n).

OPT[0] = 0

Desde i=1 ... n:

	enOptimo = V[i] + OPT[P(i)]
	noEnOptimo = OPT[i-1]

	Si enOptimo >= noEnOptimo:
		OPT[i] = enOptimo
	Sino:
		OPT[i] = noEnOptimo

Retornar OPT[n]

Question 15

Weighted Interval Scheduling: Explique para el pseudocódigo sus complejidades temporales y espaciales.

Answer 15

Complejidad Temporal: O(n)
Complejidad Espacial: O(n)

Question 16

Weighted Interval Scheduling: ¿Qué agregaríamos al pseudocódigo si quisiéramos reconstruir las elecciones?

Answer 16

Podemos guardar True o False en un arreglo, dependiendo de si está o no en el óptimo.

Luego recorremos el arreglo y nos quedamos sólo con aquellas posiciones que tienen valor True y son compatibles con nuestro anterior:

i = n
Mientras i >0
        Si elegido[i]:
                Imprimir i
                i = P(i)
        sino
                i--

Question 17

Weighted Interval Scheduling: Resolver

evento          inicio          final          valor
A                    9:00           10:30          3
B                    10:15         11:45          1
C                    11:00          12:30         2
D                    12:00          13:30        3
E                    13:15          14:45         1

Answer 17

Solución: A, C, E; ganancia 6

Question 18

Cambio Mínimo: Explique el problema

Answer 18

Esta versión de cambio mínimo sirve incluso para bases no canónicas. Vamos a usar árboles de decisión para hacer uso de la memorización.

Question 19

Cambio Mínimo: Explique cómo obtener el subproblema

Answer 19

El subproblema va a ser calcular el óptimo del cambio X, usando el mínimo de los subproblemas X-Cj, para j = 1, 2, ..., n.

Question 20

Cambio Mínimo: Explique la solución con recurrencia. ¿Cuál sería la complejidad si lo resolviéramos con fuerza bruta?

Answer 20

Siendo x el cambio a dar, el OPT es 1 + min(OPT(x-C)) o 0, si x=0.
Con fuerza bruta, comparar todas los subproblemas sería O(x^n), con programación dinámica, mejora.

Question 21

Cambio Mínimo: Explique el pseudocódigo iterativo. Explique la complejidad.

Answer 21

OPT[0] = 0

Para todos los valores i de 0 a x:
       El mínimo se setea en el infinito.
       minimo = inf

       Con j desde 1 a n:
              resto = i - C[j]

              si resto < 0:
                     break

              si resto >= 0 y OPT[resto] < minimo:
                     minimo = OPT[resto]

       OPT[i] = 1 + minimo

Retornar OPT[X]

1. Inicializamos el óptimo con 0, 0
2. Recorremos todos los i de 1 a x, y para cada uno ponemos al mínimo en infinito.
   a. Recorremos todas las monedas distintas posibles, y las restamos al valor de i. Si son mayores, cambiamos de i.
   b. Si son menores o iguales, y el optimo del resto es menor al mínimo actual, actualizamos el mínimo.
   c. Cada vez que terminamos de recorrer todos los valores de j, le sumamos 1 al mínimo y lo guardamos en el óptimo de i.
3. Al final, retornamos OPT de X.

Complejidad:
Temporal O(n * x)
Espacial: O(x)

Question 22

Cambio Mínimo: Explique cómo reconstruir elecciones

Answer 22

Se puede agregar una reconstrucción, guardando la elegida[i] = j cada vez que se encuentra un óptimo menor al mínimo. Luego, hacemos lo mismo que con la soga: vamos restando al cambio los valores de C[elegida[cambio]] (va a ser el valor de una denominación del cambio) y obtenemos las elecciones óptimas.

Question 23

Cambio mínimo, resolver:

X = 6
$ = {1, 5, 10, 25, 50, 100}

Answer 23

OPT[6] = 2

Optimos: 5, 1

Question 24

Seam Carving: ¿Qué es la energía de un pixel? ¿Qué es la energía acumulada?

Answer 24

• Vamos a definir la energía de un pixel como la medida que refleja la importancia o relevancia de ese pixel en la imagen.
• Vamos a decir que la energía acumulada de un pixel está dada por la cantidad de pixeles que pueden acceder al mismo.
• En la primer columna, la energía acumulada depende de los mismos píxeles. En la segunda, la energía acumulada depende del mismo pixel + cómo se llegó a él.
• En la columna n entonces, la energía acumulada de cada pixel será la propia + toda la energía de cómo se llegó a él.

Question 25

Seam Carving: ¿Cómo se define el subproblema?

Answer 25

Calculamos para cada pixel j de la columna i la energía mínima para llegar a este.
Esto depende únicamente de la columna i-1.

El problema base es la columna 1, donde la energía es la del propio pixel j.

Question 26

Seam Carving: Explique la solución por recurrencia.

Answer 26

El óptimo es igual a la energía únicamente para el caso de la columna i=1.

Para los otros, el óptimo es la energía del pixel + el mínimo de los óptimos de todos los posibles píxeles previos (que suelen ser 2 o 3, depende).

Question 27

Seam Carving: Solución Iterativa. Explicar el pseudocódigo y la complejidad.

Answer 27

Siendo w,h el ancho y la altura de la imagen:

Para j de 1 a h:
        Inicializo el óptimo de la primer columna como la energía del pixel: OPT[1,j] = e(i,j)

Para i de 2 a w:
        Para j de 1 a h:
                OPT[i,j] = e(i,j) + min (posibles predecesores)

menor = infinito

Para j de 1 a h:
        si el OPT[w,j] < menor:
                menor = OPT[w,j]

Retornar menor

1. Inicializo a toda la primer columna con las energías.
2. Calculo para cada columna (>1) y fila, el óptimo del pixel como el valor de la energia + el minimo de los predecesores.
3. Una vez que terminé de recorrer todo, recorro únicamente la última columna. inicializo el menor en infinito, y lo voy actualizando a medida que encuentro uno más chico.

Complejidad Temporal: O(wh)
Complejidad Espacial: O(wh)

Question 28

Seam Carving: Explicar la Reconstrucción de la veta.

Answer 28

Almacenar por cada pixel desde cuál se llega con mínima energía. Luego, reconstruir para atrás el camino de energía.

eleccion[i,j] = predecesor (u,v)
u,v pueden ser: (i-1, j), (i-1, j-1), (i-1, j+1).

Empezamos a recorrer desde pixel de la última columna con el menor optimo, y vamos para atrás.