metodo coloso

Diseño de Algoritmos
TEMA 10: ALGORITMOS GOLOSOS
10.1 Introducción

El método que produce algoritmos golosos 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 lossubconjuntos 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.

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

Un conjunto decandidatos, 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 encontraruna 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.

1

Diseño de Algoritmos
Con estos elementos, podemos resumir el funcionamiento de los algoritmos golosos en
los siguientes puntos:

1.Para resolver el problema, un algoritmo goloso 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ñadirlo. 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 conjuntoobtenido es
solución.

Resumiendo, los algoritmos golosos construyen la solució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:

2

Diseño de Algoritmos
PROCEDURE AlgoritmoGoloso(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
ENDIF;
ENDIF;
ENDWHILE;
RETURN solucion;
END AlgoritmoGoloso;

De este esquema se desprende que los algoritmos golosos son muy fáciles deimplementar y producen soluciones muy eficientes. Entonces cabe preguntarse ¿por
qué no utilizarlos siempre? En primer lugar, porque no todos los problemas admiten
esta estrategia de solución. De hecho, la búsqueda de óptimos locales no tiene por qué
conducir siempre a un óptimo global. La estrategia de los algoritmos golosos consiste
en tratar de ganar todas las batallas sin pensar que, como biensaben los estrategas
militares y los jugadores de ajedrez, para ganar la guerra muchas veces es necesario
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...