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.