Algoritmos voraces

Una algoritmo voraz es un tipo de algoritmo que nos permite resolver un determinado problema de una forma concreta.

Este tipo de algoritmos voraces se aplica a problemas de optimización en los que la solución se puede construir paso a paso sin necesitar ningún dato o decisión anterior. Generalmente estos algoritmos encuentran un conjunto de candidatos que constituyen la solución y que la optimiza. Es usado en problemas de planificación, problemas que se pueden modelar con grafos y en los que se suele realizar una búsqueda, cálculo de recorridos, optimización de pesos, etc.

Por regla general los problemas que se suelen resolver con este tipo de algoritmos constan de unos candidatos y se trata de encontrar una solución basada en obtener un subconjunto de esos candidatos o una secuencia ordenada de los mismos de manera que se optimice una función objetivo (lo que queramos conseguir).

Para aplicar este tipo de algoritmos se suele trabajar por etapas o fases,  tratando un candidato en cada fase. Hay que ir seleccionando en cada etapa al candidato más "bueno" para lo que buscamos de los aún disponibles y decidir si se incluye o no en la solución.

Trabajando así podemos ver que se examina una vez cada candidato y se decide si se selecciona o se rechaza. Luego se intentará seleccionar al mejor de los candidatos restantes hasta encontrar la solución que se busque. Si el algoritmo es correcto, la primera solución encontrada es la solución óptima.

La principal característica que distingue los algoritmos voraces de otros tipos de algoritmos es que nunca se vuelve a atrás y se anula una decisión ya tomada por lo que cuando se incorpora un candidato a la solución, este permanece hasta el final. Del mismo modo cuando se rechaza un candidato no se vuelve a tener en cuenta.

Este tipo de algoritmos voraces pueden parecer sencillos y al no volver a "ver" los candidatos que ya han sido tratados suelen resultar eficientes en la mayoría de los casos.

Dos problemas de grafos muy conocidos que se resuelven con este tipo de algoritmos son hallar un árbol de recubrimiento de distancia o coste mínimo y calcular el camino de coste mínimo entre un nodo y los demás. Algunos algoritmos muy conocidos para resolverlos son los algoritmos de Prim, algoritmo de Kruskal, algoritmo de Dijkstra.

Otro problemas conocidos que se pueden resolver con algoritmos voraces son el problema de la mochila con objetos fraccionables, problemas de mantenimiento de la conectividad, problemas de mensajería urgente, etc.

Si queréis que profundicemos más sobre este tipo de algoritmos o que resolvamos algún problema con ellos no dudéis en ponerlo en los comentarios ;)