Please enable JavaScript.
Coggle requires JavaScript to display documents.
Olavo Rangel da Conceição - MM 16 - Coggle Diagram
Olavo Rangel da Conceição - MM 16
Programação Dinâmica
Resolver Problemas
Por meio de Subprobemas
Variação
Space-for-Time Trade-Off
Algumas Situações
Evitar Espaço Extra
Fibonacci
Implementação
Bottom-up
Resolve todos os subproblemas
Top-down
Resolve todos os subproblemas necessários
Exemplos de problemas
Coin-row problem
Existe uma Linha de N moedas
Valores Inteiros Positivos
Não são Necessariamente Distintos
Objetivo
Pegar o máximo da quantidade de dinheiro
Não pode pegar duas moedas adjacentes
Relação de Recorrencia
F(n) = max(Cn + F(n-2), F(n-1))
1 more item...
F(0) = 0 e F(1) = C1
Change-making problem
Dar o troco para o valor N
Usando o menor número de moedas
d1<d2<...<dm
d1 = 1
Moedas ilimitadas
Relação de Recorrencia
F(n) = minj:n>=dj{F(n - dj)} + 1
N>0
F(0) = 0
Knapsack
N itens de peso wi
valor Vi
Capacidade W
I = 1 ... N
Achar o subconjunto
De itens mais preciosos que capem na capacidade W
Relação de Recorrência
F(i,j) = max{F(i-1,j), Vi + F(i-1,j-wi)}
j - wi >= 0
F(i, j) = F(i − 1, j)
, j − wi < 0
F(0,j)=0
j>=0
F(i,0)= 0
i>=0
Memory Functions
Auxilia na hora de implementar a forma top-down
Resolve o problema de maneira descendente
Mantém uma tabela do tipo que seria usado por uma dinâmica Bottom-up
Approximation Algorithms
As vezes
Dificil
Achar Solução
NP-Completo ⊂ NP-Dificil
Solução não precisa ser ótima
Aceitável Suficiente
Exemplo
Greed Approximation for TSP
Nearest-Neighbour Algorithm
sempre ir na próxima aresta não visitado mais próxima
Passos
Escolher uma cidade arbitraria
Ir para a cidade não visitada mais próxima da ultima visitada
2 more items...
MST-Based Algorithm
Construir a MST
Caminhar pela MST
Registrando a ordem dos nós visitados
Eliminar todas as ocorrências repetidas
Exceto o nó inicial
Fazendo atalhos em uma caminhada