Algoritmos

Técnica de Programação III

São Paulo
2013

Algoritmos Gulosos

Introdução

De forma geral, os algoritmos relacionados com optimização lidam com uma sequencia de passos, sendo que em cada passo há um conjunto de escolhas/opções. Uma estratégia para resolver problemas de optimização são os algoritmos gulosos, os quais 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ências. 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.

Algoritmos Gulosos
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 100, 25, 10, 5 e 1. O problema é criar um algoritmo que para conseguir obter um determinado valor com o menor número 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, ´e verdade que com os valores dados das