Algoritmos Voraces
¿Qué hace que un algoritmo sea codicioso?
Un algoritmo codicioso crea una solución paso a paso, eligiendo siempre la opción que luce mejor en este momento, sin reconsiderar elecciones pasadas. Sin retroceder, sin mirar hacia adelante.
Funciona cuando se cumplen dos propiedades:
- Propiedad de elección codiciosa: una elección óptima localmente conduce a una solución óptima global.
- Subestructura óptima: el problema restante después de cada elección es una instancia más pequeña del mismo problema.
Selección de actividad: el ejemplo clásico
Dado un conjunto de actividades con horas de inicio y finalización, seleccione el número máximo de actividades que no se superpongan.
Estrategia codiciosa: ordenar por hora de finalización, elija siempre la actividad que finalice antes.
def max_activities(intervals):
intervals.sort(key=lambda x: x[1])
count, end = 0, 0
for s, e in intervals:
if s >= end:
count += 1
end = e
return count
¿Por qué funciona esto? Elegir la actividad que termine más temprano deja más espacio para actividades futuras. Ninguna otra opción puede hacerlo mejor.
Codificación Huffman - Concepto
Cree un código binario óptimo sin prefijos fusionando repetidamente los dos símbolos de menor frecuencia. Esto es codicioso: en cada paso, fusiona el par más barato. El resultado es un árbol donde los símbolos frecuentes obtienen códigos cortos.
Juego de salto
Dada una matriz donde nums[i] es la longitud máxima de salto desde el índice i, determine si puede alcanzar el último índice.
Enfoque codicioso: realiza un seguimiento del índice más lejano alcanzable hasta el momento. Escanee de izquierda a derecha; si alguna vez se queda atrás, devuelva falso.
Discusión
Iniciar sesión unirse a la discusión