Algoritmo ganancioso

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 é:

  1. O algoritmo é mais fácil de descrever .
  2. 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

  1. Para começar, o conjunto de soluções (contendo respostas) está vazio.
  2. Em cada etapa, um item é adicionado ao conjunto de soluções.
  3. Se o conjunto de soluções for viável, o item atual é mantido.
  4. 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:

  1. Crie um conjunto de solução vazio = ().
  2. moedas = (5, 2, 1)
  3. soma = 0
  4. Enquanto soma ≠ 28, faça o seguinte.
  5. Selecione uma moeda C entre as moedas que somam + C <28.
  6. Se C + soma> 28, não retorna nenhuma solução.
  7. Caso contrário, soma = soma + C.
  8. 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

Artigos interessantes...