¿Qué es un algoritmo voraz y en qué casos se aplica…

El algoritmo voraz es un enfoque para resolver problemas de optimización que en cada paso elige la mejor solución local (la opción más ventajosa desde el punto de vista del momento actual) con la esperanza de que esta secuencia de soluciones locales óptimas conduzca a una solución globalmente óptima. No considera las posibles consecuencias de la elección actual en los pasos futuros.

Características:

Simplicidad: Generalmente más fácil de implementar que la programación dinámica u otros métodos de optimización.
Velocidad: A menudo tiene menor complejidad computacional.
Garantía de optimalidad: No siempre garantiza encontrar la solución globalmente óptima. La garantía solo existe para ciertos tipos de problemas.

Se aplica en problemas donde se ha demostrado que la elección localmente óptima en cada paso conduce a una solución globalmente óptima. Ejemplos:

Problema de selección de actividades: Elegir la mayor cantidad de actividades no superpuestas en el tiempo.
Problema de la mochila (con fraccionamiento de objetos): Cuando los objetos se pueden dividir. Si no, es un problema de programación dinámica.
Algoritmo de Prim y Kruskal: Para encontrar el árbol de expansión mínima en un grafo.
Algoritmo de Dijkstra: Para encontrar el camino más corto en un grafo con pesos no negativos.
Codificación de Huffman: Para construir un código prefijo óptimo.

Ejemplo de pseudocódigo para el algoritmo de selección de actividades:

Función SeleccionarActividades(actividades):
  Ordenar actividades por tiempo de finalización
  actividades_seleccionadas = lista vacía
  tiempo_finalización_última = 0

  Para cada actividad en actividades:
    Si actividad.inicio >= tiempo_finalización_última:
      Añadir actividad a actividades_seleccionadas
      tiempo_finalización_última = actividad.finalización

  Devolver actividades_seleccionadas

Es importante verificar si el algoritmo voraz es aplicable a un problema específico, ya que de lo contrario puede dar una solución subóptima.

# Ejemplo simple donde el algoritmo voraz no es óptimo
# Problema de cambio: dar la menor cantidad de monedas
# Monedas disponibles: [1, 5, 10, 25] USD
# Por ejemplo, para 30 centavos

# Algoritmo voraz:
#  Tomar la moneda más grande <= 30 (25) -> resto 5
#  Tomar la moneda más grande <= 5 (5) -> resto 0
#  Resultado: 2 monedas (25 + 5). Aquí es óptimo.

# Monedas disponibles: [1, 6, 10]
# Para 12 centavos

# Algoritmo voraz:
#  Tomar la moneda más grande <= 12 (10) -> resto 2
#  Tomar la moneda más grande <= 2 (1) -> resto 1
#  Tomar la moneda más grande <= 1 (1) -> resto 0
#  Resultado: 3 monedas (10 + 1 + 1).
#  La solución óptima sería 2 monedas (6 + 6).

# Este ejemplo muestra que el algoritmo voraz no siempre conduce a la solución globalmente óptima,
# si las propiedades del problema no son compatibles con su aplicación (por ejemplo,
# denominaciones de moneda estándar suelen permitir el uso de voraz,
# pero denominaciones arbitrarias no).

¿Qué es un algoritmo voraz y en qué casos se aplica?