Algoritmos Gulosos¶

Um algoritmo guloso constrói uma solução comprometendo-se com uma escolha localmente preferível sem revisitá-la. Isso funciona apenas quando o problema possui uma propriedade adequada de troca ou dominância.

Escalonamento de intervalos¶

Dadas atividades com horários de início e término, selecione o maior subconjunto sem sobreposições. Escolher uma atividade compatível que termine primeiro é ótimo.

Argumento de troca: considere qualquer escalonamento ótimo. Sua primeira atividade não pode terminar antes da primeira atividade escolhida pelo algoritmo guloso. Substituí-la pela escolha gulosa preserva a viabilidade e o número de atividades escalonadas. Aplique o mesmo argumento às atividades compatíveis restantes.

Após a ordenação pelo horário de término, a seleção é linear; portanto, o tempo total é Θ(n log n), e o espaço adicional da seleção é Θ(1), sem contar a saída.

Quando a estratégia gulosa falha¶

Escolher o item de maior valor imediato não resolve o problema da mochila 0/1 em geral. Uma escolha local pode consumir a capacidade necessária para uma combinação melhor. A mochila fracionária possui outra estrutura e admite uma solução gulosa por densidade de valor.

Padrões de prova¶

trocar a primeira divergência de uma solução ótima pela escolha gulosa;
mostrar que a solução gulosa permanece pelo menos tão adiantada a cada etapa;
modelar os conjuntos viáveis com uma estrutura como um matroide.

Exercícios¶

Dê um contraexemplo para a escolha da atividade mais curta primeiro.
Prove a escolha de aresta segura de Kruskal usando cortes do grafo.
Explique por que pesos de aresta não negativos são necessários à etapa gulosa de Dijkstra.