Algoritmos codiciosos (estructura general y aplicaciones)

Greedy Algorithms trabaja paso a paso y siempre elige los pasos que proporcionan beneficios/beneficios inmediatos. Elige la “solución localmente óptima”, sin pensar en las consecuencias futuras. Es posible que los algoritmos codiciosos no siempre conduzcan a la solución global óptima, ya que no consideran todos los datos. La elección realizada por el enfoque codicioso no considera datos y elecciones futuras. En algunos casos, tomar una decisión que parece correcta en ese momento da la mejor solución (Greedy), pero en otros casos, no es así. La técnica voraz se usa para problemas de optimización (donde tenemos que encontrar el máximo o mínimo de algo). La técnica Greedy es la más adecuada para observar la situación inmediata.

Todos los algoritmos codiciosos siguen una estructura básica: 
 

getOptimal(Item, arr[], int n)
  1) Initialize empty result : result = {}  
  2) While (All items are not considered)

      // We make a greedy choice to select
      // an item.
      i = SelectAnItem() 

      // If i is feasible, add i to the 
      // result
      if (feasible(i))
        result = result U i 
  3) return result

¿Por qué elegir el enfoque codicioso?

El enfoque codicioso tiene algunas ventajas y desventajas, lo que puede hacerlo adecuado para la optimización. Una razón importante es lograr la solución más factible de inmediato. En el problema de selección de actividades (explicado a continuación), si se pueden realizar más actividades antes de finalizar la actividad actual, estas actividades se pueden realizar en el mismo tiempo. Otra razón es dividir un problema de forma recursiva en función de una condición, sin necesidad de combinar todas las soluciones. En el problema de selección de actividades, el paso de «división recursiva» se logra escaneando una lista de elementos solo una vez y considerando ciertas actividades.

Propiedad de elección codiciosa: esta propiedad dice que la solución óptima global se puede obtener haciendo una solución óptima localmente (Greedy). La elección realizada por un algoritmo Greedy puede depender de elecciones anteriores pero no del futuro. De forma iterativa, hace una elección Greedy tras otra y reduce el problema dado a uno más pequeño.

Subestructura óptima: un problema exhibe una subestructura óptima si una solución óptima al problema contiene soluciones óptimas a los subproblemas. Eso significa que podemos resolver subproblemas y construir las soluciones para resolver problemas más grandes.

NOTA:  Hacer elecciones localmente óptimas no siempre funciona. Por lo tanto, los algoritmos Greedy no siempre darán las mejores soluciones.

Características del enfoque Greedy 
1. Hay una lista ordenada de recursos (ganancia, costo, valor, etc.) 
2. Se toma el máximo de todos los recursos (ganancia máxima, valor máximo, etc.). 
3. Por ejemplo, en el problema de la mochila fraccionada, se toma primero el valor/peso máximo según la capacidad disponible. 

Aplicaciones de los Algoritmos Codiciosos 
1. Búsqueda de una solución óptima ( Selección de actividad , Mochila fraccional , Secuenciación de trabajos , Codificación Huffman ). 
2. Encontrar una solución cercana a la óptima para problemas NP-Hard como TSP. 

Ventajas y desventajas del enfoque codicioso  
Ventajas 
 

• El enfoque codicioso es fácil de implementar.
• Por lo general, tienen menos complejidades de tiempo.
• Los algoritmos codiciosos se pueden usar con fines de optimización o para encontrar una optimización cercana en el caso de problemas NP difíciles.

Desventajas 
 

• La solución óptima local puede no ser siempre la óptima global.

Algoritmos codiciosos estándar:

• Algoritmo de Prim
• Algoritmo de Kruskal
• Algoritmo de Dijkstra