Estratégias Gulosas

Usadas para resolver problemas de otimização, sempre escolhendo a estratégia localmente ótima, frequentemente alcançando soluções globais satisfatórias, mas sem garantir a solução absoluta. Em casos de problemas sem efeito retroativo, a abordagem gulosa garante uma solução global ideal.

Sem efeito retroativo significa que o estado atual é independente dos estados anteriores, dependendo apenas do momento presente.

Para problemas não resolvidos pela estratégia gulosa, consulte a seção sobre programação dinâmica.

A Busca em Largura (Breadth-First Search, BFS) é um algoritmo usado para percorrer ou pesquisar grafos. Embora não seja tradicionalmente considerada uma estratégia gulosa, sua natureza de explorar os nós mais próximos primeiro pode ser interpretada como tal. O BFS visita nós na ordem crescente da distância desde o ponto inicial.

Exemplo Simples de Guloso

Escolha uma estratégia adequaad para maximizar ou minimziar resultados.

Problema de Coelhos e Galinhas Priorize galinhas com menos pés ao calcular o máximo número de animais, e coelhos com mais pés ao calcular o mínimo, ajustando conforme necessário.

def lucro_maximo(preco):
    min_preco = preco[0]
    lucro = 0
    for i in range(1, len(preco)):
        min_preco = min(min_preco, preco[i])
        lucro = max(lucro, preco[i] - min_preco)
    return lucro

Intervalos Gulosos

Selecione o maior número possível de intervalos mutuamente exclusivos.

Problema: Selecionar programas televisivos com término mais cedo.

Código exemplo:

import sys

for entrada in sys.stdin:
    dados = entrada.split()
    capacidade = int(dados[0])
    distancia = float(dados[1])
    consumo = float(dados[2])
    num_postos = int(dados[3])
    postos = []
    posicao_atual = 0
    combustivel_atual = 0
    custo_total = 0
    chegou = False

    for _ in range(num_postos):
        posto = input().split()
        postos.append([float(posto[0]), float(posto[1])])

    postos.sort(key=lambda x: (x[1], x[0]))
    preços_ordenados = sorted(postos, key=lambda x: x[0])

    for j in range(len(postos)):
        if j == len(postos) - 1:
            break

        proximo_mais_barato = postos[j + 1][0] < postos[j][0]

        if posicao_atual == postos[j][1]:
            if proximo_mais_barato:
                necessidade = (postos[j + 1][1] - postos[j][1]) / consumo
                if combustivel_atual >= necessidade:
                    combustivel_atual -= necessidade
                    posicao_atual = postos[j + 1][1]
                else:
                    custo_total += (necessidade - combustivel_atual) * postos[j][0]
                    combustivel_atual = necessidade
                    posicao_atual = postos[j + 1][1]
                    combustivel_atual = 0
            else:
                alcance = posicao_atual + combustivel_atual * consumo
                if alcance >= postos[j + 1][1]:
                    pass
                else:
                    chegou = False
                    break
        else:
            chegou = False
            break

    if posicao_atual == postos[-1][1]:
        necessidade = (distancia - posicao_atual) / consumo
        if combustivel_atual + necessidade > capacidade:
            custo_total += (necessidade - combustivel_atual + capacidade) * postos[-1][0]
            posicao_atual += capacidade * consumo
            combustivel_atual = 0
        else:
            custo_total += necessidade * postos[-1][0]
            posicao_atual = distancia
            combustivel_atual = 0
    else:
        chegou = False

    if posicao_atual >= distancia:
        chegou = True
        print(f"{custo_total:.2f}")
    else:
        print(f"The maximum travel distance = {posicao_atual:.2f}")

Cobertura de Conjuntos

Selecione o menor conjunto de estações de rádio para cobrir todos os estados dos EUA.

estados_necessarios = set(["mt", "wa", "or", "id", "nv", "ut", "ca", "az"])
estações = {
    "kone": set(["id", "nv", "ut"]),
    "ktwo": set(["wa", "id", "mt"]),
    "kthree": set(["or", "nv", "ca"]),
    "kfour": set(["nv", "ut"]),
    "kfive": set(["ca", "az"])
}

def cobertura_conjunto(estados, estações):
    estações_selecionadas = set()
    while estados:
        melhor_estação = None
        estados_cobertos = set()
        for estação, cobertura in estações.items():
            interseção = estados & cobertura
            if len(interseção) > len(estados_cobertos) and estação not in estações_selecionadas:
                melhor_estação = estação
                estados_cobertos = interseção
        if melhor_estação is not None:
            estados -= estados_cobertos
            estações_selecionadas.add(melhor_estação)
            estações.pop(melhor_estação)
        else:
            return None
    return estações_selecionadas

print(cobertura_conjunto(estados_necessarios, estações))