DAA - Método codicioso

Entre todos los enfoques algorítmicos, el enfoque más simple y directo es el método Greedy. En este enfoque, la decisión se toma sobre la base de la información disponible actual sin preocuparse por el efecto de la decisión actual en el futuro.

Los algoritmos codiciosos construyen una solución parte por parte, eligiendo la siguiente parte de tal manera que brinde un beneficio inmediato. Este enfoque nunca reconsidera las opciones tomadas anteriormente. Este enfoque se utiliza principalmente para resolver problemas de optimización. El método codicioso es fácil de implementar y bastante eficiente en la mayoría de los casos. Por lo tanto, podemos decir que el algoritmo Greedy es un paradigma algorítmico basado en la heurística que sigue la elección óptima local en cada paso con la esperanza de encontrar una solución óptima global.

En muchos problemas, no produce una solución óptima, aunque ofrece una solución aproximada (casi óptima) en un tiempo razonable.

Componentes del algoritmo codicioso

Los algoritmos codiciosos tienen los siguientes cinco componentes:

  • A candidate set - Se crea una solución a partir de este conjunto.

  • A selection function - Se utiliza para elegir el mejor candidato para agregar a la solución.

  • A feasibility function - Se utiliza para determinar si se puede utilizar un candidato para contribuir a la solución.

  • An objective function - Se utiliza para asignar un valor a una solución o una solución parcial.

  • A solution function - Se utiliza para indicar si se ha alcanzado una solución completa.

Areas de aplicación

El enfoque codicioso se utiliza para resolver muchos problemas, como

  • Encontrar el camino más corto entre dos vértices usando el algoritmo de Dijkstra.

  • Encontrar el árbol de expansión mínimo en un gráfico usando el algoritmo de Prim / Kruskal, etc.

Donde el enfoque codicioso falla

En muchos problemas, el algoritmo Greedy no logra encontrar una solución óptima; además, puede producir la peor solución. Problemas como el viajante y la mochila no se pueden resolver con este enfoque.