O que é um algoritmo guloso e em que casos é aplicado?

O algoritmo guloso é uma abordagem para resolver problemas de otimização que, a cada passo, escolhe a melhor solução local (a opção mais vantajosa do ponto de vista do momento atual) na esperança de que essa sequência de soluções locais ótimas conduza a uma solução globalmente ótima. Ele não considera as possíveis consequências da escolha atual nos passos futuros.

Características:

• Simplicidade: Geralmente mais fácil de implementar do que programação dinâmica ou outros métodos de otimização.
• Velocidade: Frequentemente tem menor complexidade computacional.
• Garantia de otimalidade: Nem sempre garante encontrar a solução globalmente ótima. A garantia aplica-se apenas a certos tipos de problemas.

Aplica-se em problemas onde foi demonstrado que a escolha localmente ótima em cada passo leva a uma solução globalmente ótima. Exemplos:

• Problema de seleção de atividades: Escolher o maior número de atividades não sobrepostas no tempo.
• Problema da mochila (com fracionamento de objetos): Quando os objetos podem ser divididos. Caso contrário, é um problema de programação dinâmica.
• Algoritmo de Prim e Kruskal: Para encontrar a árvore geradora mínima em um grafo.
• Algoritmo de Dijkstra: Para encontrar o caminho mais curto em um grafo com pesos de aresta não negativos.
• Codificação de Huffman: Para construir um código prefixo ótimo.

Exemplo de pseudocódigo para o algoritmo de seleção de atividades:

Função SelecionarAtividades(atividades):
  Ordenar atividades por tempo de término
  atividades_selecionadas = lista vazia
  último_tempo_de_fim = 0

  Para cada atividade em atividades:
    Se atividade.início >= último_tempo_de_fim:
      Adicionar atividade a atividades_selecionadas
      último_tempo_de_fim = atividade.fim

  Retornar atividades_selecionadas

É importante verificar se o algoritmo guloso é aplicável a um problema específico, pois caso contrário, pode fornecer uma solução subótima.

# Exemplo simples onde o algoritmo guloso não é ótimo
# Problema de troco: dar a menor quantidade de moedas
# Moedas disponíveis: [1, 5, 10, 25] USD
# Por exemplo, para 30 centavos

# Algoritmo guloso:
# Pegamos a maior moeda <= 30 (25) -> resto 5
# Pegamos a maior moeda <= 5 (5) -> resto 0
# Resultado: 2 moedas (25 + 5). Aqui, é ótimo.

# Moedas disponíveis: [1, 6, 10]
# Para 12 centavos

# Algoritmo guloso:
# Pegamos a maior moeda <= 12 (10) -> resto 2
# Pegamos a maior moeda <= 2 (1) -> resto 1
# Pegamos a maior moeda <= 1 (1) -> resto 0
# Resultado: 3 moedas (10 + 1 + 1).
# A solução ótima seria 2 moedas (6 + 6).

# Este exemplo mostra que o algoritmo guloso nem sempre leva à solução globalmente ótima,
# se as propriedades do problema não forem compatíveis com sua aplicação (por exemplo,
# denominações de moeda padrão geralmente permitem o uso do guloso,
# mas denominações arbitrárias não).