Algoritmos Guloso

RESUMO

Algoritmos gulosos, também conhecidos como gananciosos ou greedy, são utilizados para problemas de otimização, que lidam com uma sequencia de passos específicos, para resolver um problema. Basicamente, a sua ideia de resolução consiste em resolver a maior parte do problema para posteriormente transformá-lo em um problema menor, e assim por diante. Quando conseguem chegar a uma solução apresentam grande eficiência.

Palavras-chave: Algoritmos Gulosos. Otimização. Estratégia.

LISTA DE ILUSTRAÇÕES

Figura 1 - Algoritmo para encontrar troco 8

Figura 2 - Algoritmo guloso genérico 10

SUMÁRIO

1 INTRODUÇÃO 6

2 ALGORITMOS GULOSOS 7

2.1 CARACTERÍSTICAS DOS ALGORITMOS GULOSOS 8

2.2 ELEMENTOS DA ESTRATÉGIA GULOSA 10

2.2.1 Propriedade gulosa 11

2.2.2 Subestrutura ótima 11

2.3 LIMITAÇÕES DA ESTRATÉGIA GULOSA 11

3 CONCLUSÃO 13

1 INTRODUÇÃO

Um algoritmo guloso, também conhecido por algoritmo ganancioso ou greedy, é um algoritmo usado para realizar a otimização de código. De modo geral, a estratégia gulosa propõe o projeto de um algoritmo iterativo, no qual a cada passo é aplicado um critério de otimização para encontrar parte de uma solução local.

De maneira genérica, algoritmos de otimização lidam com uma sequencia de passos, sendo estes um conjunto de escolhas, opções ou estratégias para resolver um problema. Os algoritmos gulosos escolhem a opção que lhe parece melhor no momento (chamada de escolha ótima ou mais “apetitosa”) e esperam que desta forma cheguem a uma ótima solução global (DORINI e ROCHA, 2004). Apesar de não ser sempre possível encontrar uma solução ótima a partir de um desses algoritmos, eles são bastante eficientes diante de uma diversidade de problemas, conforme será exposto posteriormente.

“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 decisões tomadas, independentemente das consequências” afirmam Dorini e Rocha (2004, p.1), de maneira que não é preciso avaliar as alternativas ou preocupar-se com as decisões anteriores. Eles possuem um nível relativamente fácil de implementação e apresentam eficiência quando funcionam.

2 ALGORITMOS GULOSOS

De acordo com Cormen et al (2002, p.314), algoritmos gulosos funcionam através de passos para resolver problemas relacionados a otimização, sendo que ele sempre fará a escolha que parece ser a melhor no momento, sendo esta ótima para as condições locais. Eles nem sempre produzem soluções ótimas, mas são úteis para muitos problemas.

Segundo Dorini e Rocha (2004) um exemplo simples para o entendimento de um algoritmo guloso pode ser descrito através do “Problema do troco”. Este problema possui a seguinte proposta: suponha que é preciso dar um troco, mas só tenha disponíveis moedas de $100, $25, $10, $5 e $1, e precisa-se criar um algoritmo para utilizar o menor número possível de moedas.

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 (DORINI E ROCHA, 2004, p. 2).

O algoritmo guloso deste exemplo pode não encontrar uma solução ótima, ou mesmo uma solução, se a quantidade de moedas for limitada ou seus valores forem diferentes. A seguir, na Figura 1, pode ser visualizado um algoritmo com proposta de solução para o problema do troco. Este algoritmo “dá o troco” para um valor M usando o menor número possível de moedas.

Figura 1 - Algoritmo para encontrar troco

Fonte: BRASSARD e BRATLEY, 1996.

Este algoritmo pode ser dito guloso, pois a cada passo ele escolhe o maior valor possível, sem refazer suas decisões. Outra estratégia de solução para este problema seria a programação dinâmica, que não será abordada neste trabalho, porém os algoritmos gulosos são mais simples e podem ser mais eficientes em alguns casos (BRASSARD e BRATLEY, 1996, p. 188 ).

De acordo com Brassard e Bratley (1996, p. 188) o algoritmo apresentado é caracterizado como guloso porque a cada passo ele escolhe a maior moeda, sem se preocupar se essa vai ser uma boa decisão ao longo da execução. Além disso, nunca muda a sua escolha: uma vez que uma moeda foi escolhida, será esta até o fim, sendo estas características dos algoritmos gulosos.

2.1 CARACTERÍSTICAS DOS ALGORITMOS GULOSOS

Geralmente, os algoritmos gulosos e seus problemas são resolvidos a partir de uma ou mais características seguintes (BRASSARD e BRATLEY, 1996, p. 189 ):

• Há um problema que precisa ser resolvido de maneira ótima, e, para se chegar a uma solução existem candidatos ou várias escolhas, sendo esta chamada de Lista de Candidatos. No exemplo acima citado, as escolhas possíveis são as moedas com diferentes valores e quantidade suficiente de moedas de cada valor;

• Em sua execução, o algoritmo cria duas listas: uma com os elementos avaliados e rejeitados, e outra com os analisados e escolhidos;

• Existe uma função que confere se um conjunto de opções produz uma solução para o problema, chamada de Função Solução. Neste momento, questões de otimização não estão sendo consideradas. No exemplo, esta função realizaria a verificação entre o valor desejado e o valor das moedas já escolhidos, se estes já são iguais.

• Uma segunda função verifica se um conjunto de opções é viável, ou seja,