Programación Dinámica: Subset Sums, Knapsacks, Camino Mínimo Flashcards
Explique el problema de Subset Sums
Sea un conjunto de n elementos E = {e1, ..., en}, donde cada elemento ei cuenta con un peso asociado wi.
Queremos seleccionar un subset de elementos de E con el mayor peso posible que no supere un valor W de peso máximo.
Es el problema de la mochila, básicamente. Una versión sencilla del mismo, sin ganancias, sólo peso.
Subset Sums: Explique la solución por fuerza bruta y su complejidad temporal.
La solución por fuerza bruta consiste en combinar todos los elementos entre sí. Esto es 2^n.
Subset Sums: Explique la solución dinámica.
Si ei pertenece a la solución, se consume wi del peso disponible.
Entonces:
- Si
eiestá en la solución,maxPeso(ei, W) = wi + maxPeso(e(i-1), W-wi) - Si
eino está en la solución,maxPeso(ei, W) = maxPeso(e(i-1), W)
Por lo que la solución óptima en ei es el máximo entre el peso que incluye a ei y el peso que no incluye a ei.
Subset Sums: Explique los subproblemas y la recurrencia
Vamos a llamar maxPeso(i,p) al problema de determinar el peso máximo que no supere a p, utilizando como posibles elementos del óptimo a los primeros i del conjunto.
La recurrencia se da de la forma:
maxPeso(i,p) = 0, si (i=0) o (p=0)
maxPeso(i,p) = max { (wi+maxPeso(i-1,p-wi)) o (maxPeso(i-1,p) }, si (i>0) y (p>0).
Subset Sums: Explique el pseudocódigo de la solución iterativa, junto con su complejidad temporal y espacial
Con i desde 0 a n:
OPT[i][0] = 0
Con p desde 0 a W:
OPT[0][p] = 0
Con i desde 1 a n:
Con p desde 1 a w:
opt_usando_elem = w[i] + OPT[ i-1, p - w[i]]
opt_sin_elem = OPT[i-1,p]
Si opt_usando_elem > opt_sin_elem:
OPT[i][p] = opt_usando_elem
De lo contrario:
OPT[i][p] = opt_sin_elem
Retornar OPT[n][W]
- Para todos los elementos, si el peso W es 0, el óptimo es 0.
- Para todos los pesos, si el elemento es el 0, el óptimo también es 0.
- Recorro todos los elementos, y todos los pesos para cada elemento.
a. Me fijo si el óptimo de usar el elemento (peso_elem + (OPT del anterior sin el peso del elemento) ) es mayor al óptimo sin el elemento (OPT acumulado del anterior).
b. Me quedo con el que sea mayor, y lo guardo para el elemento i y el peso p actual.
- Al final, devuelvo el OPT en el elemento n y peso W.
Complejidad
La complejidad temporal es O(n * W)
La complejidad espacial es O(n * W)
Resolver Subset Sum:
i, w
1, 1
2, 2
3, 4
W = 5
OPT = 6
elecciones: 3, 2
Knapsacks: Explique el problema
Sea un conjunto de n elementos E = {e1, ..., en} donde cada elemento ei cuenta con un peso asociado y una ganancia vi, queremos seleccionar un subset de elementos de E con la mayor ganancia posible que no supere un valor W de peso máximo.
Llamaremos maxGanancia(i,p) al problema de determinar la ganancia máxima que no supere p, utilizando los primeros i elementos del conjunto.
Es básicamente el problema de la mochila con ganancias.
Knapsacks: Explique la solución por recurrencia
Podemos plantear que:
- Si
eipertenece a la solución, entoncesmaxGanancia(ei, w) = vi + maxGanancia(e(i-1),W - wi). - Si
eino pertenece a la solución, entoncesmaxGanancia(ei, w) = maxGanancia(e(i-1),W).
Es decir, si el elemento no pertenece a la solución, la ganancia máxima es la ganancia máxima del anterior.
Si el elemento pertenece a la solución la ganancia máxima es la ganancia del actual + la ganancia del anterior sin incluir el peso del elemento.
Knapsacks: Explique el pseudocódigo de la solución Iterativa, junto con su complejidad temporal y espacial.
Con i desde 0 a n:
OPT[i][0] = 0
Con p desde 0 a W:
OPT[0][p] = 0
Con i desde 1 a n:
Con p desde 1 a W:
opt_con_elem = v[i] + OPT[ i-1, p - w[i]]
opt_sin_elem = OPT[i-1, p]
Si opt_con_elem > opt_sin_elem:
OPT[i][p] = opt_con_elem
De lo contrario:
OPT[i][p] = opt_sin_elem
Retornar OPT[n][W]
Es el mismo pseudocódigo de Subset Sum, pero en vez de buscar el peso máximo, buscamos la ganancia máxima sin pasarnos del peso.
La complejidad temporal es de O(n * W)
La complejidad espacial es de O(n * W)
Resolver:
Knapsack
i, w, v
1, 1, 3
2, 2, 4
3, 4, 2
W = 5
Ganancia total
7
Elementos usados de la lista:
(1,1,0)
Ejercicio de Final
Resolver: Para un nuevo satélite a poner en órbita una empresa privada puede optar por incluir diversos sensores a bordo (por ejemplo: variación de temperatura, humedad en tierra, caudal de ríos, etc).
Cada uno de ellos tiene un peso “pi” y una ganancia “gi” calculado por su uso durante la vida útil del satélite. Si bien les gustaría incluir todos, el satélite tiene una carga máxima P que puede llevar.
Nos piden que generemos un algoritmo (utilizando programación dinámica) para resolver el problema.
Incluya definición del problema, relación de recurrencia y pseudocódigo. Indique si su
solución es polinomial.
Knapsack.
Sea un conjunto de n elementos E = {e1, ..., en} donde cada elemento ei cuenta con un peso asociado y una ganancia vi, queremos seleccionar un subset de elementos de E con la mayor ganancia posible que no supere un valor W de peso máximo.
Llamaremos maxGanancia(i,p) al problema de determinar la ganancia máxima que no supere p, utilizando los primeros i elementos del conjunto.
Es básicamente el problema de la mochila con ganancias.
Para la relación de recurrencia, podemos plantear que:
- Si ei no pertenece a la solución, entonces maxGanancia(ei, w) = maxGanancia(e(i-1),W).
- Si ei pertenece a la solución, entonces maxGanancia(ei, w) = vi + maxGanancia(e(i-1),W - wi).
Es decir, si el elemento no pertenece a la solución, la ganancia máxima es la ganancia máxima del anterior.
Si el elemento pertenece a la solución la ganancia máxima es la ganancia del actual + la ganancia del anterior sin incluir el peso del elemento.
Con i desde 0 a n:
OPT[i][0] = 0
Con p desde 0 a W:
OPT[0][p] = 0
Con i desde 1 a n:
Con p desde 1 a W:
opt_con_elem = v[i] + OPT[ i-1, p - w[i]]
opt_sin_elem = OPT[i-1, p]
Si opt_con_elem > opt_sin_elem:
OPT[i][p] = opt_con_elem
De lo contrario:
OPT[i][p] = opt_sin_elem
Retornar OPT[n][W]
Es el mismo pseudocódigo de Subset Sum, pero en vez de buscar el peso máximo, buscamos la ganancia máxima sin pasarnos del peso.
La complejidad temporal es de O(n * W)
La complejidad espacial es de O(n * W)
La complejidad es pseudopolinomial.
Camino Mínimo: Explique qué son los ciclos negativos
Si existe un costo negativo, utilizar una arista puede disminuir el costo del camino total.
Sean los nodos A = a1, ..., an tal que existen las aristas ai -> a(i+1), conformando un ciclo c donde la suma de todas las aristas es menor a cero.
A este ciclo lo llamaremos ciclo negativo C.
La existencia de un ciclo negativo dentro de un camino s-t genera un camino mínimo de -infinito.
Camino Mínimo: Explique la solución por fuerza bruta
Si queremos solucionar por fuerza bruta, podemos calcular todos los costos de los caminos posibles de s a t con longitud 1.
Luego con longitud 2, 3 y así hasta llegar a n-1.
El camino mínimo tendrá una longitud de n-1 como máximo.
Camino Mínimo: Explique el algoritmo de Bellman Ford
Es un algoritmo para camino mínimo para casos de grafos ponderados sin ciclos negativos, utilizando programación dinámica.
Para llegar desde s a un nodo ni, puede haber utilizado diferentes caminos, dependiendo de sus predecesores. Y a los predecesores les pasa lo mismo, se puede llegar desde predecesores diferentes.
Para llegar de s a ni en j pasos, tengo que haber pasado por sus predecesores en j-1 pasos.
Al camino mínimo hasta el nodo ni con longitud máxima j lo vamos a llamar minPath(ni,j).
Es el camino mínimo hasta el nodo ni con una longitud que puede ir desde 0 a j.
Este camino es el mínimo entre todos los caminos mínimos que llegan a sus predecesores en un máximo de j-1.
Definimos entonces:
minPath(ni,j) = min {
minPath(ni, j-1),
min {
minPath(nx, j-1) + w(nx,j-1)
}
}
siendo nx predecesores de ni.
Camino Mínimo: Explique los subproblemas de la recurrencia
Llegar a s tiene costo 0minPath(s,j) = 0
Llegar a ni con 0 pasos tiene costo +inf:minPath(ni,0) = +inf ; si ni != s
Llegar a ni con j pasos es el mínimo entre: el costo mínimo de llegar a ni con j-1 pasos, y el mínimo de todos los costos de llegar a los predecesores con j-1 pasos + el costo de pasar del predecesor a ni (el eje):
minPath(ni,j) = min {
minPath(ni, j-1),
min {
minPath(nx, j-1) + w(nx,j-1)
}
}
siendo nx predecesores de ni.
