O que é um algoritmo ganancioso e como ele é aplicado…

O algoritmo ganancioso é uma abordagem heurística que, em cada passo, toma a decisão localmente ótima na esperança de que isso leve a uma solução globalmente ótima.

Aplicações:

Problema de seleção de atividades:

Problema: Escolher o maior número de intervalos não sobrepostos no tempo de um conjunto dado.
Solução gananciosa: Ordenar os intervalos por tempo de término crescente. A cada passo, selecionar o intervalo com o menor tempo de término que não se sobrepõe aos já selecionados.

# Exemplo de seleção de atividades
# activities = [(start_time, end_time)]

activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
activities.sort(key=lambda x: x[1]) # Ordenar por tempo de término

selected_activities = []
last_finish_time = -1

for activity in activities:
    if activity[0] >= last_finish_time:
        selected_activities.append(activity)
        last_finish_time = activity[1]

print(selected_activities) # [ (1, 4), (5, 7), (8, 11), (12, 16) ]

Problema de troco de moedas (Coin Change Problem) para conjuntos canônicos de moedas:
- Problema: Dar a quantia desejada com o menor número de moedas.
- Solução gananciosa: Usar a maior quantidade possível das denominações de moedas maiores até que a soma seja entregue. Funciona apenas para certos conjuntos de moedas (por exemplo, 1, 5, 10, 25).
```
# Exemplo de troco de moedas (para moedas canônicas)
coins = [25, 10, 5, 1]
amount = 67
result = {}

for coin in coins:
    while amount >= coin:
        result[coin] = result.get(coin, 0) + 1
        amount -= coin

print(result) # {25: 2, 10: 1, 5: 1, 1: 2}
```
Algoritmo de Kruskal para encontrar a árvore geradora mínima:
- Problema: Encontrar um subconjunto de arestas de um grafo não dirigido ponderado conectado que conecta todos os vértices com o peso total mínimo.
- Solução gananciosa: Ordenar todas as arestas por peso em ordem crescente. Adicionar as arestas na ordem, se elas não formarem um ciclo com as já selecionadas, até que n-1 arestas tenham sido adicionadas (onde n é o número de vértices).

Algoritmos gananciosos são fáceis de implementar, mas nem sempre encontram a solução globalmente ótima para problemas arbitrários. Para alguns problemas (por exemplo, troco de moedas com conjuntos arbitrários, problema da mochila em geral), a abordagem gananciosa não é ótima. Para garantir a optimalidade ou uma melhor aproximação, podem ser necessários métodos como programação dinâmica ou outros. Antes de aplicar um algoritmo ganancioso, é importante garantir que ele seja adequado para o problema em questão.

O que é um algoritmo ganancioso e como ele é aplicado na resolução de problemas?