Índice:
Definição - O que significa o Greedy Algorithm?
Um algoritmo ganancioso é uma estratégia algorítmica que faz a melhor escolha ideal em cada estágio pequeno, com o objetivo de levar a uma solução ótima globalmente. Isso significa que o algoritmo escolhe a melhor solução no momento, sem levar em consideração as consequências. Ele escolhe a melhor saída imediata, mas não considera o cenário geral, portanto é considerado ganancioso.
Techopedia explica o algoritmo ganancioso
Um algoritmo ganancioso funciona escolhendo a melhor resposta possível em cada etapa e depois passando para a próxima etapa até chegar ao fim, sem levar em consideração a solução geral. Ele espera apenas que o caminho a seguir seja o ideal globalmente, mas, como comprovado repetidamente, esse método nem sempre apresenta uma solução ideal globalmente. De fato, é inteiramente possível que as melhores soluções de curto prazo levem ao pior resultado global possível.
Pense nisso como usar muitos atalhos em um negócio de manufatura: no curto prazo, grandes quantidades são economizadas no custo de manufatura, mas isso eventualmente leva à queda, pois a qualidade é comprometida, resultando em devoluções de produtos e baixas vendas à medida que os clientes se familiarizam com o produto. Produto "barato". Mas nem sempre é esse o caso, existem muitas aplicações em que o algoritmo ganancioso funciona melhor para encontrar ou aproximar a solução globalmente ótima, como na construção de uma árvore de Huffman ou de uma árvore de aprendizado de decisão.
Por exemplo: Siga o caminho com a maior soma geral. Um algoritmo ganancioso seguiria o caminho azul, como resultado da miopia, em vez do caminho laranja, que produz a maior soma.
Componentes:
- Um conjunto candidato de dados que precisa de uma solução
- Uma função de seleção que escolhe o melhor colaborador para a solução final
- Uma função de viabilidade que auxilia a função de seleção, determinando se um candidato pode ser um colaborador da solução
- Uma função objetivo que atribui um valor a uma solução parcial
- Uma função de solução que indica que a solução ideal foi descoberta
