Algoritmo voraz

En ciencias de la computación, un algoritmo voraz (también conocido como goloso, ávido, devorador o greedy) es una estrategia de búsqueda por la cual se sigue una heurística consistente en elegir la opción óptima en cada paso local con la esperanza de llegar a una solución general óptima. Este esquema algorítmico es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente se aplica a los problemas de optimización.

Un algoritmo voraz determina el mínimo número de monedas que debe devolverse en el cambio. En la figura se muestran los pasos que un ser humano debería seguir para emular a un algoritmo voraz para acumular 36 céntimos usando solamente monedas de valores nominales de 1, 5, 10 y 20. La moneda del mayor valor menor que el resto debido es el óptimo local en cada paso. Nótese que en general el problema de devolución del cambio requiere programación dinámica o programación lineal para encontrar una solución óptima. Sin embargo, en muchos sistemas monetarios, incluyendo el euro y el dólar estadounidense, son casos especiales donde en la estrategia del algoritmo voraz da con la solución óptima.

Esquema

Dado un conjunto finito de entradas $C$, un algoritmo voraz devuelve un conjunto $S$ (seleccionados) tal que $S\subseteq C$ y que además cumple con las restricciones del problema inicial. A cada conjunto $S$ que satisfaga las restricciones se le suele denominar prometedor, y si este además logra que la función objetivo se minimice o maximice (según corresponda) diremos que $S$ es una solución óptima.

Características

Se utilizan generalmente para resolver problemas de optimización (obtener el máximo o el mínimo). Toman decisiones en función de la información que está disponible en cada momento. Una vez tomada la decisión, ésta no vuelve a replantearse en el futuro. Suelen ser rápidos y fáciles de implementar. No siempre garantizan alcanzar la solución óptima.

El enfoque “greedy” no nos garantiza obtener soluciones óptimas. Por lo tanto, siempre habrá que estudiar la corrección del algoritmo para demostrar si las soluciones obtenidas son óptimas o no.

Elementos de los que consta la técnica

• El conjunto $C$ de candidatos, entradas del problema.
• Función solución. Comprueba, en cada paso, si el subconjunto actual de candidatos elegidos forma una solución (no importa si es óptima o no lo es).
• Función de selección. Informa cuál es el elemento más prometedor para completar la solución. Este no puede haber sido escogido con anterioridad. Cada elemento es considerado una sola vez. Luego, puede ser rechazado o aceptado y pertenecerá a $C\setminus S$.
• Función de factibilidad. Informa si a partir de un conjunto se puede llegar a una solución. Lo aplicaremos al conjunto de seleccionados unido con el elemento más prometedor.
• Función objetivo. Es aquella que queremos maximizar o minimizar, el núcleo del problema.

Funcionamiento

El algoritmo escoge en cada paso al mejor elemento $x\in C$ posible, conocido como el elemento más prometedor. Se elimina ese elemento del conjunto de candidatos ($C\gets C\setminus \{x\}$) y, acto seguido, comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados ($S\cup \{x\}$) produce una solución factible.

En caso de que así sea, se incluye ese elemento en $S$. Si la inclusión no fuera factible, se descarta el elemento. Iteramos el bucle, comprobando si el conjunto de seleccionados es una solución y, si no es así, pasando al siguiente elemento del conjunto de candidatos.

Algoritmo

Greedy (conjunto de candidatos C): solución S

S = Ø

while (S no sea una solución y C ≠ Ø) {

x = selección(C)

C = C – {x}

if (S∪{x} es factible)

S = S∪{x}

}

if (S es una solución)

return S;

else

return “No se encontró una solución”;

Aplicaciones

• Planificación de tareas.
• Minimización del tiempo de espera=Almacenamiento en cintas.
• Planificación de tareas a plazo fijo = Selección de actividades.
• Cajero (devolver un número mínimo de monedas/billetes [pero no sellos]).
• Caminos mínimos en grafos (algoritmo de Dijkstra).
• Árbol generador minimal (algoritmos de Prim & Kruskal Kruskal).
• Códigos Huffman y compresión de datos.
• Construcción de árboles de decisión.
• Heurísticas greedy…

Heurísticas greedy

Hay situaciones en las cuales no podemos encontrar un algoritmo greedy que proporcione una solución óptima…

En muchas ocasiones, se podrían obtener mejores soluciones reconsiderando alternativas desechadas por un algoritmo greedy (cuando, a partir de una solución óptima local no se puede alcanzar una solución óptima global).

Pese a ello, resultan útiles los algoritmos greedy que proporcionan una solución rápida a problemas complejos, aunque ésta no sea óptima.

Ejemplos de algoritmos voraces

• Algoritmo de Kruskal
• Algoritmo de Prim
• Algoritmo de Dijkstra
• Algoritmo de triangulación voraz
• Algoritmo para la ubicación óptima

Temas relacionados

• Algoritmo
• Algoritmo heurístico

Referencias

• Brassard, Gilles; Bratley, Paul (1997). «Algoritmos voraces». Fundamentos de Algoritmia. Madrid: PRENTICE HALL. ISBN 84-89660-00-X. 
• Departamento de ciencias de la computación Universidad de Granada. (s. f.). Algoritmos Greedy.
• Abad Soriano, M. T. (2007–2008). Algoritmos voraces.
• Fillottrani, P. R. (2017). Algoritmos y complejidad.

Enlaces externos

• Wikilibros alberga un libro o manual sobre Algoritmia/Algoritmos voraces.

En inglés:

• Definición del NIST

• Datos: Q504353
• Multimedia: Greedy algorithms / Q504353