Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Programação Dinâmica: Problema da Cobertura Ótima

+3 votos
20 visitas
perguntada Jun 25 em Ciência da Computação por Pablo Castro (281 pontos)  

Este é o problema 2.7 do livro Dynammic programming: A computational tool de Art Lew e Holger Mauch: OPTIMAL COVERING PROBLEM (COV)

Neste problema, precisamos proteger \(k\) arbustos de tamanhos diferentes da geada. Assuma que os arbustos são organizados por tamanho, de forma que o menor é o \(0\) e o maior é o \(k-1\). O custo de fabricação de um cobertor para o arbusto de tamanho \(i\) é denominado \(c_i\). Cobertores maiores podem proteger arbustos menores.

Restrição de fabricação: Cobertores serão fabricados em não mais que \(n\) tamanhos diferentes, onde \(n \leq k\)

Objetivo: Selecionar os \(n\) tamanhos que são capazes de proteger TODOS os arbustos ao menor custo.

A função de programação dinâmica deste problema é:
\[ f(j, l) = \left\{ \begin{array}{lll} min_{d \in \{j-2, ..., l-1\}} \{(l-d)c_l + f(j-1, d)\}& \text{if} & j > 1 \\ (l + 1)c_l & \text{if} & j =1 \end{array} \right. \]
Onde \(j\) denota o número de cobertores disponíveis que ainda não foram escolhidos e \(l\) o maior arbusto dos que ainda estão sendo considerados. O objetivo é computar \(f(n, k-1)\)

Exemplo do livro:
\(k = 10\), os custos de fabricação da cobertura do arbusto de tamanho \(i\) é dado por \( (c_0, ..., c_9) = (1, 4, 5, 7, 8, 12, 13, 18, 19, 21) \) e \(n=3\). Então a política ótima é ordenar a fabricação do \(9\), \(6\) e \(4\) (cobrindo os arbustos 9, 8 e 7 com a cobertura de tamanho 9, cobrindo os arbustos 6 e 5 com a de tamanho 6 e de 4 a 0 cobrindo com a de tamanho 4) ao custo total de \(f(3, 9) = 129 \).

Compartilhe

1 Resposta

+3 votos
respondida Jun 25 por Pablo Castro (281 pontos)  
editado 6 dias atrás por Pablo Castro

A implementação foi feita com base na fórmula da DP function dada.

Cada vez que a função é chamada, geramos uma nova dlista, onde cada unidade d pertence a uma lista que começa de j-2 e vai até l-1. De todas as iterações dentro da dlistad, a menor é guardada. Na variável mínimo, guardamos o menor custo de cada iteração

Os comentários com print's ajudam a entender melhor o que acontece. Abaixo a implementação:

def cov(n, l, cl):
    minimo = 100000000
    dlista = list(range(n-2, l)) 
    # print(f'Lista d criada: {dlista}' + '\n')
    if n > 1:
        for d in dlista:
            menor_custo = (l - d) * cl[l] + cov(n-1, d, cl)
            # print(f'{l - d} * {cl[l]} + {cov(n-1, d, cl)} = {menor_custo}')
            if menor_custo < minimo:
                minimo = menor_custo
                # print(f'Menor valor da lista d é {minimo}')
        return minimo
    elif n == 1:
        # print(f'Caiu no j=1, retornando o valor {(l + 1) * cl[l]}')
        return (l + 1) * cl[l] 

Testando o exemplo dado pelo livro:

if __name__ == '__main__': 
    k = 10
    n = 3
    cl = [1, 4, 5, 7, 8, 12, 13, 18, 19, 21]
    print(cov(n, k-1, cl)) 

Output:

129 

Como mostrado no livro.

...