Algoritmos Gulosos

Em diversos casos da vida, a noção de ganho é dúbia. Não é possível saber se uma solução encontrada é de fato a melhor. A única coisa que pode ser feita é garantir o ganho de pequenas conquistas para ter uma esperança de uma melhor resolução.

Após esse monólogo, o ponto que quero chegar é: a relação custo-benefício de determinada resolução.

Muitas vezes, apesar do senso comum, nem sempre uma solução otimizada é de fato a melhor, às vezes a solução em questão pode produzir uma vitória pírrica, isto é, quando o custo de fazer algo excede seu resultado. Esse termo pode ser usado em tudo na vida, inclusive na hora de desenvolver um projeto, independente da área.

Algoritmos Guloso

Os algoritmos gulosos tentam resolver o problema fazendo a escolha localmente ótima em cada fase com a esperança de encontrar um ótimo global. Esses algoritmos enxergam apenas um passo de cada vez ao invés de se concentrar no todo. As duas premissas principal deste algoritmo são: 

• Sempre procurar a solução ideal em um dado passo
• E executar o passo.

Você pode encontrar diversos algoritmos gananciosos na internet, que vão desde análise de gráficos, como o Kruskal’s Minimum Spanning Tree(MST), que traça o menor caminho entre dois pontos num gráfico, e algoritmos de compressão de dados, como o Huffman Encoding.

Por que nem sempre a solução mais otimizada nem sempre é melhor?

Cientistas e matemáticos usam esses algoritmos com uma certa frequência, porém nem sempre é conveniente usá-los. Apesar da premissa de escolha ótima descrita na Wikipédia. Normalmente as pessoas estão em busca de uma boa solução, que normalmente fornece resultados mensuráveis, e não necessariamente de uma solução específica. Antes de aplicar qualquer solução, você tem que ter certeza do problema ser resolvido, para que consiga sempre economizar recursos, até porque o tempo e dinheiro normalmente são limitados.

Contextualizando, digamos que você crie uma máquina que reduza um número ao valor mínimo de cédulas usando os valores 25, 10, 5 e 1. 

Num algoritmo guloso, um valor 16 poderia ser reduzido a três cédulas de 10, 5 e 1, o que poderia ser o melhor resultado. Porém, caso o número a ser reduzido fosse 40, e não houvesse cédulas de 5 seriam necessárias cédulas de 25, 10 e 5 de 1, sendo que nesse caso, seria melhor o uso de 4 cédula de 10.

Então a conclusão que pode ser tirada é que nem sempre a solução mais otimizada é a melhor.

OBS: Este artigo foi baseado de um livro que estou lendo atualmente, inclusive o exemplo da máquina. Então, caso eu tenha errado em algo, agradeço o feedback da comunidade : ).