Algoritmos

osCapí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 nentradas 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 elvalor 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á

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 óptimoglobal 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 lasolución en etapas 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 losproblemas admiten esta 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 esnecesario perder 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...