¿Qué es un algoritmo voraz y cómo se aplica en la…

El algoritmo voraz es un enfoque heurístico que en cada paso toma la decisión localmente óptima con la esperanza de que esto conduzca a una solución globalmente óptima.

Aplicaciones:

Problema de selección de actividades:

Problema: Elegir la mayor cantidad de intervalos no superpuestos en el tiempo de un conjunto dado.
Solución voraz: Ordenar los intervalos por tiempo de finalización ascendente. En cada paso, seleccionar el intervalo con el menor tiempo de finalización que no se superponga con los ya seleccionados.

# Ejemplo de selección de actividades
# activities = [(start_time, end_time)]

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
activities.sort(key=lambda x: x[1]) # Ordenar por tiempo de finalización

selected_activities = []
last_finish_time = -1

for activity in activities:
    if activity[0] >= last_finish_time:
        selected_activities.append(activity)
        last_finish_time = activity[1]

print(selected_activities) # [ (1, 4), (5, 7), (8, 11), (12, 16) ]

Problema de cambio de monedas (Coin Change Problem) para conjuntos canónicos de monedas:
- Problema: Dar la cantidad dada con el mínimo número de monedas.
- Solución voraz: Usar la mayor cantidad posible de las denominaciones de monedas más grandes hasta que se entregue la suma. Solo funciona para ciertos conjuntos de monedas (por ejemplo, 1, 5, 10, 25).
```
# Ejemplo de cambio de monedas (para monedas canónicas)
coins = [25, 10, 5, 1]
amount = 67
result = {}

for coin in coins:
    while amount >= coin:
        result[coin] = result.get(coin, 0) + 1
        amount -= coin

print(result) # {25: 2, 10: 1, 5: 1, 1: 2}
```
Algoritmo de Kruskal para encontrar el árbol de expansión mínima:
- Problema: Encontrar un subconjunto de aristas de un grafo no dirigido ponderado conectado que conecte todos los vértices con el peso total mínimo.
- Solución voraz: Ordenar todas las aristas por peso en orden ascendente. Añadir aristas en orden, si no forman un ciclo con las ya seleccionadas, hasta que se hayan añadido n-1 aristas (donde n es el número de vértices).

Los algoritmos voraces son fáciles de implementar, pero no siempre encuentran la solución globalmente óptima para problemas arbitrarios. Para algunos problemas (por ejemplo, cambio de monedas con conjuntos arbitrarios, problema de la mochila en general), el enfoque voraz no es óptimo. Para garantizar la optimalidad o una mejor aproximación, pueden ser necesarios métodos como programación dinámica u otros. Antes de aplicar un algoritmo voraz, es importante asegurarse de que sea adecuado para el problema en cuestión.

¿Qué es un algoritmo voraz y cómo se aplica en la resolución de problemas?