Algoritmo codicioso
Un algoritmo codicioso es un enfoque para resolver un problema seleccionando la mejor opción disponible en ese momento. No se preocupa si el mejor resultado actual traerá el resultado óptimo general.
El algoritmo nunca revierte la decisión anterior, incluso si la elección es incorrecta. Funciona en un enfoque de arriba hacia abajo.
Es posible que este algoritmo no produzca el mejor resultado para todos los problemas. Es porque siempre busca la mejor opción local para producir el mejor resultado global.
Sin embargo, podemos determinar si el algoritmo se puede usar con cualquier problema si el problema tiene las siguientes propiedades:
1. Propiedad de elección codiciosa
Si se puede encontrar una solución óptima al problema eligiendo la mejor opción en cada paso sin reconsiderar los pasos anteriores una vez elegidos, el problema se puede resolver utilizando un enfoque codicioso. Esta propiedad se llama propiedad de elección codiciosa.
2. Subestructura óptima
Si la solución global óptima del problema corresponde a la solución óptima de sus subproblemas, entonces el problema se puede resolver utilizando un enfoque codicioso. Esta propiedad se llama subestructura óptima.
Ventajas del enfoque codicioso
- el algoritmo es más fácil de describir.
- Este algoritmo puede Desempeñar mejor que otros algoritmos (pero, no en todos los casos).
Inconveniente del enfoque codicioso
Como se mencionó anteriormente, el algoritmo codicioso no siempre produce la solución óptima. Esta es la principal desventaja del algoritmo.
Por ejemplo, supongamos que queremos encontrar el camino más largo en el siguiente gráfico desde la raíz hasta la hoja. Usemos el algoritmo codicioso aquí.
Enfoque codicioso
1. Comencemos con el nodo raíz 20. El peso del niño derecho es 3 y el peso del hijo izquierdo es 2.
2. Nuestro problema es encontrar el camino más largo. Y, la solución óptima en este momento es 3. Entonces, el algoritmo codicioso elegirá 3.
3. Finalmente el peso de un hijo único de 3 es 1. Esto nos da nuestro resultado final. 20 + 3 + 1 = 24
.
Sin embargo, no es la solución óptima. Hay otro camino que lleva más peso (20 + 2 + 10 = 32
) como se muestra en la siguiente imagen.
Por lo tanto, los algoritmos codiciosos no siempre dan una solución óptima/factible.
Algoritmo codicioso
- Para empezar, el conjunto de soluciones (que contiene las respuestas) está vacío.
- En cada paso, se agrega un elemento al conjunto de soluciones hasta que se llega a una solución.
- Si el conjunto de soluciones es factible, se mantiene el elemento actual.
- De lo contrario, el artículo se rechaza y no se vuelve a considerar nunca más.
Ahora usemos este algoritmo para resolver un problema.
Ejemplo: enfoque codicioso
Problem: You have to make a change of an amount using the smallest possible number of coins. Amount: $18 Available coins are $5 coin $2 coin $1 coin There is no limit to the number of each coin you can use.
Solución:
- Crear un vacío
solution-set = { }
. Las monedas disponibles son{5, 2, 1}
. - Se supone que debemos encontrar el
sum = 18
. Empecemos consum = 0
. - Seleccione siempre la moneda con el mayor valor (es decir, 5) hasta que el
sum > 18
. (Cuando seleccionamos el valor más grande en cada paso, esperamos llegar al destino más rápido. Este concepto se llama propiedad de elección codiciosa.) - En la primera iteración,
solution-set = {5}
ysum = 5
. - En la segunda iteración,
solution-set = {5, 5}
ysum = 10
. - En la tercera iteración,
solution-set = {5, 5, 5}
ysum = 15
. - En la cuarta iteración,
solution-set = {5, 5, 5, 2}
ysum = 17
. (No podemos seleccionar 5 aquí porque si lo hacemos,sum = 20
que es mayor que 18. Entonces, seleccionamos el segundo elemento más grande que es 2.) - De manera similar, en la quinta iteración, seleccione 1. Ahora
sum = 18
ysolution-set = {5, 5, 5, 2, 1}
.
Diferentes tipos de algoritmos codiciosos
- Clasificación de selección
- Problema de mochila
- Árbol de expansión mínimo
- Problema de ruta más corta de fuente única
- Problema de programación de trabajos
- Algoritmo de árbol de expansión mínimo de Prim
- Algoritmo de árbol de expansión mínimo de Kruskal
- Algoritmo de árbol de expansión mínimo de Dijkstra
- Codificación de Huffman
- Algoritmo de Ford-Fulkerson