Estruturas de dados - Algoritmos Greedy
Um algoritmo é projetado para alcançar a solução ideal para um determinado problema. Na abordagem de algoritmo guloso, as decisões são feitas a partir do domínio de solução dado. Por ser ganancioso, é escolhida a solução mais próxima que parece fornecer uma solução ótima.
Algoritmos gananciosos tentam encontrar uma solução ótima localizada, que pode eventualmente levar a soluções globalmente otimizadas. No entanto, algoritmos geralmente gananciosos não fornecem soluções otimizadas globalmente.
Contando Moedas
Este problema é contar até um valor desejado escolhendo o menor número possível de moedas e a abordagem gananciosa força o algoritmo a escolher a maior moeda possível. Se nos forem fornecidas moedas de $$ 1, 2, 5 e 10 e formos solicitados a contar $$ 18, o procedimento ganancioso será -
1 - Selecione uma moeda de $ 10, a contagem restante é 8
2 - Em seguida, selecione uma moeda de $ 5, a contagem restante é 3
3 - Em seguida, selecione uma moeda de $ 2, a contagem restante é 1
4 - E, por fim, a seleção de uma moeda de 1 $ resolve o problema
Embora, pareça estar funcionando bem, para esta contagem precisamos pegar apenas 4 moedas. Mas se mudarmos ligeiramente o problema, a mesma abordagem pode não ser capaz de produzir o mesmo resultado ótimo.
Para o sistema monetário, onde temos moedas de 1, 7, 10 valores, contar moedas para o valor 18 será absolutamente ótimo, mas para contas como 15, pode usar mais moedas do que o necessário. Por exemplo, a abordagem gananciosa usará 10 + 1 + 1 + 1 + 1 + 1, total de 6 moedas. Considerando que o mesmo problema poderia ser resolvido usando apenas 3 moedas (7 + 7 + 1)
Portanto, podemos concluir que a abordagem gananciosa escolhe uma solução otimizada imediata e pode falhar onde a otimização global é uma grande preocupação.
Exemplos
A maioria dos algoritmos de rede usa a abordagem gananciosa. Aqui está uma lista de alguns deles -
- Problema do caixeiro viajante
- 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
- Gráfico - Colorir Mapa
- Gráfico - Capa do vértice
- Problema da mochila
- Problema de programação de trabalho
Existem muitos problemas semelhantes que usam a abordagem gananciosa para encontrar uma solução ideal.