O que são algoritmos gulosos e quando funcionam?

Question

Accepted Answer

Um **algoritmo guloso** faz a **escolha localmente ótima** em cada passo, esperando que leve a um ótimo global. É simples e rápido, mas apenas correto quando o problema tem a **propriedade da escolha gulosa** e **subestrutura ótima**.

## A ideia

Nunca reconsidere escolhas passadas — comprometa-se com a melhor opção imediata e siga adiante.

## Exemplo: troco com moedas canônicas

```python
def greedy_coins(amount, coins=(25, 10, 5, 1)):
    result = []
    for coin in coins:                 # largest first
        while amount >= coin:
            amount -= coin             # take as many as possible
            result.append(coin)
    return result

greedy_coins(36)                       # -> [25, 10, 1]
```

Isto é ótimo para moedas dos EUA, mas **falha** para conjuntos como {1, 3, 4} onde ganancioso dá 4+1+1 para 6 em vez de 3+3.

## Quando guloso funciona

- **Subestrutura ótima:** uma solução ótima contém sub-soluções ótimas.
- **Propriedade da escolha gulosa:** um ótimo local faz parte de um ótimo global.

Exemplos que funcionam: Dijkstra, Kruskal/Prim (MST), codificação de Huffman, agendamento de intervalos.

## Complexidade

Usualmente rápido — frequentemente O(n log n) após ordenação.

## Armadilhas

Guloso **nem sempre é correto**. Prove a propriedade da escolha gulosa ou teste contra um baseline de força bruta/DP antes de confiar nela.

## Por que isso importa

Quando guloso se aplica, é muito mais simples e rápido que DP ou força bruta.

Saber *quando* é válido — e quando silenciosamente dá respostas erradas — é uma marca de maturidade algorítmica.

Muitos algoritmos de grafos fundamentais são gulosos no seu cerne.