Algoritmos Gulosos

Algoritmos gulosos constroem uma solução incrementalmente, fazendo repetidamente a escolha que parece melhor na etapa atual, e estão corretos precisamente quando tais escolhas localmente ótimas comprovadamente levam a uma solução globalmente ótima.

Definition

Um algoritmo guloso constrói uma solução através de uma sequência de escolhas, cada uma selecionada para otimizar algum critério local, nunca revisitando escolhas anteriores; ele está correto apenas quando as escolhas localmente ótimas produzem um resultado globalmente ótimo.

Scope

Este tópico abrange o paradigma guloso: a propriedade da escolha gulosa e a subestrutura ótima que a justificam, as técnicas de prova padrão (argumentos de troca e o arcabouço de matróides), e algoritmos gulosos canônicos, incluindo codificação de Huffman, árvores geradoras mínimas (Kruskal e Prim), caminhos mais curtos de Dijkstra e escalonamento de intervalos. Também aborda quando as estratégias gulosas servem apenas como heurísticas de aproximação, em vez de métodos exatos.

Core questions

• O que é a propriedade da escolha gulosa e como ela é provada para um dado problema?
• Como um argumento de troca demonstra que uma escolha gulosa é segura?
• Quais problemas possuem estrutura de matróide que garante a otimalidade gulosa?
• Quando um método guloso é apenas uma aproximação em vez de um algoritmo exato?
• Como o método guloso se compara à programação dinâmica para o mesmo problema?

Key concepts

• propriedade da escolha gulosa
• subestrutura ótima
• argumento de troca
• matróides
• codificação de Huffman
• árvore geradora mínima
• escalonamento de intervalos
• problema da mochila fracionária

Key theories

Propriedade da escolha gulosa e argumentos de troca

Um problema admite uma solução gulosa quando uma solução globalmente ótima pode sempre ser modificada para concordar com a primeira escolha gulosa sem perda de otimalidade; argumentos de troca (ou 'guloso permanece à frente') formalizam isso.

Matróides e otimalidade gulosa

Quando as soluções viáveis formam os conjuntos independentes de um matróide ponderado, o algoritmo guloso sempre encontra um conjunto independente de peso máximo; isso unifica resultados como a otimalidade do algoritmo de árvore geradora mínima de Kruskal.

Clinical relevance

Algoritmos gulosos impulsionam sistemas amplamente utilizados: codificação de Huffman em formatos de compressão de dados, algoritmos de árvore geradora mínima em projeto de redes, algoritmo de Dijkstra em roteamento e navegação, e heurísticas de escalonamento guloso e cobertura de conjuntos em sistemas operacionais e alocação de recursos.

History

O raciocínio guloso aparece em resultados clássicos como os algoritmos de árvore geradora mínima de Kruskal (1956) e Prim (1957), os códigos de prefixo ótimos de Huffman (1952) e o algoritmo de caminho mais curto de Dijkstra (1959). A explicação teórica de matróides sobre quando os métodos gulosos são bem-sucedidos foi desenvolvida por Edmonds e outros nas décadas de 1960 e 1970.

Key figures

• David A. Huffman
• Joseph Kruskal
• Robert Prim
• Edsger W. Dijkstra

Seminal works

• dijkstra1959
• cormen2009

Frequently asked questions

Por que o algoritmo guloso funciona para o problema da mochila fracionária, mas não para o problema da mochila 0/1?

No problema da mochila fracionária, os itens podem ser divididos, então pegar o item de maior valor por peso primeiro é sempre seguro e comprovadamente ótimo. No problema da mochila 0/1, os itens são indivisíveis, a escolha gulosa pode impedir uma combinação melhor, e a programação dinâmica é necessária para um ótimo exato.

Como se prova que um algoritmo guloso está correto?

As duas técnicas padrão são o argumento de troca, que transforma qualquer solução ótima na solução gulosa sem piorá-la, e o argumento 'guloso permanece à frente', que mostra que a solução parcial gulosa é pelo menos tão boa quanto qualquer outra em cada etapa. A teoria dos matróides fornece uma condição geral suficiente.