Algoritmos Voraces (Greedy Algorithms) PDF

ALGORITMOS VORACES (GREEDY ALGORITHMS) Generalidades y ejemplo ¿En qué consiste la técnica? 01 02 03 Los algoritmos voraces es El algoritmo nunca reversa El algoritmo puede no una técnica para resolver una decisión anterior, aún lograr...

ALGORITMOS VORACES (GREEDY ALGORITHMS) Generalidades y ejemplo ¿En qué consiste la técnica? 01 02 03 Los algoritmos voraces es El algoritmo nunca reversa El algoritmo puede no una técnica para resolver una decisión anterior, aún lograr la solución óptima, un problema, mediante la si esa escogencia fue pero si una solución escogencia de la mejor “mala”. bastante buena. opción disponible en el momento. Metodología Si el conjunto solución es En cada paso se agrega un factible, se conserva el Para comenzar, el conjunto ítem al conjunto solución, ítem agregado. En caso solución (Que contiene las hasta que se logra una contrario, se descarta ese respuestas) está vacío. solución. ítem y no se considera nuevamente.  Ejemplo Problema: Dar cambio de una Las monedas disponibles son: No hay cantidad límite en la Cantidad a devolver: $1800 cierta cantidad, usando la cantidad de monedas de cada menor cantidad posible de denominación. monedas. $100 $200 $500 Ejemplo (cont) CONJUNTO SOLUCIÓN = {} DENOMINACIONES ¿COMO PROCEDEMOS? DISPONIBLES = {100, 200, 500} Paso a paso Tomar monedas de la denominación más grande, mientras la suma sea menor o igual a la cantidad solicitada (1800): Solución = {500, 500, 500, 500 Suma = 500 1000 1500 2000 Tomar de la siguiente denominación más grande: Solución = {500, 500, 500, 200, 200 Suma = 1700, 1900 Tomar de la siguiente denominación: Solución = {500, 500, 500, 200, 100} Suma = 1800 objetivo alcanzado, termina el algoritmo