Estructuras de datos: algoritmos codiciosos

Un algoritmo está diseñado para lograr una solución óptima para un problema dado. En el enfoque de algoritmo codicioso, las decisiones se toman a partir del dominio de solución dado. Como codicioso, se elige la solución más cercana que parece proporcionar una solución óptima.

Los algoritmos codiciosos intentan encontrar una solución óptima localizada, que eventualmente puede conducir a soluciones optimizadas globalmente. Sin embargo, los algoritmos generalmente codiciosos no proporcionan soluciones optimizadas globalmente.

Contando monedas

Este problema es contar hasta un valor deseado eligiendo la menor cantidad de monedas posibles y el enfoque codicioso obliga al algoritmo a elegir la moneda más grande posible. Si nos proporcionan monedas de ₹ 1, 2, 5 y 10 y se nos pide que cuentemos ₹ 18, el procedimiento codicioso será:

• 1 - Seleccione una moneda de ₹ 10, la cuenta restante es 8

• 2 - Luego seleccione una moneda de ₹ 5, la cuenta restante es 3

• 3 - Luego seleccione una moneda de ₹ 2, la cuenta restante es 1

• 4 - Y finalmente, la selección de una moneda de ₹ 1 resuelve el problema.

Sin embargo, parece estar funcionando bien, para este recuento necesitamos elegir solo 4 monedas. Pero si cambiamos ligeramente el problema, es posible que el mismo enfoque no pueda producir el mismo resultado óptimo.

Para el sistema monetario, donde tenemos monedas de valor 1, 7, 10, contar monedas por valor 18 será absolutamente óptimo, pero para cuentas como 15, puede usar más monedas de las necesarias. Por ejemplo, el enfoque codicioso utilizará 10 + 1 + 1 + 1 + 1 + 1, un total de 6 monedas. Mientras que el mismo problema podría resolverse usando solo 3 monedas (7 + 7 + 1)

Por lo tanto, podemos concluir que el enfoque codicioso elige una solución optimizada inmediata y puede fallar cuando la optimización global es una preocupación importante.

Ejemplos

La mayoría de los algoritmos de redes utilizan el enfoque codicioso. Aquí hay una lista de algunos de ellos:

• Problema del vendedor ambulante
• 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
• Gráfico - Colorear Mapa
• Gráfico - Cubierta de vértice
• Problema de la mochila
• Problema de programación de trabajos

Hay muchos problemas similares que utilizan el enfoque codicioso para encontrar una solución óptima.