Algoritmos Greedy (Voraz)
Es una estrategia de resolución de problemas que se basa en hacer elecciones localmente
óptimas en cada etapa, con la esperanza de obtener una solución óptima global.
Ejemplo: ¿Cuál es el número más grande que consiste de los dígitos 9, 8, 9, 6, 1?
Ejemplo 2: n pacientes van a un consultorio médico a las 9am. No existe un orden de
atención, sin embargo, se sabe que para el paciente i el tiempo necesario para su
tratamiento es ti. Ordena a los pacientes en una cola de tal forma que el tiempo de espera
total sea minimizado.
Estrategia voraz:
- Hacer una elección voraz.
- Reducir a un problema más pequeño.
- Iterar.
Sub-problema: Es un problema similar de menor tamaño.
Para el ejemplo 1: sol(1,9,8,9,6)=9+sol(1,8,9,6)
Para el ejemplo 2: sol(t1,t2,…,ti-1,ti=min,ti+1,…,tn-1,tn)=(n-1)*tmin+ sol(t1,t2,…,ti-1,ti+1,tn-1,…,tn)
Elección segura: Una elección voraz es llamada segura, si existe una solución óptima
consistente con la primera elección. No todas las primeras elecciones son seguras, las
elecciones voraces son usualmente inseguras. Deben ser probadas.
Para el ejemplo 2:
- Lemma: Tratar al paciente tj = min es una elección segura.
- Proof: ¿Es posible un arreglo óptimo que tenga 2 pacientes consecutivos en orden con
tiempo de espera ti y ti+1 tales que ti+1>ti? ¡Imposible!, Si intercambiamos esos 2
pacientes consecutivos, la espera de los pacientes anteriores y los siguientes no
cambia, pero el tiempo de espera de ti incrementa en ti+1 y el tiempo de espera de ti+1
decrementa en ti. El tiempo total se incrementa en ti+1-ti, por lo tanto, decrece. Probamos
que en un arreglo óptimo de pacientes, el primero de 2 pacientes consecutivos tiene el
menor tiempo de tratamiento.
Reducción a un sub-problema
- Hacer una primera elección.
- Después, resolver un problema del mismo tipo.
- El nuevo problema debe ser más pequeño.
1
- A este nuevo problema le llamamos sub-problema.
Estrategia general:
Problema -> Elección voraz -> Elección Segura -> Sub-problema
- Hacer una elección voraz.
- Probar que de la elección voraz es una elección segura.
- Reducir a un sub-problema.
Ejemplo 3 (fractional knapsack - mochila fraccionaria):
Input: Pesos w1, …, wn y valor v1,…,vn de n artículos, capacidad W.
Salida: El valor total máximo de fracciones de artículos que caben en una mochila de
capacidad W.
w(v): 5($30), 4($28), 3($24) W=9, casos: 5+4($58), 5+3+1($61), 3+4+2($64)
Lemma: Existe una solución óptima que utiliza la mayor cantidad posible de un artículo con
el máximo valor por unidad de peso. Proof: 9 = 5($30$)+4($28) = 3($18)+2($12)+4($28)
podemos reemplazar 3($18) por 3($24) incrementando el valor total.
Algoritmo:
- Mientras la mochila no esté llena.
- Elegir el ítem i con el máximo vi/wi.
- Si cabe en la mochila, poner todo.
- Sino, coger una fracción que llene la mochila.
- Retornar el valor total.
“Las elecciones voraces son usualmente inseguras”
Ejemplo 4: (Change problema) Encontrar la cantidad mínima de monedas necesarias para
hacer el cambio.
Input: money, coin1, …, coind
Output: El mínimo número de monedas que cambia el dinero.
Greedy!: Moneda con la denominación más grande.
US: 1,5,10,25,50, money=40, greedy=25+10+5
Tanzania: 1,5,10,20,25,50, money=40, greedy=25+10+5 no es óptimo, 20+20
2
Recursividad
Ejemplo 5 (usar luego): Dadas las denominaciones 6,5,1, ¿Cuál es el mínimo número de
monedas necesarias para hacer el cambio de 9 céntimos?
MinNumCoins(9)=min{Minnumcoins(9-6)+1, Minnumcoins(9-5)+1, Minnumcoins(9-1)+1}
int solve(int x)
if(x<0) return INF;
if (x==0) return 0;
int best=INF;
for(auto c:coins)
best=min(besst,solve(x-c)+1);
return best;
Árbol recursivo para 76.
¿No sería genial conocer todas las respuestas de dinero - monedai antes de calcular el
cambio para dinero?
En vez de consumir tiempo en llamadas a recursivechange(money-coini, coins) podemos
simplemente consultar los valores.
Programación Dinámica
“Programación” en “Programación Dinámica” no tiene nada que ver con Programación.
Bellman desarrolló la idea en 1950 trabajando en un proyecto de la Fuerza Aérea.
La idea clave en programación dinámica es memorización, lo que significa que cada valor
de la función es guardado en un arreglo después de ser calculado, luego, cuando el valor es
necesitado de nuevo, puede ser recuperado del arreglo sin necesidad de llamadas
recursivas.
DP = fuerza bruta cuidadosa
DP = subproblemas + reuso
Ejemplo 6 (Fibonacci):
Fib(1,2)=1
Fib(n)=Fib(n-1)+Fib(n-2)
Objetivo: Calcular Fn
Algoritmo Recursivo:
fib(b):
if n<=2: f=1
else: f=fib(n-1)+fib(n-2)
return f
3
Complejidad en Tiempo: O(2^(n/2))
Algoritmo DP con Memoization
memo = {}
fib(n):
if n is memo: return memo[n]
if n<=2: f=1
else f=fib(n-1)+fib(n-2)
memo[n]=f
return f
Árbol Recursivo -> reuso
fib(k) solo se repite la primera vez que es llamada
las llamadas memorizadas solo cuestan O(1)
# de llamadas no memorizadas es n: fib(1),fib(2),...,fib(n)
trabajo no recursivo por llamada = O(1)
tiempo total O(n)
DP: recursión + memorización
memoriza y reusa soluciones a subproblemas que ayudan a resolver el problema
tiempo = #subproblemas + tiempo/subproblema (no cuenta las recursiones)
tiempo = n + O(1)
Algoritmo DP Bottom-Up
fib={}
for k in range(1:n+1):
if k<=2: f=1
else: f=fib[n-1]+fib[n-2]
return fib[n]
Exactamente mismo cómputo
Orden topológico de la dependencia de subproblemas DAG
DAG: Fn-3 -> Fn-2 -> Fn-1 -> Fn
OJO: Las dependencias de un problema deben ser acyclicas (DAG)
Ahorra espacio
Un poco menos obvio que Recursivo Memorización
4
DP Guessing (Suposición)
No sé la respuesta -> supongo, intentar todas las suposiciones (y coger la memor)
DP: Recursión + Memorización + Suposición
5 pasos para programación dinámica:
1. Definir subproblemas - # subproblemas
2. Suponer - # elecciones para suposición
3. Relacionar el subproblema con la solución - # tiempo/subproblema
4. Recursión + Memorización o Construir la tabla DP Bottom-Up - Verificar que la
recurrencia de subproblemas sea acyclica (tenga un orden topológico)
5. Resolver el problema original
Ejemplo 7: (Mismo que ejemplo 5)
Resolver con DP.
bool ready[n]
int value[n]
int solve(int x)
if(x<0) return INF;
if(x==0) return 0;
if(ready[x]) return value[x];
int best=INF;
for(auto c:coins)
best=min(besst,solve(x-c)+1);
return best;
Ejemplo 8: La subsecuencia creciente más larga de un arreglo de n elementos es una
secuencia de longitud máxima de elementos del array que va de izquierda a derecha, y
cada elemento de esta secuencia es mayor que el elemento anterior.
Solución: Podemos encontrar eficientemente la subsecuencia creciente más larga en un
array usando programación dinámica. Sea length(k) la longitud de la subsecuencia creciente
más larga que termina en la posición k. Entonces, si calculamos todos los valores de
length(k)donde 0 ≤ k ≤ n - 1, encontraremos la longitud de la subsecuencia creciente más
larga. Los valores de la función para nuestro array de ejemplo son los siguientes:
length(0)=1, length(1)=1, length(2)=2, length(3)=1, length(4)=3, length(5)=2, length(6)=4,
length(7)=2
Para calcular un valor de length(k), debemos encontrar una posición i < k para la cual
array[i] < array[k] y length(i) sea lo más grande posible. Entonces sabemos que longitud(k) =
longitud(i) + 1, porque ésta es una forma óptima de añadir array[k] a una subsecuencia. Sin
5
embargo, si no existe tal posición i, entonces longitud(k) = 1, lo que significa que la
subsecuencia sólo contiene array[k].
Dado que todos los valores de la función se pueden calcular a partir de sus valores más
pequeños, podemos utilizar la programación dinámica para calcular los valores. En el
siguiente código, los valores de la función se almacenarán en un array length.
for (int k = 0; k < n; k++)
{
length[k] = 1;
for (int i = 0; i < k; i++)
{
if (array[i] < array[k])
{
length[k] = max(length[k],length[i]+1);
}
}
}
Ejemplo 9:
Nuestro siguiente problema es encontrar un camino desde la esquina superior izquierda
hasta la esquina inferior derecha de una cuadrícula n × n, con la restricción de que sólo
podemos movernos hacia abajo y hacia la derecha. Cada cuadrado contiene un número
entero, y el camino debe construirse de manera que la suma de los valores a lo largo del
camino sea lo más grande posible.
Como ejemplo, la Fig. uestra un camino óptimo en una cuadrícula de 5 × 5. La suma de los
valores en el camino es 67, y ésta es la mayor suma posible en un camino desde la esquina
superior izquierda hasta la esquina inferior derecha.
Supongamos que las filas y columnas de la cuadrícula están numeradas de 1 a n, y que el
valor[y][x] es igual al valor del cuadrado (y, x). Sea suma(y, x) la suma máxima en un camino
desde la esquina superior izquierda hasta el cuadrado (y, x). Entonces, sum(n, n) nos dice la
suma máxima desde la esquina superior izquierda hasta la esquina inferior derecha. Por
ejemplo, en la cuadrícula anterior, sum(5, 5) = 67. Ahora podemos utilizar la fórmula
sum(y, x) = max(sum(y, x - 1), sum(y - 1, x)) + value[y][x],
que se basa en la observación de que un camino que termina en el cuadrado (y, x) puede
venir del cuadrado (y, x - 1) o del cuadrado (y - 1, x). Por lo tanto, seleccionamos la
dirección que maximiza la suma. Suponemos que sum(y, x) = 0 si y = 0 ox = 0, por lo que la
fórmula recursiva también funciona para los cuadrados situados más a la izquierda y más
arriba.
6
int sum[N][N];
for (int y = 1; y <= n; y++) {
for (int x = 1; x <= n; x++) {
sum[y][x] = max(sum[y][x-1],sum[y-1][x])+value[y][x];
} }
Knapsack Problem (Problema de la mochila)
Objetivo: Maximizar el valor mientras limitamos el peso total.
7
Ejemplo 10: Knapsack con repeticiones
Dados los pesos w1, …, wn y los valores v1,...,vn de n items, y un peso total W.
Calcular el maximo valor de los items cuyo peso no exceda W. Cada item puede ser
utilizado cualquier número de veces.
Subproblema: Considera una solución óptima con el item wi. Si quitamos ese item,
obtenemos una solución óptima para W-wi.
Sea value(w) el maximo valor de una mochila de peso w.
value(w)= max i: wi<w {value(w-wi)+vi}
El algoritmo sería:
value(0)=0
for w form 1 to W:
value(w) = 0
for i from 1 to n:
if wi<w:
val=value(w-wi)+vi
if val>value(w):
value(w)=val
return value(w)
Ejemplo 11: Knapsack sin repeticiones
Dados los pesos w1, …, wn y los valores v1,...,vn de n items, y un peso total W.
Calcular el maximo valor de los items cuyo peso no exceda W. Cada item puede ser
utilizado como máximo 1 vez.
Si el n-ésimo elemento se toma en una solución óptima: entonces lo que queda es una
solución óptima para una mochila de peso total W - wn utilizando los elementos 1, 2, . . . , n
- 1. Si no se utiliza la posición n-ésima, toda la mochila debe llenarse de forma óptima con
las posiciones 1, 2, . . . , n - 1
Para 0 ≤ w ≤ W y 0 ≤ i ≤ n, valor(w, i) es el valor máximo alcanzable utilizando una mochila
de peso w y elementos 1, . . . , i.
El elemento i-ésimo se utiliza o no: valor(w, i) es igual a max{valor(w-wi, i-1)+vi, valor(w, i-1)}
8
9
