Capítulo 16. Algoritmos Greedy (Parte I)

Características de los Algoritmos Greedy

 

La técnica de diseño de algoritmos denominada Greedy (algoritmos voraces) es aquella que va construyendo la solución de un problema a partir de decisiones parciales tomadas en base a la información disponible en cada momento.

 

No mira hacia adelante, es decir, no ve los efectos de las decisiones tomadas a futuro y nunca reconsidera una decisión ya tomada.

 

Esta técnica es utilizada en general para resolver problemas de optimización. Suelen ser muy eficientes pero su eficacia debe ser validada, o sea, debe tenerse mucho cuidado con su correctitud. Esto quiere decir que se debe demostrar que la solución encontrada es óptima.

 

Se basa en un conjunto de candidatos a formar parte de la solución. En cada paso se toma uno de los candidatos, el más apropiado y se evalúa si sirve o no. Si sirve, el candidato es agregado a la solución, caso contrario es descartado. Para ello, es necesario saber en todo momento, dado un candidato, si el mismo está pendiente de ser evaluado, si ya fue evaluado y agregado a la solución o si fue descartado.

 

Para cumplir con esto deben conocerse cuatro funciones:

• La función selección que es la que selecciona el mejor candidato dentro de los pendientes.
• La función factibilidad que evalúa si un candidato seleccionado es factible de formar parte de la solución.
• La función solución que evalúa si un conjunto solución propuesto conforma la solución al problema.
• La función objetivo que es la que se debe maximizar o minimizar (optimizar).

 

En el próximo capítulo presentaremos el pseudocódigo de la forma general de los algoritmos Greedy. Tener en cuenta que, aunque las cuatro funciones mencionadas deben estar presentes en el diseño, no siempre es trivial la identificación de las mismas dentro del algoritmo.

Fuentes:

 

Programación III - Apuntes de Cátedra. Cuadrado Estrebou, María Fernanda. Trutner, Guillermo Hernán.