Lançado · em melhoria
Algorithm
Algoritmos gulosos fazem a melhor escolha local a cada passo, sem voltar atrás, e resolvem rápido o agendamento de intervalos, Huffman e a mochila fracionária.
Um algoritmo guloso (greedy) constrói a solução por meio de uma sequência de decisões: a cada passo, escolhe o candidato que parece melhor segundo uma regra fixa e nunca revê essa decisão. A maioria ordena os candidatos ou os coloca em uma fila de prioridade e os aceita um a um, então o código é curto e o tempo de execução costuma ser O(n log n), dominado pela ordenação ou pelas operações de heap.
Quando funciona, a abordagem gulosa é a solução mais rápida e simples, mas nem sempre funciona. Para garantir o ótimo, é preciso ter a propriedade da escolha gulosa e subestrutura ótima, o que geralmente se prova com um argumento de troca. Basta um contraexemplo, como formar 6 com moedas de 1, 3 e 4, para saber que é preciso usar programação dinâmica. O princípio guloso também está no centro de algoritmos muito usados, como a codificação de Huffman, os caminhos mínimos de Dijkstra e as árvores geradoras mínimas.
Comece pelo agendamento de intervalos (seleção de atividades) e explique com um argumento de troca por que escolher a reunião que termina primeiro é correto. Depois implemente a codificação de Huffman, a mochila fracionária e a alocação de salas com heap, e crie o hábito de comparar seus resultados gulosos com uma busca exaustiva em entradas pequenas: é o jeito mais rápido de identificar uma regra errada em entrevistas de programação.
Precisa existir uma solução ótima que contenha a primeira escolha gulosa; essa é a condição central para a correção.
Mostra-se que qualquer solução ótima pode ser transformada, elemento a elemento, na solução gulosa sem piorar.
Os candidatos são ordenados por horário de término, valor por peso ou frequência, ou retirados de um heap, por isso o custo costuma ser O(n log n).
Com sistemas de moedas arbitrários ou na mochila 0/1, a regra gulosa erra e é preciso recorrer à programação dinâmica.
O programa escolhe o maior conjunto de reuniões que não se sobrepõem. Ele ordena as reuniões pelo horário de término e só aceita uma reunião se ela começar depois do fim da última escolhida. A ordenação custa O(n log n) e a varredura O(n); no exemplo, 4 das 11 reuniões são escolhidas.
greedy.py
def select_intervals(intervals):
"""Return a maximum set of non-overlapping half-open intervals [start, end)."""
chosen = []
last_end = float("-inf")
for start, end in sorted(intervals, key=lambda iv: iv[1]): # earliest end first
if start >= last_end:
chosen.append((start, end))
last_end = end
return chosen
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(select_intervals(meetings)) # [(1, 4), (5, 7), (8, 11), (12, 16)]
python greedy.pySeis capítulos que levam você da instalação aos conceitos essenciais de Algoritmos gulosos.
Tire dúvidas, compartilhe experiências e troque opiniões sobre Algoritmos gulosos.
Ainda não há discussões. Comece a primeira.
0 comentários
Fazer login · Faça login para deixar um comentário.
Seja o primeiro a comentar.