Algoritmos voraces

Capítulo 4
ALGORITMOS ÁVIDOS

4.1 INTRODUCCIÓ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 lasrestricciones diremos que son soluciones
prometedoras. Una solución prometedora que maximice o minimice una función
objetivo la denominaremos solución óptima.
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 entradasdel 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 valorde 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á

142

TÉCNICAS DE DISEÑO DE ALGORITMOS

de entre todos los candidatos el que produce un óptimo local para esa etapa,
suponiendo que será a su vez óptimo global para elproblema.
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 enetapas sucesivas,
tratando siempre de tomar la decisión óptima para cada etapa. 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) DOx:=SeleccionarCandidato(entrada);
IF EsPrometedor(x,solucion) THEN
Incluir(x,solucion);
IF EsSolucion(solucion) THEN
encontrada:=TRUE
END;
END
END;
RETURN solucion;
END AlgoritmoAvido;

De este esquema se desprende que los algoritmos ávidos son muy fáciles de
implementar y producen soluciones muy eficientes. Entonces cabe preguntarse
¿por qué no utilizarlos siempre? En primer lugar, porque no todos los problemas
admitenesta estrategia de solución. De hecho, la búsqueda de óptimos locales no
tiene por qué conducir siempre a un óptimo global, como mostraremos en varios
ejemplos de este capítulo. La estrategia de los algoritmos ávidos consiste en tratar
de ganar todas las batallas sin pensar que, como bien saben los estrategas militares
y los jugadores de ajedrez, para ganar la guerra muchas veces es necesarioperder
alguna batalla.
Desgraciadamente, y como en la vida misma, pocos hechos hay para los que
podamos afirmar sin miedo a equivocarnos que lo que parece bueno para hoy
siempre es bueno para el futuro. Y aquí radica la dificultad de estos algoritmos.
Encontrar la función de selección que nos garantice que el candidato escogido o
rechazado en un momento determinado es el que ha de formar parte o no...