O problema com greedy algorithms
A primeira coisa que todo mundo aprende sobre o algoritmo guloso é a definição de livro didático. Escolha localmente a melhor opção a cada passo, sem se preocupar com o futuro. Isso funciona muito bem em teoria. Na prática, você vai tropeçar em casos onde a escolha gulosamente óbvia te leva a uma solução subótima ou até a um resultado completamente errado. Eu construí um sistema de escalonamento de tarefas há uns três anos pra uma operação logística. Precisávamos alocar veículos pra rotas com j... janelas de tempo específicas, capacidades limitadas e custos variáveis. A tentação de usar uma abordagem gulosa era enorme porque era rápida. Implementei, testei, e nos primeiros dias funcionou bem. Até começarmos a ver cases onde o veículo mais próximo sendo escalonado primeiro impedia que dois outros pedidos menores fossem atendidos no mesmo percurso. Perdiam-se ganhos de 18% a 23% na utilização da frota porque a decisão local ignorava o padrão global.
Como funciona o algoritmo guloso na prática
O funcionamento é simples. Você define uma função de seleção que avalia as opções disponíveis num dado momento e escolhe a que parece melhor agora. Depois atualiza o estado do problema e repete até não haver mais opções. O problema é definir essa função de seleção. Se você escolher mal, todo o resto do algoritmo vai pro desenho. Existem dois cenários onde o algoritmo guloso realmente brilha. O primeiro é quando o problema tem a propriedade de escolha gulosa, o que significa que uma decisão local ótima leva necessariamente a uma solução global ótima. O segundo é quando você precisa de uma resposta rápida e aproximada, sabendo que não será perfeita. Em problemas de escalonamento com estruturas de grafo ou árvore, por exemplo, algoritmos como os de Kruskal e Prim garantem optimalidade. Mas fora desses casos, você está lidando com heurística pura.
Um detalhe que poucas pessoas mencionam: o algoritmo guloso precisa de duas propriedades fundamentais pra ser correto. A propriedade de escolha gulosa e a subestrutura ótima. A subestrutura ótima significa que uma solução ótima pro problema contém soluções ótimas pra subproblemas. Sem essas duas, o algoritmo pode produzir resultados aceitáveis, mas você não tem garantia de nada. A maioria dos problemas do mundo real não satisfaz nenhuma das duas.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Casos onde eu acertei e onde eu errei
Depois do fiasco do escalonamento logístico, mudei a estratégia. Em vez de descartar completamente a abordagem gulosa, eu passei a usá-la como primeira fase de um processo maior. Criei um algoritmo que usava uma versão gulosa pra gerar uma solução inicial viável, e depois aplicava uma técnica de melhoria local, tipo troca de vizinhança, pra refinar o resultado. Isso reduziu a perda de eficiência de 18-23% para algo em torno de 4-6%, o que era perfeitamente aceitável pra operação. Outro caso interessante foi com compactação de dados. Algoritmo de Huffman é puramente guloso e funciona perfeitamente porque o problema satisfaz ambas as propriedades. A cada iteração, você combina os dois nós de menor frequência disponíveis. É elegante, é eficiente, e produz árvores de codificação ótimo. Foi um dos raros momentos em que a ganância realmente compensa.
Problemas de mochila fracionária também se resolvem naturalmente com greedy. Você calcula o valor por unidade de peso de cada item e vai colocando até a mochila encher. A complexidade é O(n log n) devido à ordenação. Mas se o problema for de mochila 0/1, onde você não pode fracionar itens, o mesmo approach falha miseravelmente. Já vi gente implementar isso em produção achando que ia funcionar. Funciona em 40% dos casos, no máximo. O resto é pura sorte.
O que você precisa verificar antes de aplicar
Antes de implementar qualquer algoritmo guloso, pergunte-se: existe uma prova de corretude? Não precisa ser formal, mas pelo menos você precisa conseguir argumentar por que a escolha local leva ao resultado global. Se não conseguir, provavelmente está criando um bug disfarçado de otimização. Outra coisa: entenda a complexidade temporal. Uma classificação gulosa típica custa O(n log n) porque a ordenação domina. Mas existem casos onde a função de seleção é complexa o suficiente pra tornar o algoritmo mais lento do que uma programação dinâmica equivalente. Já passei por isso com um problema de agendamento de manutenção industrial onde a função de custo local envolvia simulações de Monte Carlo. Cada iteração do greedy levava minutos. No final, a programação dinâmica com memoização foi duas vezes mais rápida no total, apesar da complexidade teórica pior.
Também vale a pena testar contra uma solução exata em instâncias pequenas. Se você tem um dataset de teste com 50 a 100 instâncias, rode o algoritmo guloso e compare com um solver de programação inteira ou com enumeração completa. Anote a diferença de qualidade e o tempo de execução. Isso te dá uma noção realista do trade-off antes de colocar em produção. A abordagem gulosa é uma ferramenta válida no conjunto. O problema é quando as pessoas tratam ela como solução universal porque é fácil de implementar e rápida de rodar. Eu vejo isso constantemente. Alguém implementa um greedy em uma tarde, acha que resolvedo, e só descobre seis meses depois que o sistema está produzindo resultados sistematicamente piores do que deveriam. A lição é: use greedy quando o problema permitir, valide quando não permitir, e nunca confie cegamente na escolha local.
