Análise e Técnicas de Algoritmos
Período 2002.2

Aula 9: Método Guloso

20/01/2003

Também disponível nos formatos pdf e no formato ps.

Características Gerais de Algoritmos Gulosos

Como apresentado, algoritmos gulosos são utilizados para resolver problemas de otimização. Os algoritmos que se baseiam em uma estratégia gulosa são, em geral, simples e de fácil implementação. É possível definir elementos que comumente fazem parte de uma solução gulosa, na tentativa de definir uma cara genérica para uma solução gulosa. Vamos considerar o exemplo do cálculo do trôco, em um sistema monetário que apresenta o seguinte conjunto de moedas $C = \{ 100, 25, 10, 5, 1 \}$. Uma possível solução que utiliza estratégia gulosa é apresentada abaixo:

A solução é obtida partindo-se de um conjunto vazio de moedas e, em cada etapa, escollhendo a maior moeda possível. É possível identificar neste algortimo os seguintes elementos:

1. Uma lista de candidatos, definido pelo conjunto $C$.
2. Uma lista de elementos escolhidos, definido pelo conjunto $S$.
3. Uma função SELEÇÃO que seleciona um dos candidatos. No nosso exemplo é a uma função que retorna a maior moeda.
4. Uma função VIABILIDADE que verifica a viabilidade da escolha. No exemplo, a função que testa se a soma dos valores da nova moeda escolhida com os valores das moedas previamentes escolhidas não ultrapassa o valor do montante.
5. Uma função SOLUÇÃO que verifica se um determinado conjunto de candidatos é uma solução para o problema. Em nosso exemplo, é a função que testa se a soma dos elementos escolhidos é igual ao montante $M$.

Além dos elementos listados, em algumas soluções é possível identificar mais dois elementos: um conjunto de candidatos rejeitados e uma função que define o valor de uma solução (serve para definir a eficiência de uma solução. No exemplo do cálculo do trôco, essa função retorna o número de moedas utilizadas para fornecer o trôco).

Solução Genérica

Um algoritmo guloso genérico define inicialmente um conjunto vazio de candidatos escolhidos. Em cada etapa um novo elemento é escolhido da lista de candidatos e adicionado ao conjunto de candidatos escolhidos. Esta escolha é guiada pela função SELEÇÃO que através do crivo da função VIABILIDADE define se o elemento selecionado deve ser considerado ou rejeitado. Se o elemento for rejeitado ele não deve ser considerado novamente. Se o elemento é adicionado ao conjunto dos elementos escolhidos, a função SOLUÇÃO verifica se o novo conjunto corresponde a solução do problema.