Algoritmos Gulosos

Algoritmos Gulosos

1 Introdução

De forma geral, os algoritmos relacionados com otimização lidam com uma sequencia, de passos, sendo que em cada passo há um conjunto de escolhas/opções, ou seja, uma estratégia para resolver problemas de otimização.

Os algoritmos gulosos escolhem a opção que parece ser a melhor no momento (escolha ótima), e esperam que desta forma consiga-se chegar a uma solução ótima global.

Embora nem sempre seja possível chegar a uma solução ótima a partir da utilização de algoritmos gulosos, eles são eficientes em uma ampla variedade de problemas.

Os algoritmos gulosos tomam decisões com base apenas na informação disponível, sem se preocupar com os efeitos futuros de tais decisões, isto é, eles nunca reconsideram as decisões tomadas, independentemente das consequência . Não há, portanto, necessidade de avaliar as alternativas nem de empregar procedimentos elaborados permitindo que decisões anteriores sejam desfeitas. Devido a tais características, de forma geral eles são fáceis de inventar e implementar, e são eficientes quando funcionam.

2. Algoritmos Gulosos

É uma técnica de algoritmos para resolver problemas de otimização, sempre realizando a escolha que parece ser a melhor no momento; fazendo uma escolha ótima local, na esperança de que esta escolha leve até a solução ótima global.

Para possibilitar uma noção geral de como trabalham os algoritmos gulosos, vamos abordar um exemplo. Suponha que tenhamos disponíveis moedas com valores de 1.00, 0.25, 0.10,0.05 e 0.00 1. O problema é criar um algoritmo que para conseguir obter um determinado valor com o menor numero de moedas possível (problema do troco).

Suponha que é preciso “dar um troco” de $2.89. A melhor solução, isto é, o menor número de moedas possível para obter o valor, consiste em 10 moedas: 2 de valor 100, 3 de valor 25, 1 de valor 10 e 4 de valor 1. De forma geral, agimos tal como um algoritmo guloso: em cada estágio adicionamos a moeda de maior valor possível, de forma a não passar da quantia necessária.

Embora seja uma afirmação difícil de provar, é verdade que com os valores dados das moedas, e tendo-se disponível uma quantidade adequada de cada uma, o algoritmo sempre irá fornecer uma solução ótima para o problema. Entretanto, ressalta-se que para diferentes valores de moedas, ou então quando se tem uma quantidade limitada de cada uma, o algoritmo guloso pode vir a não chegar em uma solução ótima, ou até mesmo não chegar a solução nenhuma (mesmo esta existindo). O algoritmo para resolver o problema do troco é apresentado a seguir

Algoritmo 1 Algoritmo que “dá o troco” para n unidades usando o menor n´umero possível de moedas.

1: função TROCO(n)

2: const C {100, 25, 10, 5, 1} . C é o conjunto de moedas

3: S 0 S é o conjunto que irá conter a solução

4: s 0 s é a soma dos itens em S

5: enquanto s ≠ n faça

6: x o maior item em C tal que s + x • n

7: se este item não existe então

8: retorne “Não foi encontrada uma solução!”

9: fim se

10: S Ã U {uma moeda de valor x}

11: s s + x

12: fim enquanto

13: retorne S

14: fim função

O algoritmo apresentado é caracterizado como guloso porque a cada passo ele escolhe o maior valor possível, sem refazer suas decisões, isto é, uma vez que um determinado valor de moeda foi escolhido, não se retira mais este valor do conjunto solução.

Uma outra estratégia para resolver este problema é a programação dinâmica, a qual irá sempre obter um resultado. Entretanto, os algoritmos gulosos são mais simples, e quando tanto o algoritmo guloso quanto o algoritmo utilizando programação dinâmica funcionam, o primeiro é mais eficiente. A seguir serão apresentadas as características gerais dos algoritmos gulosos.

2. Características gerais dos algoritmos gulosos

De forma geral, os algoritmos gulosos e os problemas por eles resolvidos são caracterizados pelos itens abordados a seguir. Para facilitar o entendimento, cada um dos itens será relacionado ao exemplo exposto anteriormente (problema do troco):

• há um problema a ser resolvido de maneira ótima, e para construir a solução existe um conjunto de candidatos. No caso do problema do troco, os candidatos são o conjunto de moedas. (que possuem valor 100, 25, 10, 5 e 1), com quantidade de moedas suficiente de cada valor;

• durante a “execução” do algoritmo são criados dois conjuntos: um contem os elementos que foram avaliados e rejeitados e outro os elementos que foram analisados e escolhidos;

• há uma função que verifica se um conjunto de candidatos produz uma solução para o problema. Neste momento, questões de otimalidade não são levadas em consideração. No caso do exemplo, esta função verificaria se o valor das moedas já escolhidas é exatamente igual ao valor desejado.

• uma segunda função e responsável por verificar a viabilidade do conjunto de candidatos, ou seja, se é ou não possível adicionar mais candidatos a este conjunto de tal forma que pelo menos uma solução seja obtida. Assim como no item anterior, não há preocupação com otimalidade. No caso do problema do troco, um conjunto de moedas é viável se seu valor total não excede o valor desejado;

• uma terceira função, denominada função de seleção, busca identificar qual dos candidatos restantes (isto é, que ainda não foram analisados e enviados ou para o conjunto dos rejeitados ou dos aceitos) é o melhor (o conceito de melhor dependerá do contexto do problema). No exemplo, a função de seleção seria responsável por escolher a moeda com maior valor entre as restantes;

• por fim, existe a função objetivo, a qual retorna o valor da solução encontrada. No exemplo, esta função seria responsável