Algoritmo codicioso
El algoritmo codicioso (en inglés: greedy algorithm), también llamado algoritmo voraz, es una estrategia algorítmica que en cada paso toma la mejor u óptima (es decir, la más favorable) elección en el estado actual, con la esperanza de que el resultado final sea el mejor u óptimo a nivel global.
Algoritmo codiciosoComo suele decirse, solo se preocupa por el beneficio inmediato, sin considerar el óptimo global; la elección realizada es solo, en cierto sentido, una solución óptima local.
Imagina que tienes un montón de monedas de diferentes denominaciones (por ejemplo, 1 yuan, 5 jiao, 1 jiao) y necesitas formar 1,8 yuanes con la menor cantidad de monedas.
Una idea muy natural es:Cada vez, tomar primero la moneda de mayor denominación。
Primero tomas 1 yuan, quedan 0,8 yuanes; luego tomas 5 jiao, quedan 0,3 yuanes; por último tomas tres monedas de 1 jiao.
En todo el proceso, en cada paso tomamosla mejor elección que parece en el momento actual, este es el núcleo del algoritmo codicioso.
Algoritmo codiciosoEs como una persona de miras cortas pero con decisiones firmes:
- Elección en cada paso: tomar la elección que parece óptima en el estado actual
- No considerar el panorama global: no considerar el impacto de esta elección en el futuro
- Resultado esperado: esperar que las elecciones óptimas locales conduzcan a una solución óptima global
Casos de la vida real:
- Dar cambio: usar siempre primero la moneda de mayor denominación
- Escalar una montaña: avanzar siempre en la dirección más empinada
- Compras: comprar siempre el artículo con la mejor oferta actual
- Elección de ruta: elegir siempre el camino más corto en el momento actual
Características del algoritmo codicioso
- Propiedad de la elección codiciosa: La solución óptima de cada paso puede deducirse de las soluciones óptimas locales de los pasos anteriores. Las elecciones posteriores no afectan a las anteriores.
- Subestructura óptima: La solución óptima de un problema contiene las soluciones óptimas de sus subproblemas. Esta es una propiedad que también tiene la programación dinámica, pero el algoritmo codicioso elige "codiciosamente" la solución óptima del subproblema en cada paso.
| Característica | Descripción | Ventajas | Desventajas |
|---|---|---|---|
| Óptimo local | Elegir en cada paso la solución óptima actual | Simple e intuitivo | Puede no ser el óptimo global |
| Irreversible | No se puede cambiar la elección después de hacerla | Decisión rápida | Es fácil caer en un óptimo local |
| Alta eficiencia | Normalmente tiene baja complejidad temporal | Gran practicidad | Alcance de aplicación limitado |
| Implementación sencilla | Lógica clara y fácil de entender | Fácil de codificar | Requiere demostrar su corrección |
Diferencias con la programación dinámica
Este es un punto que suele confundir a los principiantes. Comparemos con una tabla:
| Propiedad | Algoritmo codicioso | Programación dinámica |
|---|---|---|
| Criterio de decisión | En cada paso toma la elección óptima actual,sin posibilidad de retroceder。 | Cada elección depende de las soluciones de los subproblemas, guarda los resultados intermedios y puede comparar múltiples opciones. |
| Garantía de solución óptima | No siempre se obtiene la solución óptima global; se requiere que el problema tenga la propiedad de elección codiciosa. | Normalmente se obtiene la solución óptima global. |
| Eficiencia | Alta, normalmente con baja complejidad temporal. | Relativamente baja, porque es necesario resolver subproblemas superpuestos. |
| Escenarios de aplicación | Problemas con propiedad de elección codiciosa y subestructura óptima, como la codificación de Huffman y el árbol de expansión mínima. | Problemas con subestructura óptima y subproblemas superpuestos, como el problema de la mochila y el camino más corto. |
En pocas palabras,la programación dinámica es "planificar antes de actuar" y sacrifica lo inmediato por el beneficio a largo plazo; mientras que el algoritmo codicioso es "vivir el momento" y solo persigue el beneficio inmediato.
Marco básico del algoritmo codicioso
El algoritmo codicioso no tiene una plantilla de código fija, pero su idea se puede resumir en los siguientes pasos:
- Establecer el modelo matemático: abstraer el problema real como un problema matemático.
- Definir la estrategia codiciosa: determinar el criterio para elegir la "solución óptima" en cada paso. Este es el núcleo y la dificultad del algoritmo.
- Demostrar la estrategia codiciosa: demostrar que la estrategia codiciosa definida puede conducir a la solución óptima global (opcional pero importante; para los problemas de algoritmos, normalmente es necesario comprender su corrección).
- Resolución iterativa: según la estrategia, comenzando desde el estado inicial, ir tomando elecciones codiciosas paso a paso hasta obtener la solución del problema.
Un marco general en pseudocódigo es el siguiente:
Ejemplo
# 1. Inicialización: puede incluir ordenamiento, creación del contenedor de resultados, etc.
solution = []
# 2. Recorrer todas las opciones; normalmente es necesario ordenarlas primero según alguna regla
for item in sorted(problem.items, key=Regla de la estrategia codiciosa):
# 3. Elección codiciosa: si la elección actual cumple la condición, se adopta
if is_feasible(solution, item):
solution.append(item)
# 4. Devolver la solución final construida
return solution
Problemas clásicos y ejemplos de código
Veamos la aplicación del algoritmo codicioso a través de varios problemas clásicos. Para cada problema: 1) analizaremos el problema y la estrategia codiciosa; 2) proporcionaremos el código completo; 3) haremos un análisis línea por línea.
Ejemplo 1: Problema de cambio de monedas (Coin Change)
Descripción del problema: supongamos que el sistema de monedas es [100, 50, 20, 10, 5, 1] (unidad: céntimos) y se necesita dar un cambio deamountcéntimos; hallar el número mínimo de monedas a utilizar.
Estrategia codiciosa：Elegir cada vez la moneda de mayor valor que no supere el monto restante. Para el sistema monetario RMB, esta estrategia es válida.
Implementación del código：
Ejemplo
"""
Uso del algoritmo codicioso para resolver el problema de cambio de monedas (para un sistema de monedas específico)
:param coins: list[int], lista de valores de monedas, debe estar ordenada de forma descendente
:param amount: int, monto total del cambio necesario
:return: list[int], lista de valores de monedas utilizadas
"""
coins.sort(reverse=True) # Asegurar que las monedas estén ordenadas de mayor a menor valor
result = [] # Lista para almacenar las monedas del cambio
remaining = amount # Monto restante por devolver
for coin in coins:
# Mientras el valor de la moneda actual sea menor o igual al monto restante, usarla tantas veces como sea posible
while remaining >= coin:
result.append(coin)
remaining -= coin # Restar el valor de la moneda actual del monto restante
# Comprobar si el cambio es exacto
if remaining == 0:
return result
else:
# Para el caso en que no se pueda dar el cambio exacto (aunque no ocurre con este sistema de monedas)
return None
# Datos de prueba
test_coins = [100, 50, 20, 10, 5, 1]
test_amount = 186 # 1 yuan, 8 jiao y 6 fen
change = coin_change_greedy(test_coins, test_amount)
print(f"Cambio de {test_amount} céntimos, monedas necesarias: {change}")
print(f"Cantidad de monedas: {len(change)}")
# Salida: cambio de 186 céntimos, monedas necesarias: [100, 50, 20, 10, 5, 1]
# Cantidad de monedas: 6
Análisis del código：
- Línea 8:
coins.sort(reverse=True)Es la preparación clave de la estrategia codiciosa; garantiza que siempre consideremos primero las monedas de mayor valor. - Líneas 12-15:
whileEl bucle garantiza que mientras aún se pueda usar la moneda de valor actual, se siga usando; esto implementa la elección codiciosa de "usar tantas como sea posible". - Líneas 18-22: se comprueba el resultado final para asegurar que el monto coincida exactamente.
Advertencia importante: el algoritmo codicioso para resolver el problema del cambiono siempre obtiene la solución óptima¡Por ejemplo, si el sistema de monedas es [25, 20, 10, 5, 1] y se necesita formar 40 céntimos, el método codicioso elegiría 25+10+5 (tres monedas), pero la solución óptima es 20+20 (dos monedas).La estrategia codiciosa solo es válida bajo ciertos sistemas monetarios (como el RMB).
Ejemplo 2: Problema de programación de intervalos (Interval Scheduling)
Descripción del problema}]"
Estrategia codiciosa：Cada vez, se elige la reunión con la hora de finalización más temprana. Así se deja más tiempo para las siguientes.
Implementación del código：
Ejemplo
"""
Resolver el problema del máximo conjunto de intervalos disjuntos (programación de intervalos)
:param intervals: list of [start, end], lista de intervalos
:return: list of [start, end], la lista de intervalos seleccionados
"""
# 1. Ordenar por hora de finalización en orden ascendente
intervals_sorted = sorted(intervals, key=lambda x: x[1])
selected = [] # Almacenar los intervalos seleccionados
last_end_time = -float('inf') # Inicializar la hora de finalización del último intervalo seleccionado
for interval in intervals_sorted:
start, end = interval
# 2. Selección codiciosa: si la hora de inicio del intervalo actual no es anterior a la hora de finalización del último intervalo seleccionado, selecciónalo
if start >= last_end_time:
selected.append(interval)
last_end_time = end # Actualizar la última hora de finalización
return selected
# Datos de prueba: cada sublista representa una reunión [hora de inicio, hora de finalización]
test_intervals = [
[1, 3], [2, 4], [3, 5], [4, 6], [5, 7],
[1, 2], [2, 3], [1, 4]
]
result = interval_scheduling(test_intervals)
print("Máximo número de reuniones que se pueden programar (ordenadas por hora de finalización):")
for meeting in result:
print(f" Reunión [{meeting)
print(f"Total: {len(result)} reuniones")
# Una posible salida (ya que el orden después de ordenar puede variar, pero la cantidad es óptima):
# Reunión [1, 2]
# Reunión [2, 3]
# Reunión [3, 5] o [4, 6], etc.
# Total: 4 reuniones
Análisis del código：
- Línea 10:
sorted(intervals, key=lambda x: x[1])Es el núcleo de la implementación de la estrategia codiciosa: ordenar por hora de finalización. - Líneas 16-19:
if start >= last_end_timeEs la verificación de viabilidad, que garantiza que la reunión actual no se superponga con las reuniones ya seleccionadas. - La complejidad temporal de este algoritmo es O(n log n), que proviene principalmente de la ordenación.
Ejemplo 3: Codificación de Huffman (Huffman Coding) - Concepto e implementación simplificada
La codificación de Huffman es un algoritmo codicioso utilizado para la compresión de datos sin pérdida. Su idea central es:Asignar códigos más cortos a los caracteres de alta frecuencia y códigos más largos a los de baja frecuencia。
Estrategia codiciosa: Fusionar repetidamente los dos nodos de menor frecuencia para construir un árbol binario.
Dado que la implementación completa es bastante extensa, aquí se muestra su proceso central de fusión codiciosa:
Ejemplo
class Node:
"""Clase de nodo del árbol de Huffman"""
def __init__(self, char, freq):
self.char = char # Carácter (solo en nodos hoja)
self.freq = freq # Frecuencia
self.left = None
self.right = None
# Para poder comparar en el montículo, definir el método de comparación
def __lt__(self, other):
return self.freq < other.freq
def build_huffman_tree(char_freq):
"""
Construir el árbol de Huffman
:param char_freq: dict, caracteres y sus frecuencias, p. ej. {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
:return: Node, el nodo raíz del árbol de Huffman
"""
# 1. Inicialización: crear un nodo hoja para cada carácter y colocarlos en un montículo mínimo (cola de prioridad)
heap = [Node(char, freq) for char, freq in char_freq.items()]
heapq.heapify(heap) # Convertir la lista en un montículo mínimo
# 2. Fusión codiciosa: mientras haya más de un nodo en el montículo
while len(heap) > 1:
# Extraer los dos nodos de menor frecuencia
left = heapq.heappop(heap)
right = heapq.heappop(heap)
# Crear un nuevo nodo interno cuya frecuencia sea la suma de las frecuencias de los nodos hijos
merged = Node(None, left.freq + right.freq)
merged.left = left
merged.right = right
# Volver a insertar el nuevo nodo en el montículo
heapq.heappush(heap, merged)
# El último nodo que queda en el montículo es el nodo raíz del árbol de Huffman
return heap[0] if heap else None
# Datos de prueba
test_freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
root = build_huffman_tree(test_freq)
print("¡Árbol de Huffman construido! Frecuencia del nodo raíz =", root.freq if root else 0)
# Salida: ¡Árbol de Huffman construido! Frecuencia del nodo raíz = 100
Visualización del algoritmo: La siguiente figura muestra los primeros pasos del proceso de fusión para construir el árbol de Huffman con los datos de prueba anteriores:
Explicación del diagrama: El algoritmo siempre selecciona los dos nodos de menor frecuencia entre todos los nodos disponibles (inicialmente nodos hoja, y posteriormente también nodos internos) y los fusiona para generar un nuevo nodo interno. Este proceso se repite hasta formar un árbol binario completo. Los nodos hoja de este árbol corresponden a los caracteres originales, y la ruta desde la raíz hasta la hoja (la rama izquierda es 0, la rama derecha es 1) es el código de Huffman de ese carácter.
Demostración de la corrección del algoritmo codicioso
¿Cómo saber si un problema se puede resolver con un algoritmo codicioso? Generalmente, hay que demostrar los siguientes dos puntos:
- Propiedad de la elección codiciosa: Se puede demostrar mediante inducción matemática o reducción al absurdo que la elección óptima del primer paso está contenida en alguna solución óptima global.
- Subestructura óptima: Demostrar que, después de tomar la primera elección codiciosa, el problema original se reduce a un subproblema de menor escaladel mismo tipo。
conProblema de programación de intervaloscomo ejemplo, la idea de la demostración:
- Elección codiciosa: Sea el intervalo con la hora de finalización más temprana de todos
i. Existe una solución óptima que incluye al intervaloi。- Demostración: Supongamos que una solución óptima no incluye
i. Sea el primer intervalo de dicha solución óptimaj. Comoies el que termina más temprano, se usaipara reemplazarj, no entrará en conflicto con otros intervalos y el tamaño de la solución no cambiará; por lo tanto, incluiritambién produce una solución óptima.
- Demostración: Supongamos que una solución óptima no incluye
- Subestructura óptima: Tras seleccionar el intervalo
i, el problema restante es: entre todos los intervalos queino se superponen con él, encontrar la solución óptima. Esto constituye un subproblema del problema original.
Ejercicios prácticos
Ahora, intenta resolver los siguientes problemas con el algoritmo codicioso para consolidar tu comprensión.
Ejercicio 1: Juego de saltos
Problema: Dado un arreglo de enteros no negativosnums, inicialmente te encuentras en el primer índice del arreglo. Cada elemento del arreglo representa la longitud máxima que puedes saltar desde esa posición. Determina si puedes llegar al último índice.Ejemplo：nums = [2,3,1,1,4], devuelveTrue(salta 1 paso del índice 0 al índice 1, y luego 3 pasos hasta el último índice).Sugerencia de estrategia codiciosa: No se trata de simular cuánto saltar en cada paso, sino de mantener unalcance máximo alcanzable。
Ejercicio 2: Repartir galletas
Problema: Hay un grupo de niños y un montón de galletas; cada niño tiene un valor de apetitog[i], y cada galleta tiene un tamaños[j]. Un niño solo se satisface cuando el tamaño de la galleta es >= su apetito. Calcula el número máximo de niños que se pueden satisfacer.Ejemplo：g = [1,2,3], s = [1,1], salida1。
Sugerencia de estrategia codiciosa: Para satisfacer a más niños,se debe usar la galleta más pequeña para satisfacer al niño con el apetito más pequeño(o pensarlo al revés).
Ejercicio 3: Mejor momento para comprar y vender acciones II
Problema: Dado un arregloprices, dondeprices[i]es el precio de una acción determinada en el díai. Puedes realizar un número ilimitado de transacciones (es decir, comprar y vender una acción), pero no puedes participar en múltiples transacciones al mismo tiempo (debes vender la acción anterior antes de volver a comprar). Calcula el beneficio máximo que puedes obtener.Ejemplo：prices = [7,1,5,3,6,4], salida7(comprar a 1 y vender a 5, beneficio 4; comprar a 3 y vender a 6, beneficio 3; beneficio total 7).Sugerencia de estrategia codiciosa: El beneficio se puede descomponer en las diferencias de precio diarias. Mientrasel precio de hoy sea más alto que el de ayer, toma esa diferencia como beneficio。