Algoritmo ganancioso - Greedy algorithm

Algoritmos gananciosos determinam o número mínimo de moedas a serem dadas durante o troco. Essas são as etapas que a maioria das pessoas executaria para emular um algoritmo ganancioso para representar 36 centavos usando apenas moedas com valores {1, 5, 10, 20}. A moeda de maior valor, menor do que o troco restante devido, é o ótimo local. (Em geral, o problema de fazer mudanças requer uma programação dinâmica para encontrar uma solução ótima; no entanto, a maioria dos sistemas monetários, incluindo o Euro e o dólar americano, são casos especiais em que a estratégia gananciosa encontra uma solução ótima.)

Um algoritmo guloso é qualquer algoritmo que segue a heurística de resolução de problemas de fazer a escolha localmente ideal em cada estágio. Em muitos problemas, uma estratégia gulosa não produz uma solução ótima, mas uma heurística gulosa pode produzir soluções localmente ótimas que se aproximam de uma solução globalmente ótima em um período de tempo razoável.

Por exemplo, uma estratégia gananciosa para o problema do caixeiro viajante (que é de alta complexidade computacional) é a seguinte heurística: "Em cada etapa da jornada, visite a cidade não visitada mais próxima." Essa heurística não pretende encontrar a melhor solução, mas termina em um número razoável de etapas; encontrar uma solução ótima para um problema tão complexo normalmente requer muitas etapas injustificáveis. Na otimização matemática, os algoritmos gulosos resolvem de forma otimizada problemas combinatórios com propriedades de matróides e fornecem aproximações de fator constante para problemas de otimização com a estrutura submodular.

Especificidades

Em geral, algoritmos gulosos têm cinco componentes:

1. Um conjunto de candidatos, a partir do qual uma solução é criada
2. Uma função de seleção, que escolhe o melhor candidato a ser adicionado à solução
3. Uma função de viabilidade, que é usada para determinar se um candidato pode ser usado para contribuir para uma solução
4. Uma função objetivo, que atribui um valor a uma solução, ou uma solução parcial, e
5. Uma função de solução, que indicará quando descobrimos uma solução completa

Algoritmos gananciosos produzem boas soluções para alguns problemas matemáticos , mas não para outros. A maioria dos problemas para os quais trabalham terá duas propriedades:

Propriedade de escolha gananciosa

Podemos fazer qualquer escolha que pareça melhor no momento e então resolver os subproblemas que surgirem mais tarde. A escolha feita por um algoritmo guloso pode depender das escolhas feitas até agora, mas não de escolhas futuras ou de todas as soluções para o subproblema. Ele faz iterativamente uma escolha gananciosa após a outra, reduzindo cada problema em um menor. Em outras palavras, um algoritmo ganancioso nunca reconsidera suas escolhas. Esta é a principal diferença da programação dinâmica , que é exaustiva e com garantia de encontrar a solução. Após cada estágio, a programação dinâmica toma decisões com base em todas as decisões tomadas no estágio anterior e pode reconsiderar o caminho algorítmico do estágio anterior para a solução.

Subestrutura ótima

"Um problema exibe uma subestrutura ótima se uma solução ótima para o problema contém soluções ótimas para os subproblemas."

Casos de insucesso

Exemplos de como um algoritmo guloso pode falhar em alcançar a solução ideal.

Partindo de A, um algoritmo ganancioso que tenta encontrar o máximo seguindo a maior inclinação encontrará o máximo local em "m", esquecido do máximo global em "M".

Para atingir a maior soma, em cada etapa, o algoritmo guloso escolherá o que parece ser a escolha imediata ótima, então ele escolherá 12 em vez de 3 na segunda etapa, e não alcançará a melhor solução, que contém 99.

Algoritmos gananciosos falham em produzir a solução ótima para muitos outros problemas e podem até produzir a pior solução possível . Um exemplo é o problema do caixeiro viajante mencionado acima: para cada número de cidades, há uma atribuição de distâncias entre as cidades para as quais a heurística do vizinho mais próximo produz o pior trajeto único possível. Para outros exemplos possíveis, consulte efeito horizonte .

Tipos

Algoritmos gananciosos podem ser caracterizados como 'míopes' e também como 'irrecuperáveis. Eles são ideais apenas para problemas que possuem uma 'subestrutura ideal'. Apesar disso, para muitos problemas simples, os algoritmos mais adequados são gananciosos. É importante, no entanto, observar que o algoritmo guloso pode ser usado como um algoritmo de seleção para priorizar opções dentro de uma pesquisa ou algoritmo de ramificação e limite. Existem algumas variações para o algoritmo ganancioso:

• Algoritmos puramente gananciosos
• Algoritmos gulosos ortogonais
• Algoritmos gananciosos relaxados

Teoria

Algoritmos gananciosos têm uma longa história de estudo em otimização combinatória e ciência da computação teórica . Heurísticas gananciosas são conhecidas por produzir resultados abaixo do ideal em muitos problemas e, portanto, as questões naturais são:

• Para quais problemas os algoritmos gulosos têm um desempenho ideal?
• Para quais problemas os algoritmos gulosos garantem uma solução aproximadamente ótima?
• Para quais problemas o algoritmo guloso tem garantia de não produzir uma solução ótima?

Existe uma grande quantidade de literatura respondendo a essas questões para classes gerais de problemas, como matróides , bem como para problemas específicos, como cobertura de conjuntos .

Matroids

Um matróide é uma estrutura matemática que generaliza a noção de independência linear de espaços vetoriais para conjuntos arbitrários. Se um problema de otimização tem a estrutura de uma matróide, então o algoritmo guloso apropriado irá resolvê-lo de forma otimizada.

Funções submodulares

Uma função definida em subconjuntos de um conjunto é chamada de submodular se para cada nós a tivermos . ${\ displaystyle f}$${\ displaystyle \ Omega}$${\ displaystyle S, T \ subseteq \ Omega}$${\ displaystyle f (S) + f (T) \ geq f (S \ cup T) + f (S \ cap T)}$

Suponha que se queira encontrar um conjunto que maximize . O algoritmo guloso, que constrói um conjunto adicionando incrementalmente o elemento que mais aumenta a cada etapa, produz como saída um conjunto que é no mínimo . Ou seja, o greedy tem um desempenho dentro de um fator constante tão bom quanto a solução ideal. ${\ displaystyle S}$${\ displaystyle f}$${\ displaystyle S}$${\ displaystyle f}$${\ displaystyle (1-1 / e) \ max _ {X \ subseteq \ Omega} f (X)}$${\ displaystyle (1-1 / e) \ aprox. 0,63}$

Garantias semelhantes podem ser provadas quando restrições adicionais, como restrições de cardinalidade, são impostas na saída, embora muitas vezes pequenas variações no algoritmo guloso sejam necessárias. Veja para uma visão geral.

Outros problemas com garantias

Outros problemas para os quais o algoritmo guloso dá uma forte garantia, mas não uma solução ótima, incluem

• Definir capa
• O problema da árvore Steiner
• Balanceamento de carga
• Conjunto independente

Muitos desses problemas têm limites inferiores correspondentes; ou seja, o algoritmo guloso não tem um desempenho melhor do que a garantia no pior caso.

Formulários

Os algoritmos gananciosos normalmente (mas nem sempre) falham em encontrar a solução globalmente ideal porque geralmente não operam exaustivamente em todos os dados. Eles podem se comprometer com certas escolhas muito cedo, impedindo-os de encontrar a melhor solução geral mais tarde. Por exemplo, todos os algoritmos de coloração gulosos conhecidos para o problema de coloração de grafos e todos os outros problemas NP-completos não encontram consistentemente soluções ótimas. No entanto, eles são úteis porque são rápidos para pensar e freqüentemente fornecem boas aproximações para o ótimo.

Se for possível provar que um algoritmo guloso produz o ótimo global para uma determinada classe de problema, ele normalmente se torna o método de escolha porque é mais rápido do que outros métodos de otimização, como a programação dinâmica . Exemplos de tais algoritmos gulosos são o algoritmo de Kruskal e algoritmo de Prim para encontrar árvore de extensão mínima e o algoritmo para encontrar melhores árvores Huffman .

Algoritmos gananciosos também aparecem no roteamento da rede . Usando o roteamento ganancioso, uma mensagem é encaminhada ao nó vizinho que está "mais próximo" do destino. A noção de localização de um nó (e, portanto, "proximidade") pode ser determinada por sua localização física, como no roteamento geográfico usado por redes ad hoc . A localização também pode ser uma construção inteiramente artificial, como no roteamento de pequenos mundos e na tabela de hash distribuída .

Exemplos

• O problema de seleção de atividades é característico dessa classe de problemas, em que o objetivo é escolher o número máximo de atividades que não conflitem entre si.
• No jogo de computador para Macintosh Crystal Quest, o objetivo é coletar cristais, de forma semelhante ao problema do caixeiro viajante . O jogo tem um modo de demonstração, onde o jogo usa um algoritmo ganancioso para ir a cada cristal. A inteligência artificial não leva em conta os obstáculos, então o modo de demonstração geralmente termina rapidamente.
• A busca de correspondência é um exemplo de algoritmo guloso aplicado na aproximação do sinal.
• Um algoritmo ganancioso encontra a solução ótima para o problema de Malfatti de encontrar três círculos disjuntos dentro de um determinado triângulo que maximizam a área total dos círculos; conjectura-se que o mesmo algoritmo ganancioso é ótimo para qualquer número de círculos.
• Um algoritmo guloso é usado para construir uma árvore de Huffman durante a codificação de Huffman, onde encontra uma solução ótima.
• No aprendizado de árvore de decisão , algoritmos gulosos são comumente usados, no entanto, não é garantido que eles encontrem a solução ótima.
  • Um algoritmo popular é o algoritmo ID3 para construção de árvore de decisão.
• O algoritmo de Dijkstra e o algoritmo de pesquisa A * relacionado são algoritmos gulosos verificáveis ​​e ótimos para pesquisa de gráfico e localização do caminho mais curto .
  • Uma * pesquisa é condicionalmente ótima, exigindo uma " heurística admissível " que não superestime os custos do caminho.
• Algoritmo de Kruskal e algoritmo de prim são algoritmos gulosos para a construção de árvore de extensão mínima de um dado grafo conexo . Eles sempre encontram uma solução ótima, que pode não ser única em geral.

Veja também

Referências

Fontes

links externos

• "Greedy algorithm" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Presente, Noah. "Exemplo de moeda gananciosa do Python" .