Algoritmos Gulosos

4.1 Definição de algoritmos gulosos.

Algoritmos Gulosos (Greedy Algorithms) — é uma classe de algoritmos que constroem a solução tomando decisões localmente ótimas em cada passo. Essas decisões são baseadas no estado atual e não são revistas no futuro.

Algoritmos gulosos são frequentemente usados para resolver problemas de otimização, onde a meta é maximizar ou minimizar uma certa quantidade.

Princípios básicos dos algoritmos gulosos

• Escolha gulosa: Em cada passo, o algoritmo escolhe a melhor opção local, que, segundo ele, levará à solução globalmente ótima.
• Subestrutura ótima: O problema deve ter a propriedade de que soluções localmente ótimas podem ser combinadas para obter uma solução globalmente ótima.
• Monotonicidade: Depois de escolher um passo localmente ótimo, a solução não deve ser prejudicada por escolhas subsequentes.

Vantagens e desvantagens dos algoritmos gulosos

Vantagens:

• Facilidade de implementação: Algoritmos gulosos são frequentemente fáceis de entender e implementar.
• Eficiência: Normalmente, eles funcionam mais rápido do que algoritmos mais complexos, como programação dinâmica.

Desvantagens:

• Falta de otimalidade global: Algoritmos gulosos nem sempre levam a uma solução globalmente ótima.
• Nem todos os problemas são adequados: Somente certos problemas podem ser resolvidos por algoritmos gulosos.

Existe toda uma classe de problemas, onde a melhor solução é alcançada por um algoritmo guloso. Seria útil aprender sobre esses.

4.2 Problema da troca de moedas.

Problema:

Temos moedas de diferentes denominações. Precisamos encontrar o número mínimo de moedas para devolver um determinado troco.

Solução:

A moeda com a maior denominação, que não excede o valor restante, é sempre escolhida.

Complexidade temporal: O(n), onde n é o número de tipos de moedas.

Exemplo de código em Python:

def min_coins(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count
        

4.3 Problema da mochila

Problema:

Temos itens com valores e pesos conhecidos. Queremos colocar no mochila de tamanho fixo itens no valor máximo possível

Nesta variação do problema, os itens podem ser divididos em partes. Por exemplo, queremos comprar diferentes grãos, e pode ser 1000 gramas, ou até 512.

Solução:

Ordenação dos itens por valor específico (valor/peso) e escolha das maiores relações específicas até encher a mochila.

Complexidade temporal: O(n log n), onde n é o número de itens.

Exemplo de código em Python:

class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight
        self.ratio = value / weight
        
def fractional_knapsack(items, capacity):
    items.sort(key=lambda x: x.ratio, reverse=True)
    total_value = 0.0
    for item in items:
        if capacity >= item.weight:
            total_value += item.value
            capacity -= item.weight
        else:
            total_value += item.ratio * capacity
            break
    return total_value
        
        

4.4 Problema de cobertura com segmentos

Problema:

Existem segmentos em uma linha reta, dados pelas suas extremidades (x1, x2), e um segmento-alvo. É necessário encontrar o número mínimo de segmentos que cubram todos os pontos do segmento-alvo.

Solução:

Ordenação dos segmentos pela extremidade direita e escolha do menor segmento, cobrindo o ponto atual.

Complexidade temporal: O(n log n), onde n é o número de segmentos.

Exemplo de código em Python:

def min_segments(segments):
    segments.sort(key=lambda x: x[1])
    count = 0
    end = -float('inf')
    for seg in segments:
        if seg[0] > end:
            end = seg[1]
            count += 1
    return count
        

1

Опрос

Algoritmos gananciosos,  59 уровень,  3 лекция

недоступен

Algoritmos gananciosos

Algoritmos gananciosos

Открыть