viernes 23 agosto 2024

¿Qué son los algoritmos voraces?

Los algoritmos voraces (también conocidos como algoritmos greedy en inglés) son un tipo de algoritmo que toma decisiones secuenciales, eligiendo en cada paso la opción que parece ser la mejor en ese momento, con la esperanza de encontrar una solución global óptima. Estos algoritmos no siempre garantizan la mejor solución en todos los casos, pero son muy útiles cuando pueden asegurar una solución óptima o cuando una solución aproximada es suficiente.

Características de los Algoritmos Voraces:

1. Selección Voraz (Greedy Choice): En cada paso, el algoritmo elige la opción que parece ser la mejor en ese momento.

2. Subestructura óptima: El problema puede ser resuelto combinando soluciones óptimas de subproblemas.

3. Irreversibilidad: Las decisiones hechas no se revisan. Una vez tomada una decisión, no se reconsidera.

Ejemplos Clásicos de Algoritmos Voraces

1. Problema del Cambio de Monedas

El problema consiste en devolver una cantidad de dinero usando la menor cantidad de monedas posibles. Supongamos que tenemos monedas de diferentes denominaciones.

Ejemplo en TypeScript:

function cambiarMonedas(cantidad: number, denominaciones: number[]): number[] {
    // Array que almacenará las monedas utilizadas
    let resultado: number[] = [];
    
    // Ordenamos las denominaciones de mayor a menor
    denominaciones.sort((a, b) => b - a);
    
    for (let i = 0; i < denominaciones.length; i++) {
        // Mientras podamos usar la moneda de esta denominación
        while (cantidad >= denominaciones[i]) {
            cantidad -= denominaciones[i];
            resultado.push(denominaciones[i]);
        }
    }
    
    return resultado;
}

// Uso del algoritmo
let cantidad = 67;
let denominaciones = [25, 10, 5, 1];
let cambio = cambiarMonedas(cantidad, denominaciones);
console.log(cambio);  // [25, 25, 10, 5, 1, 1]

Explicación:

Este algoritmo selecciona siempre la moneda de mayor valor que pueda ser utilizada para reducir la cantidad restante. Aunque este enfoque funciona perfectamente en muchos sistemas monetarios (como el dólar), no garantiza siempre la solución óptima en otros sistemas donde las denominaciones no son tan "amigables".

2. Problema de la Mochila Fraccionaria

Dado un conjunto de objetos, cada uno con un peso y un valor, y una mochila que puede contener un peso máximo, el objetivo es maximizar el valor total de los objetos en la mochila. En la versión fraccionaria, puedes tomar fracciones de los objetos.

Ejemplo en TypeScript:

type Objeto = {
    peso: number;
    valor: number;
};

function mochilaFraccionaria(pesoMaximo: number, objetos: Objeto[]): number {
    // Calculamos el valor por peso de cada objeto
    let objetosConValorPorPeso = objetos.map(objeto => ({
        ...objeto,
        valorPorPeso: objeto.valor / objeto.peso
    }));
    
    // Ordenamos los objetos por su valor por peso de mayor a menor
    objetosConValorPorPeso.sort((a, b) => b.valorPorPeso - a.valorPorPeso);
    
    let valorTotal = 0;
    let pesoActual = 0;
    
    for (let i = 0; i < objetosConValorPorPeso.length && pesoActual < pesoMaximo; i++) {
        let objeto = objetosConValorPorPeso[i];
        
        if (pesoActual + objeto.peso <= pesoMaximo) {
            // Si el objeto entero cabe en la mochila, lo tomamos todo
            pesoActual += objeto.peso;
            valorTotal += objeto.valor;
        } else {
            // Si no cabe entero, tomamos la fracción que cabe
            let fraccion = (pesoMaximo - pesoActual) / objeto.peso;
            pesoActual += objeto.peso * fraccion;
            valorTotal += objeto.valor * fraccion;
        }
    }
    
    return valorTotal;
}

// Uso del algoritmo
let objetos: Objeto[] = [
    { peso: 10, valor: 60 },
    { peso: 20, valor: 100 },
    { peso: 30, valor: 120 }
];
let pesoMaximo = 50;
let valorMaximo = mochilaFraccionaria(pesoMaximo, objetos);
console.log(valorMaximo);  // 240

Explicación:

El algoritmo selecciona primero los objetos con el mayor valor por unidad de peso, tomando tanto como sea posible (o una fracción si el objeto no cabe completamente). En este caso, la estrategia voraz asegura la solución óptima.

Conclusión

Los algoritmos voraces son herramientas poderosas, especialmente cuando se pueden aplicar a problemas con subestructuras óptimas y donde las decisiones locales óptimas conducen a una solución global óptima. Sin embargo, en algunos problemas, la elección voraz no garantiza la solución óptima, y se necesita utilizar otros enfoques, como la programación dinámica o backtracking.

Etiquetas:

algoritmos typescript

Creado por:

Jorge García

Fullstack developer