24 de Março
Greedy
O que greedy significa, quando a melhor escolha local ajuda a chegar na resposta certa e por que isso nem sempre funciona.
O que e
Greedy e uma estratégia que escolhe o melhor passo aparente agora.
A aposta e que essa escolha local vai levar a uma boa resposta global.
Quando usar
Ela aparece quando:
- a decisão atual pode ser tomada sem olhar todas as combinações futuras
- o problema tem estrutura que valida essa escolha local
Erro comum
O erro clássico e achar que greedy e atalho universal.
Muita gente tenta usar greedy onde o problema na verdade pede DP, busca ou backtracking.
Pergunta melhor
Antes de aplicar, vale perguntar:
- por que a melhor escolha local continua segura depois?
- existe contraexemplo pequeno que quebra essa intuição?
- eu consigo justificar a escolha ou só estou torcendo?
Compartilhar esta página
Copie o link manualmente no campo abaixo.