Greedy: Mochila Fraccionaria, Cambio Mínimo & Seam Carving Flashcards
Explique el problema de la Mochila Fraccionaria
Se tiene:
- Un contenedor (mochila) de capacidad
W - Un conjunto de
nelementos fraccionables (se pueden subdividir) de valorviy de pesowi.
Queremos seleccionar un subconjunto de elementos o fracciones de ellos de modo de maximizar el valor almacenado y sin superar la cantidad de la mochila.
Mochila Fraccionaria: Explique la solución Greedy
Se priorizan los elementos más valiosos por unidad de peso.
Se repite el proceso mientras quede espacio en el contenedor y elementos disponibles.
Mochila Fraccionaria: Explique el pseudocódigo
- Se tiene un contenedor con capacidad
W - Se tiene
nelementos fraccionables, es decir, que pueden usarse sólo partes de ellos. Los elementos tienen, cada uno, un valor y un peso. - Queremos seleccionar un conjunto de elementos o fracciones de ellos de modo de maximizar el valor almacenado y sin superar la capacidad de la mochila.
De cada elemento se tiene una cantidad.
Mientras haya elementos disponibles:
Elijo al elemento con valor valor por unidad, y uso todos los que pueda (o en su caso, una fracción del elemento).
Sumo al valor total el valor agregado por el elemento elegido, y resto al peso disponible el paso aportado por el mismo elemento en total.
Elimino al elemento de los posibles.
Vuelvo a elegir un nuevo elemento.
Cuando no hay más elementos disponibles, devuelvo el valor total.
Mochila Fraccionaria: ¿El algoritmo Greedy, es siempre óptimo?
Sí, el algoritmo Greedy para la Mochila Fraccionaria es siempre óptimo.
Explique el problema de Cambio Mínimo
Se cuenta con:
- Un conjunto de monedas de diferente denominación, sin restricción de cantidad $ = {c1, c2, ..., cn}
- Un importe X de cambio a dar
Se quiere entregar la menor cantidad posible de monedas como cambio.
Cambio Mínimo: Explique la solución Greedy
La solución Greedy para Cambio Mínimo implica tomar siempre la moneda de mayor denominación posible que sea menor o igual al cambio a dar.
Se dan luego tantas monedas de esa denominación como sea posible. Con el resto, se repite el proceso hasta dar todo el cambio.
Cambio Mínimo: Explique el pseudocódigo
Mientras siga habiendo cambio para devolver:
Elegir la moneda de mayor denominación en el conjunto, tal que sea menor o igual al cambio a devolver
Devolver de esa moneda la mayor cantidad posible
Restar del cambio el valor de la moneda * la cantidad devuelta
Continuar la iteración
Una vez que ya no quedan monedas disponibles: Retornar la cantidad de monedas utilizadas en totalCambio Mínimo: ¿Qué complejidad tiene la solución?
La complejidad es O(n), ya que se recorren en el peor de los casos todas las monedas posibles.
Cambio Mínimo: ¿Es Greedy siempre óptimo? Explique.
No.
Greedy sólo funciona en los casos donde la base $ es canónica (o estándar, ordenado o greedy).
Se puede demostrar si una base es canónica o no con un contraejemplo. Basta con buscar un valor x entre:
c3 + 1 < x < cn + c(n-1)
tal que no se cumpla que óptimo = greedy
Seam Carving: Explique el problema
Seam Carving es un algoritmo para la manipulación de imágenes.
Analiza la imagen recortando los píxeles de menor importancia.
- Seam significa “veta” y carving “tallado”.
- La veta puede ser horizontal o vertical.
- Al retirarla, tiene el menor impacto sobre la visualización.
- Retira tantas vetas como sea necesario para llegar al tamaño requerido.
Seam Carving: ¿Cómo determina qué píxeles son poco importantes?
Existen diferentes métodos. Por ejemplo:
- Entropía
- Diferencia cromática
- Movimiento de la mirada
Seam Carving: Explique la diferencia cromática
La diferencia cromática la da relevancia a los píxeles que rodean al pixel actual.
- Si es un pixel rodeado de píxeles similares, tiene poca importancia
- Si es un pixel rodeado de pixels diferentes, tiene mucha importancia.
Inicialmente, se debe calcular la importancia de cada pixel.
Seam Carving: Explique la solución por Camino Mínimo (¿cómo se interpreta la imagen?)
Trataremos la imagen como una grilla de píxeles intercomunicados. Lo representaremos como un grafo, donde todos los píxeles son nodos y los ejes son posibles cambios de la veta.
Lo que vamos a hacer es calcular el camino mínimo entre s y t.
Seam Carving: Camino Mínimo: Explique el algoritmo Dijsktra
Dijsktra es un algoritmo Greedy, y funciona para un grafo G dirigido y ponderado (con costos positivos) de N nodos aislados y M ejes.
Dados dos nodos s y t, busca el camino mínimo que los une.
Es un algoritmo iterativo que divide los nodos en tres conjuntos:
- Alcanzados: inicialmente, sólo el
s - Externos: inicialmente, todos menos
s - Frontera: pertenecientes a externos, pero conectados a alguno de los nodos alcanzados.
Seam Carving: Camino Mínimo: Explique el pseudocódigo de Dijsktra
Sean los alcanzados un conjunto donde inicialmente sólo se encuentra `s` con costo `0` y predecesor `nulo`.
Sea la frontera un conjunto vacío.
Por cada nodo vecino a `s`, agregar a la frontera, con costo `c_s` y predecesor `s`.
Mientras la frontera no esté vacía:
Obtener al nodo `x`, que tiene el menor costo.
Quitar a `x` de la frontera
Agregar a `x` a los alcanzados
Por cada `y` vecino de `x`:
El costo de `y` será el costo de `y` más el acumulado de `x`
Si `y` está en la frontera y el costo accediendo desde `x` es menor a su costo actual, actualizar `y` tal que su costo y predecesor sea `c_x` y `x`.
Si `y` no está en la frontera, agregar a `x` como predecesor. Agregar a `y` en la frontera con costo `c_y + c_x`.
Una vez que se llegó a `t`, puedo recorrer los alcanzados de forma inversa (con los predecesores) y obtener el camino mínimo.
