Abordagem Gulosa

Abordagem dividir-e-conquistar

Programação dinâmica

Sequência de Fibonacci

• Por exemplo, considere a sequência de Fibonacci:

$F_n = \begin{cases} 1 &\text{se } n=1 \\ 1 &\text{se } n=2 \\ F_{n-1}+F_{n-2}&\text{se } n>2 \end{cases}$

Sequência de Fibonacci

Fibonacci recursivo

• Cuja complexidade é dada pela equação de recorrência:

$T(n) =T(n-1)+T(n-2)+1$

Qual é a complexidade?

• Vamos usar o método da substituição para mostrar que $\Omega\left(\left(\frac{1+\sqrt{5}}{2}\right)^n\right)$
• Inicialmente, vamos mostrar que $T(n) \geq x^n$ para $x>1$.
• Seja $T(1) = 1$, e $T(2)=3$, e $n\geq 2$
• Suponha que $T(m)\geq x^n$, para $2\leq m \leq n-1$. Assim, aplicando a $T(n)$, temos:

$\begin{aligned} T(n) &=T(n-1)+T(n-2)+1 \\ & \geq x^{n-1}+x^{n-2} \\ & \geq x^{n-2}(1+x) \end{aligned}$

Qual é a complexidade?

• Note que $1+x\geq x^2$ para $(1-\sqrt{5}) / 2 \leq x \leq(1+\sqrt{5}) / 2$.
• Portanto, fazendo $x=(1+\sqrt{5}) / 2$ e substituindo em $T(n)$, temos

$\begin{aligned} T(n) & \geq\left(\frac{1+\sqrt{5}}{2}\right)^{n-2}\left(1+\left(\frac{1+\sqrt{5}}{2}\right)\right) \\ & \geq\left(\frac{1+\sqrt{5}}{2}\right)^{n-2}\left(\frac{1+\sqrt{5}}{2}\right)^{2} \\ &=\left(\frac{1+\sqrt{5}}{2}\right)^{n} \end{aligned}$

Dá pra fazer melhor?

• Observe que na abordagem puramente recursiva, precisamos resolver o mesmo problema várias vezes.

• Podemos criar uma memória auxiliar para armzenar valores intermediários.

  • Criar um vetor de tamanho $n$
  • A medida que formos calculando $F_i$, armanezenamos esse valor para consultar posteriormente.

Fibonacci com memória

Fibonacci com memória

• Uma outra abordagem é preencher o vetor em uma abordagem bottom-up

Fibonacci com memória

• Esse é um exemplo de programação dinâmica!

• É fácil ver que a complexidade do algoritmo é $O(n)$ já que a consulta ao vetor pode ser feita em $O(1)$

• Entretanto, precisamos de uma memória auxiliar para armazenar os subproblemas já solucionados

Corte da barra de ferro

• Considere um problema em que temos uma barra de ferro de tamanho $n$, e queremos dividí-la em pedaços, cujos tamanho também são inteiros

• Suponha também que os pedaços tem preços diferentes

• Como cortar as barra para otimizar o lucro?

Corte da barra de ferro

Corte da barra de ferro

• Quantas combinações de corte existem?
• Cada ponto de corte é uma variável aleatória binária ($0$ ou $1$)
• Temos $n-1$ possíveis pontos de corte
• O total de possibilidades é $2^{n-1}$

Corte da barra de ferro

• Uma abordagem simplista consiste em gerar todas as possíveis combinações
• Calcular o lucro de cada uma delas
• Selecionar aquela que maximiza o lucro
• Claramente essa abordagem tem uma complexidade $O(2^n)$, já que temos $2^{n-1}$ combinações

Corte da barra de ferro

• Uma outra possibilidade é um algoritmo recursivo

• Um algoritmo recursivo para o problema do corte da barra escolhe uma posição $p_i$ para fazer o corte e faz uma chamada recursiva

• Como não sabemos qual o tamanho do primeiro corte, testamos todas as possibilidades de $1$ a $n$

Corte da barra de ferro recursivo

Corte da barra de ferro recursivo

• A equação de recorrência desse algoritmo é
  $T(n) = 1+\sum_{i=1}^nT(n-i)$

• Podemos usar o método da substituição para mostrar que esse algoritmo é $O(2^n)$. Suponha que $T(m)\geq2^m$ para $0\leq m\leq n-1$

$\begin{aligned}T(n)&=1+T(0)+T(1)+\cdots+T(n-1)\\ & \geq 1+\left(2^{0}+2^{1}+\cdots+2^{n-1}\right)\\ & =2^{n}\end{aligned}$

Corte da barra de ferro recursivo

Corte da barra de ferro

• O problema do corte da barra de ferro é um problema de otimização

• Ele tem a propriedade de subestrutura ótima

  • Você precisa saber o corte ótimo do sub-problema para calcular o corte ótimo

• Tem uma solução recursiva exponencial

Corte da barra de ferro

• Vamos usar um vetor $B$ de $n$ posições para armezar o custo de um sub-problema já resolvido
• Além disso, um vetor $S$ em que a posição $S[j]$ indica a posição em que a barra de tamanho $j$ deve ser cortada

Corte da barra de ferro

Abordagem BottomUP

• Também podemos ter uma abordagem BottomUp

Corte da barra de ferro

• Considerando os preços

• O algoritmo calcula

Corte da barra de ferro

• O primeiro passo do algoritmo é verificar se o subproblema já foi resolvido.
• Caso não esteja resolvido, ele faz isso de uma maneira parecida com o algoritmo CorteBarra.
• A diferença é que o primeiro local pra fazer o corte de uma barra de tamanho $i$ é armazenada em $S[i]$, e o maior lucro em $B[i]$.

Complexidade

• Observe que a cada chamada de CorteBarraRecursivoTopDown, um subproblema que já foi resolvido retorna imediatamente.
• As demais linhas são executadas em tempo constante.
• Como armazenamos o resultado sempre que resolvemos um subproblema, cada subproblema é resolvido uma vez.
• O tempo de execução é então

$T(m)=1+2+\cdots+m=\Theta\left(m^{2}\right)$

Impressão dos Cortes

• Para saber os pontos de corte, podemos percorrer o vertor $S[i]$ para encontrar os pontos de corte.
• Observe que em $S[n]$, temos o tamanho do primeiro corte.
• Após esse corte, a barra tem tamanho $n-S[-]$
  

Mochila inteira

• Dado um conjunto $I=\{1,2,\cdots,n\}$ contendo $n$ itens
• Cada item $i\in I$ tem um peso $w_i$ e um valor $v_i$
• Como podemos selecionar um subconjutno de $S \subseteq I$ uma mochila com capacidade $W$ tal que:
  • O peso dos itens selecionados cabe na mochila: $\sum_{i \in S} w_i \leq W$
  • O valor dos itens selecionados é maximo: $\max \sum_{i \in S} v_i$

Mochila inteira

• Por exemplo, dado o seguinte conjunto de itens

• Como podemos selecionar itens para preencher uma mochila de tamanho 10?

Mochila inteira

• Podemos resolver o problema por força bruta enumerando todos os subconjuntos possíveis
• Verificar quais subconjuntos cabem na mochila
• Calcular o valor total dos suconjuntos que cabem e armazenar o maior deles

Quantos subconjuntos existem?

• Para cada item, temos a opção de colocá-lo ou não
• Temos um total de $2^n$ subconjuntos
• Para cada conjunto, levamos $O(n)$ para verificar se os itens cabem na mochila e qual é o seu valor total
• Ou seja, esse algoritmo leva temp $O(n2^n)$

Subestrutura do problema

• Seja uma instância do problema por $K\left(I_{n}, v, w W\right)$, em que:
  • $I_n = \{1,2,\cdots,n\}$ um conjunto de itens
  • $v$ é uma lista dos valores dos itens
  • $w$ é uma lista dos pesos dos itens
  • $W$ é a capacidade da mochila

Subestrutura do problema

• $S^*$ é uma solução ótima para $K(I_{n}, v, w, W)$, e $S^*\subseteq, I_n$ com um valor total ótimo $V_{n,W} = \sum_{i \in S^*} v_i$

  • Se $n \notin S$, então $S^*$ também é uma solução para $K\left(I_{n-1}, W\right)$
  • Se $n \in S$, então $S^*$ também é uma solução para $K\left(I_{n-1}, W - w_n\right)$

• Como saber se $n$ está em $S^*$?

  • Máximo entre selecionar ou não o item $n$, se ele cabe na mochila
  • Valor do problema desconsiderando o item $n$, se ele não cabe na mochila

$V_{n, W}=\left\{\begin{array}{ll}{\max \left\{V_{n-1, W}, V_{n-1, W-w_{n}}+v_{n}\right\}} & {\text { se } w_{n} \leq W} \\ {V_{n-1, W}} & {\text { se } w_{n}>W}\end{array}\right.$

Mochila inteira

Mochila inteira

• Uma solução direta recursiva baseada nessa regra:

Mochila inteira

• A equação de recorrência para esse algoritmo é $T(n) = 2(Tn-1)$, cuja solução é $O(2^n)$

• Olhando a árvore de recursão, é fácil perceber que esse algoritmo resolve o mesmo subproblema várias vezes.

• Observe que os subproblemas dependem tanto do número de itens $n$, quanto da capacidade $W$ do subproblema.

  • Poderíamos armazenar as soluções usando um vetor de tamanho $nW$
  • Entretanto, usar uma matriz $n \times W$ facilita a indexação

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Mochila inteira

Imprimindo a mochila

• Na última célula da matriz $M[n][W]$ contém o valor ótimo.

• Mas não sabemos quais itens devem estar na mochila

• No entanto, a maneira como a matriz foi preenchida nos permite obter quais são esses elementos

Imprimindo a mochila

Complexidade

• É fácil perceber que a complexidade do algoritmo é proporcioal ao tamanho da matriz, ou seja $O(nW)$

• No entanto, observe que precisamos de uma coluna na tabela para cada possível tamanho da mochila dos subproblemas. Esse número, no entanto, não é polinomial no tamanho do da entrada

• Considerando pesos inteiros, teríamos $O(2^{\log W})$ possíveis valores para $W$, e a complexidade do algoritmo é $O(n2^{\log W})$

• Esse algoritmo é o que chamamos de pseudo-polinomal

Programação dinâmica

1. Identificar subestrutura ótima
2. Encontrar uma formulação recursiva
3. Usar programação dinâmica para encontrar o valor da função ótima
4. Se necessário, armazenar informação adicional de tal maneira que no passo 3 podemos encontrar a solução ótima