Algoritmo codicioso

Tabla de contenido

Solución factible
Algoritmo codicioso
Ejemplo: enfoque codicioso
Aplicaciones de algoritmos codiciosos

En este tutorial, aprenderá qué es un algoritmo codicioso. Además, encontrará un ejemplo de un enfoque codicioso.

Un algoritmo codicioso es un enfoque para resolver un problema seleccionando la mejor opción disponible en este momento, sin preocuparse por el resultado futuro que traería. En otras palabras, las mejores opciones a nivel local apuntan a producir los mejores resultados a nivel mundial.

Este algoritmo puede no ser la mejor opción para todos los problemas. Puede producir resultados incorrectos en algunos casos.

Este algoritmo nunca retrocede para revertir la decisión tomada. Este algoritmo funciona con un enfoque de arriba hacia abajo.

La principal ventaja de este algoritmo es:

El algoritmo es más fácil de describir .
Este algoritmo puede funcionar mejor que otros algoritmos (pero no en todos los casos).

Solución factible

Una solución factible es aquella que brinda la solución óptima al problema.

Algoritmo codicioso

Para empezar, el conjunto de soluciones (que contiene respuestas) está vacío.
En cada paso, se agrega un elemento al conjunto de soluciones.
Si el conjunto de soluciones es factible, se mantiene el elemento actual.
De lo contrario, el artículo se rechaza y nunca se vuelve a considerar.

Ejemplo: enfoque codicioso

 Problema: Tienes que cambiar una cantidad utilizando la menor cantidad posible de monedas. Monto: $ 28 Monedas disponibles: $ 5 moneda $ 2 moneda $ 1 moneda

Solución:

Cree un conjunto de soluciones vacío = ().
monedas = (5, 2, 1)
suma = 0
Mientras suma ≠ 28, haga lo siguiente.
Seleccione una moneda C de las monedas de modo que sume + C <28.
Si C + suma> 28, no devuelve ninguna solución.
De lo contrario, suma = suma + C.
Agregue C al conjunto de soluciones.

Hasta las primeras 5 iteraciones, el conjunto de soluciones contiene 5 monedas de $ 5. Después de eso, obtenemos 1 moneda de $ 2 y finalmente, 1 moneda de $ 1.