O que você precisa saber antes de escrever qualquer coisa
A primeira coisa que todo mundo aprende sobre o algoritmo guloso é que ele escolhe a melhor opção local em cada passo. Isso parece simples, mas a parte difícil não é implementar, é saber quando ele funciona e quando ele vai te entregar uma resposta errada. Eu passei muito tempo tentando encaixar esse tipo de abordagem em problemas onde ela simplesmente não se aplicava.
algoritmo guloso na prática
Na prática, um algoritmo guloso funciona assim: você tem um problema de otimização, seja maximizar ou minimizar algo, e em cada etapa você faz a escolha que parece melhor no momento, sem olhar para trás. A decisão é irrevogável. Você não volta, não recalcula, não reconsidera. Cada escolha é final. O problema é que essa definição sozinha não diz se o resultado vai ser ótimo ou apenas razoável. A diferença entre os dois casos é enorme e normalmente aparece só depois que você já perdeu horas debugando.
Eu tive um caso bem específico com um problema de escalonamento de tarefas. O cenário era o seguinte: tínhamos um conjunto de jobs com tempos de execução e deadlines, e precisávamos maximizar o número de jobs concluídos antes do prazo. A versão ingênua seria sortear ou usar força bruta. O que eu fiz foi aplicar um algoritmo guloso clássico que ordena os jobs pelo menor deadline primeiro e vai agendando sequencialmente. Funcionou perfeitamente nos testes unitários. Quando coloquei em produção, comecei a receber reclamações de jobs being missed em cenários onde os deadlines vinham com float de precisão, não inteiros. O workaround foi converter todos os deadlines para microssegundos usando floor antes da comparação, porque a ordem relativa de jobs com deadlines próximos a ponto flutuante ficava instável dependendo da plataforma. Esse detalhe passa despercebido em qualquer material introdutório.
Quando o algoritmo guloso realmente funciona
Nem todo problema de otimização se presta a uma abordagem gulosa. Para que ela produza o ótimo global, o problema precisa satisfazer duas propriedades: a propriedade da escolha gulosa e a subestrutura ótima. A propriedade da escolha gulosa significa que uma solução ótima global pode ser construída fazendo a escolha localmente ótima em cada passo. A subestrutura ótima significa que, depois de fazer essa escolha, o problema restante ainda é um problema do mesmo tipo, só que menor. Se uma dessas propriedades não vale, o algoritmo guloso vai te dar uma resposta subótima e você vai gastar tempo achando que está errado por causa de um bug.
Problemas clássicos onde o algoritmo guloso funciona incluem o problema da mochila fracionária, a árvore geradora mínima de Kruskal e Prim, e o caminho mais curto de Dijkstra. Nestes casos, a prova de correção envolve mostrar que nenhuma escolha alternativa poderia levar a um resultado melhor. Por outro lado, problemas como o problema da mochila 0-1, o caixeiro viajante geral e o problema da cobertura de vértices não têm essa garantia. Para eles, você precisa recorrer a programação dinâmica, branch and bound, ou aproximações com fator conhecido.
👉 Clique no botão abaixo para saber mais sobre o assunto!
Implementação básica e armadilhas comuns
Uma implementação típica de um algoritmo guloso segue quatro etapas: definir a função de seleção que decide qual candidato escolher no passo atual, garantir que o candidato seja viável, verificar se a solução está completa e, se necessário, extrair a solução encontrada. A etapa mais crítica é a função de seleção. Ela precisa ser definida com cuidado porque é ela que determina a ordem das escolhas. Trocar a heurística de seleção é o que diferencia um algoritmo guloso que dá o ótimo de um que dá algo completamente fora.
Um erro comum é assumir que a ordem natural dos dados já é a ordem correta. Em muitos problemas, o que importa é a ordenação por uma métrica secundária, como densidade de valor por peso no caso de mochila fracionária, ou o tempo de término no caso de escalonamento. Outro erro frequente é esquecer de lidar com empates. Quando dois candidatos têm o mesmo valor segundo a função de seleção, a ordem entre eles pode fazer diferença no resultado final. Em alguns casos, o desempate por índice original preserva a estabilidade. Em outros, precisa-se de uma regra adicional.
Em termos de complexidade, a parte de ordenação geralmente domina. Um algoritmo guloso que requer ordenação prévia tem complexidade O(n log n). A seleção em si costuma ser linear ou linear-logarítmica dependendo da estrutura de dados usada, como heap ou árvore balanceada.
Um exemplo concreto
Vamos pegar o problema do troco. Você precisa devolver um troco usando o menor número possível de notas e moedas. Se o sistema monetário for canônico, como o real ou o dólar, o algoritmo guloso funciona perfeitamente: sempre pegue a maior denominação possível e repita. Para um troco de R$ 87,43, você pega uma nota de 50, uma de 20, uma de 10, uma de 5, uma de 2, uma de 0,40 e uma de 0,03. Sete moedas e notas. Não tem jeito melhor. Mas se o sistema monetário fosse arbitrário, digamos com denominações de 1, 3 e 4, o algoritmo guloso falharia. Para um valor de 6, o guloso pegaria 4 mais 1 mais 1, três unidades. A solução ótima seria 3 mais 3, apenas duas unidades. Isso mostra que a estrutura do problema é que determina a validade da escolha gulosa, não a engenhosidade da implementação.
O que ninguém conta sobre limite de aplicação
O maior problema do algoritmo guloso não é a implementação, é a convicção errada de que ele se aplica a tudo. Eu já vi gente tentar resolver problemas de scheduling com recursos limitados usando guloso puro e gastar dias tentando ajustar a função de seleção quando a resposta certa seria uma programação dinâmica com estado exponencial ou uma relaxação Lagrangeana. Se o seu problema tem dependências entre as escolhas — ou seja, a decisão atual restringe opções futuras de forma não trivial — o algoritmo guloso provavelmente não é a ferramenta certa. Nesses casos, a abordagem correta envolve explorar o espaço de soluções de forma mais sistemática.
Existe também a questão dos algoritmos de aproximação. Em problemas NP-difíceis onde oguloso não dá a solução exata, ele ainda pode ser usado como heurística com garantias de aproximação conhecidas. O algoritmo guloso para cobertura de conjuntos, por exemplo, tem fator de aproximação de H_n, onde H_n é o n-ésimo número harmônico. Isso significa que a solução gulosa é no pior caso log n vezes pior que a ótima. Para muitos casos práticos, esse fator é perfeitamente aceitável, mas é bom saber exatamente o quanto você está abrindo mão. Se você está começando a estudar o tema, a recomendação é simples: resolva os problemas clássicos primeiro, decore os contraexemplos, e antes de usar uma abordagem gulosa, pergunte-se se as duas propriedades fundamentais realmente valem para o seu caso. Se não tiver certeza, teste em instâncias pequenas contra uma solução exata e compare os resultados. A diferença aparece rápido.
