Neste tutorial, você aprenderá o que é um Algoritmo Greedy. Além disso, você encontrará um exemplo de abordagem gananciosa.
Um algoritmo guloso é uma abordagem para resolver um problema selecionando a melhor opção disponível no momento, sem se preocupar com o resultado futuro que ela traria. Em outras palavras, as melhores escolhas localmente visam produzir os melhores resultados globalmente.
Este algoritmo pode não ser a melhor opção para todos os problemas. Em alguns casos, pode produzir resultados errados.
Este algoritmo nunca volta para reverter a decisão tomada. Este algoritmo funciona em uma abordagem de cima para baixo.
A principal vantagem deste algoritmo é:
- O algoritmo é mais fácil de descrever .
- Este algoritmo pode funcionar melhor do que outros algoritmos (mas não em todos os casos).
Solução viável
Uma solução viável é aquela que fornece a solução ótima para o problema.
Algoritmo ganancioso
- Para começar, o conjunto de soluções (contendo respostas) está vazio.
- Em cada etapa, um item é adicionado ao conjunto de soluções.
- Se o conjunto de soluções for viável, o item atual é mantido.
- Caso contrário, o item é rejeitado e nunca mais considerado.
Exemplo - abordagem gananciosa
Problema: Você deve fazer uma alteração de um valor usando o menor número possível de moedas. Quantidade: $ 28 Moedas disponíveis: $ 5 moedas $ 2 moedas $ 1 moeda
Solução:
- Crie um conjunto de solução vazio = ().
- moedas = (5, 2, 1)
- soma = 0
- Enquanto soma ≠ 28, faça o seguinte.
- Selecione uma moeda C entre as moedas que somam + C <28.
- Se C + soma> 28, não retorna nenhuma solução.
- Caso contrário, soma = soma + C.
- Adicione C ao conjunto de soluções.
Até as 5 primeiras iterações, o conjunto de soluções contém 5 moedas de $ 5. Depois disso, temos 1 moeda de $ 2 e, finalmente, 1 moeda de $ 1.
Aplicações de algoritmo ganancioso
- Ordem de Seleção
- Problema da mochila
- Árvore de alcance mínimo
- Problema de caminho mais curto de fonte única
- Problema de programação de trabalho
- Algoritmo de árvore de expansão mínima de Prim
- Algoritmo de árvore de expansão mínima de Kruskal
- Algoritmo de árvore de expansão mínima de Dijkstra
- Codificação Huffman
- Algoritmo Ford-Fulkerson