Algoritmos Ávidos

4.1 Definición de algoritmos ávidos.

Algoritmos Ávidos (Greedy Algorithms) — son una clase de algoritmos que construyen una solución tomando decisiones localmente óptimas en cada paso. Estas decisiones se toman basándose en el estado actual y no se reconsideran en el futuro.

Los algoritmos ávidos se utilizan a menudo para resolver problemas de optimización, donde el objetivo es maximizar o minimizar una cantidad específica.

Principios básicos de los algoritmos ávidos

• Elección ávida: En cada paso, el algoritmo elige la mejor opción local, que según su criterio, llevará a una solución globalmente óptima.
• Estructura óptima: El problema debe tener la propiedad de que las soluciones localmente óptimas se puedan combinar para obtener una solución globalmente óptima.
• Monotonía: Después de elegir un paso localmente óptimo, la solución no debe empeorarse con elecciones posteriores.

Ventajas y desventajas de los algoritmos ávidos

Ventajas:

• Simplicidad en la implementación: Los algoritmos ávidos son frecuentemente fáciles de entender e implementar.
• Eficiencia: Generalmente, son más rápidos que algoritmos más complejos, como la programación dinámica.

Desventajas:

• Falta de óptimo global: Los algoritmos ávidos no siempre llevan a una solución óptima global.
• No todos los problemas son aptos: Solo ciertos problemas pueden resolverse con algoritmos ávidos.

Hay toda una clase de problemas donde la mejor solución se alcanza con un algoritmo ávido. Será útil que conozcas sobre ellos.

4.2 Problema de cambio de monedas.

Problema:

Tenemos monedas de diferentes denominaciones. Necesitamos encontrar la cantidad mínima de monedas para dar cambio de una cantidad dada.

Solución:

Siempre se toma la moneda de mayor denominación que no exceda la cantidad restante.

Complejidad temporal: O(n), donde n es el número de tipos de monedas.

Ejemplo de código en Python:

def min_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count
        

4.3 Problema de la mochila

Problema:

Tenemos objetos con un valor y un peso conocidos. Queremos meter en una mochila de tamaño fijo la mayor cantidad de valor posible.

En esta variante del problema los objetos se pueden dividir en partes. Por ejemplo, si queremos comprar diferentes cereales, podemos comprar tanto 1000 gramos como 512.

Solución:

Ordenar los objetos por su valor unitario (valor/peso) y elegir los mayores valores unitarios hasta llenar la mochila.

Complejidad temporal: O(n log n), donde n es el número de objetos.

Ejemplo de código en Python:

class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight
        self.ratio = value / weight
        
def fractional_knapsack(items, capacity):
    items.sort(key=lambda x: x.ratio, reverse=True)
    total_value = 0.0
    for item in items:
        if capacity >= item.weight:
            total_value += item.value
            capacity -= item.weight
        else:
            total_value += item.ratio * capacity
            break
    return total_value
        
        

4.4 Problema de cobertura con segmentos

Problema:

Hay segmentos en una línea recta, definidos por sus extremos (x1, x2), y un segmento objetivo. Necesitamos encontrar el número mínimo de segmentos que cubren todos los puntos del segmento objetivo.

Solución:

Ordenar los segmentos por su extremo derecho y elegir el segmento más pequeño que cubra el punto actual.

Complejidad temporal: O(n log n), donde n es el número de segmentos.

Ejemplo de código en Python:

def min_segments(segments):
    segments.sort(key=lambda x: x[1])
    count = 0
    end = -float('inf')
    for seg in segments:
        if seg[0] > end:
            end = seg[1]
            count += 1
    return count
        

1

Cuestionario/control

Algoritmos voraces, nivel 59, lección 3

No disponible

Algoritmos voraces

Algoritmos voraces

Abrir