Please enable JavaScript.
Coggle requires JavaScript to display documents.
Programação dinâmica, Algoritmos de aproximação para problemas NP-hard -…
Programação dinâmica
Problema das moedas
Problema: Temos uma carreira de N moedas de valores positivos mas não necessariamente distintos, o objetivo é obter a maior quantidade de dinheiro possível dado a que nenhuma moeda obtida seja adjacente a outra obtida.
A relação de recorrência é deduzida a partir da seleção que inclui a última moeda (F(n-2) + Cn) e da seleção que não inclui a última moeda (F(n-1)). Sendo F(0) o estado inicial (Nenhuma moeda obtida) e F(1) selecionando a primeira moeda.
Técnica de design de algorimto inventada como um método geral para otimizar processos de decisões multi-etapa, ou seja, 'Programação' nesse contexto quer dizer PLANEJAMENTO e não programação computacional.
-
A abordagem Bottom-Up da programação dinâmica consiste em resolver todos os menores subproblemas de um dado problema.
Já a abordagem Top-Down consiste em uma exploração de "funções de memória" e evitar resolver subproblemas desnecessários.
-
Problema da Mochila
Problema: dado n itens de pesos conhecidos (não negativos) e valores conhecidos não negativos e uma mochila de capacidade W, qual o conjunto de itens que cabem na mochila a fim de maximizar a quantidade de itens?
Para uma subinstância vamos manter duas variáveis em mente: O valor da melhor solução para os primeiros i itens que cabem numa mochila de capacidade j.
A partir disso, classificamo-os em dois grupos: Os que contém o item i (solução F(i-1, j - wi) + vi) e os que não contém o item i (solução F(i-1,j)).
Sabemos que F(0, j) = 0 para j >= 0 e F(i, 0) = 0 para j >= 0.
-
Para uma abordagem top-down, vamos estabelecer uma função de memória que vai nos permitir não recomputar algo que já computamos previamente. (Lembre que os subproblemas se sobrepõem)
Temos um ganho de constante em relação à abordagem bottom-up, mas de maneira geral elas tema mesma classe de eficiência. A top-down pode ser menos eficiente espacialmente do que uma bottom-up.
O mais crucial, não importando a abordagem, é derivar uma relação de recorrência entre a solução do problema e as soluções dos seus menores subproblemas.
-