DAA - Método Ganancioso
Entre todas as abordagens algorítmicas, a abordagem mais simples e direta é o método Greedy. Nesta abordagem, a decisão é tomada com base nas informações atualmente disponíveis, sem se preocupar com o efeito da decisão atual no futuro.
Algoritmos gananciosos constroem uma solução parte por parte, escolhendo a próxima parte de forma que ela forneça um benefício imediato. Essa abordagem nunca reconsidera as escolhas feitas anteriormente. Essa abordagem é usada principalmente para resolver problemas de otimização. O método Greedy é fácil de implementar e bastante eficiente na maioria dos casos. Portanto, podemos dizer que o algoritmo Greedy é um paradigma algorítmico baseado em heurística que segue a escolha ótima local em cada etapa com a esperança de encontrar uma solução ótima global.
Em muitos problemas, ele não produz uma solução ótima, embora forneça uma solução aproximada (quase ótima) em um tempo razoável.
Componentes do Algoritmo Greedy
Algoritmos gananciosos têm os seguintes cinco componentes -
A candidate set - Uma solução é criada a partir deste conjunto.
A selection function - Usado para escolher o melhor candidato a ser adicionado à solução.
A feasibility function - Usado para determinar se um candidato pode ser usado para contribuir para a solução.
An objective function - Usado para atribuir um valor a uma solução ou solução parcial.
A solution function - Usado para indicar se uma solução completa foi alcançada.
Areas de aplicação
Abordagem gananciosa é usada para resolver muitos problemas, como
Encontrando o caminho mais curto entre dois vértices usando o algoritmo de Dijkstra.
Encontrar a árvore geradora mínima em um gráfico usando o algoritmo de Prim / Kruskal, etc.
Onde a abordagem gananciosa falha
Em muitos problemas, o algoritmo Greedy falha em encontrar uma solução ótima, além disso, pode produzir a pior solução. Problemas como caixeiro viajante e mochila não podem ser resolvidos com esta abordagem.