Definição – O que significa Greedy Algorithm?
Um algoritmo guloso é uma estratégia algorítmica que faz a melhor escolha ideal em cada pequeno estágio com o objetivo de levar a uma solução globalmente ideal. Isso significa que o algoritmo escolhe a melhor solução no momento, sem levar em conta as consequências. Ele escolhe o melhor resultado imediato, mas não considera o quadro geral, portanto é considerado ganancioso.
Definirtec explica Greedy Algorithm
Um algoritmo guloso funciona escolhendo a melhor resposta possível em cada etapa e, em seguida, passando para a próxima etapa até chegar ao fim, sem levar em conta a solução geral. Ele apenas espera que o caminho percorrido seja o globalmente ideal, mas, como já foi provado várias vezes, esse método nem sempre apresenta uma solução globalmente ideal. Na verdade, é inteiramente possível que as soluções de curto prazo mais ótimas levem ao pior resultado global possível.
Pense nisso como uma série de atalhos em um negócio de manufatura: no curto prazo, grandes quantidades são economizadas no custo de manufatura, mas isso eventualmente leva à queda, uma vez que a qualidade é comprometida, resultando em devoluções de produtos e vendas baixas à medida que os clientes se familiarizam com o Produto “barato”. Mas nem sempre é o caso, existem muitas aplicações onde o algoritmo guloso funciona melhor para encontrar ou aproximar a solução globalmente ótima, como na construção de uma árvore de Huffman ou uma árvore de aprendizagem de decisão.
Por exemplo: pegue o caminho com a maior soma geral. Um algoritmo ganancioso tomaria o caminho azul, como resultado da miopia, ao invés do caminho laranja, que produz a maior soma.
Componentes:
- Um conjunto de dados candidato que precisa de uma solução
- Uma função de seleção que escolhe o melhor contribuidor para a solução final
- Uma função de viabilidade que auxilia a função de seleção ao determinar se um candidato pode ser um contribuidor para a 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