Algoritmos ávidos

Definición

El método que produce algoritmos ávidos es un método muy sencillo y que puede  ser aplicado a numerosos problemas, especialmente los de optimización. Dado un problema con n entradas el método consiste en obtener un subconjunto de éstas que satisfaga una determinada restricción definida para el problema. Cada uno de los subconjuntos que cumplan las restricciones diremos que son soluciones prometedoras. Una solución prometedora que maximice o minimice una función objetivo la denominaremos solución óptima.

¿Cuándo usar un algoritmo ávido?

Como ayuda para identificar si un problema es susceptible de ser resuelto por  un algoritmo ávido vamos a definir una serie de elementos que han de estar  presentes en el problema:

•  Un conjunto de candidatos, que corresponden a las n entradas del problema.
•  Una función de selección que en cada momento determine el candidato idóneo para formar la solución de entre  los que aún no han sido seleccionados ni rechazados.
•  Una función que compruebe si un cierto subconjunto de candidatos es prometedor. Entendemos por prometedor que sea posible seguir añadiendo  candidatos y encontrar una solución.
•  Una  función objetivo que determine el valor de  la solución hallada. Es la  función que queremos maximizar o minimizar.
•  Una función que compruebe si un subconjunto de estas entradas es solución al problema, sea óptima o no.

Con estos elementos, podemos resumir el funcionamiento de los algoritmos ávidos en los siguientes puntos:

1. Para resolver el problema, un algoritmo ávido tratará de encontrar un subconjunto de candidatos tales que, cumpliendo las restricciones del problema, constituya la solución óptima.
2. Para ello trabajará por etapas, tomando en cada una de ellas la decisión que le  parece la mejor, sin considerar las consecuencias futuras, y por tanto escogerá de entre todos los candidatos el que produce un óptimo local para esa etapa,  suponiendo que será a su vez óptimo global para el problema.
3. Antes de añadir un candidato a la solución que está construyendo comprobará si  es prometedora al añadilo. En caso afirmativo lo incluirá en ella y en caso  contrario descartará este candidato para siempre y no volverá a considerarlo.
4. Cada vez que se incluye un candidato comprobará si el conjunto obtenido es  solución.

Resumiendo, los algoritmos ávidos construyen la solución en etapas sucesivas,  tratando siempre de tomar la decisión óptima para cada etapa.

El algoritmo

A la vista de todo  esto no resulta difícil plantear un esquema general para este tipo de algoritmos:

PROCEDURE AlgoritmoAvido(entrada:CONJUNTO):CONJUNTO;
VAR x:ELEMENTO; solucion:CONJUNTO; encontrada:BOOLEAN;
BEGIN
encontrada:=FALSE; crear(solucion);
WHILE NOT EsVacio(entrada) AND (NOT encontrada) DO
x:=SeleccionarCandidato(entrada);
IF EsPrometedor(x,solucion) THEN
Incluir(x,solucion);
IF EsSolucion(solucion) THEN
encontrada:=TRUE
END;
END
END;
RETURN solucion;
END AlgoritmoAvido;

Fuente: Técnicas de Diseño de Algoritmos de Rosa Guerequeta y Antonio Vallecillo , Servicio de Publicaciones de la Universidad de Málaga.