Algoritmos Gulosos
O que torna um algoritmo ganancioso?
Um algoritmo ganancioso constrói uma solução um passo de cada vez, sempre escolhendo a opção que parece melhor agora - sem reconsiderar escolhas anteriores. Sem retrocesso, sem olhar para frente.
Funciona quando duas propriedades são válidas:
- Propriedade de escolha gananciosa - uma escolha localmente ótima leva a uma solução globalmente ótima.
- Subestrutura ótima - o problema restante após cada escolha é uma instância menor do mesmo problema.
Seleção de atividades - o exemplo clássico
Dado um conjunto de atividades com horários de início e término, selecione o número máximo de atividades não sobrepostas.
Estratégia gananciosa: classifique por horário de término, sempre escolha a atividade que termina mais cedo.
def max_activities(intervals):
intervals.sort(key=lambda x: x[1])
count, end = 0, 0
for s, e in intervals:
if s >= end:
count += 1
end = e
return count
Por que isso funciona? Escolher a atividade que termina mais cedo deixa mais espaço para atividades futuras. Nenhuma outra escolha pode fazer melhor.
Codificação Huffman - Conceito
Crie um código binário ideal sem prefixo mesclando repetidamente os dois símbolos de frequência mais baixa. Isso é ganancioso: a cada passo, junte o par mais barato. O resultado é uma árvore onde símbolos frequentes recebem códigos curtos.
Jogo de salto
Dado um array onde nums[i] é o comprimento máximo do salto do índice i, determine se você pode alcançar o último índice.
Abordagem gananciosa: rastreie o índice mais distante acessível até o momento. Digitalize da esquerda para a direita - se você ficar para trás, retorne falso.
def can_jump(nums):
farthest = 0
for i, jump in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + jump)
return True
Discussão
Entrar participar da discussão