Prof. Dr. Sérgio Crespo
Alexandre Nunes Barbosa
Daniel de Souza Martins
[email protected]/ [email protected]








Introdução
Como Funciona
Como Funciona: Características
Aplicação
Múltiplos caminhos
Fibonacci
Conclusão
Referencias
É um método de construção de algoritmos
para
a
resolução
de
problemas
computacionais, em especial os de
otimização combinatória.
Se aplica aos problemas cuja a solução
ótima pode ser computada a partir da
solução ótima de seus subproblemas
(estas
soluções
devem
estar
armazenadas de forma a evitar o
recálculo).

Particiona os problemas em subproblemas
independentes;

Resolve os problemas de forma recursiva;

Armazena as soluções em uma tabela;

Combina as soluções
problema original.
para
resolver
o



Subestrutura ótima: as soluções ótimas do
problema contém soluções ótimas para os
subproblemas;
Sobreposição de subproblemas (Overlaping
subproblems): A solução ótima de um
subproblema é utilizada várias vezes, mas
calculada uma única vez;
Fórmula de recorrências: descreve a relação
entre as soluções ótimas dos subproblemas.

Caminhos mínimos (algorítimo de Floyd
Warshall);

Fibonacci;

Jogo da velha;

Problema binário da mochila;

Multiplicação de cadeia de matrizes.

Dado um grafo orientado G, calcular o custo
mínimo do caminho mais curto entre todos
os pares de vértices. Os custos podem ser
negativos, mas não existem ciclos negativos.

Problema:
◦ Calcular a menor distância (custo) entre todos os
vértices do grafo.
◦
◦
◦
◦
◦
◦
◦
◦
Calcular
Calcular
Calcular
Calcular
a
a
a
a
Calcular a
Calcular a
Calcular a
Calcular a
distância
distância
distância
distância
entre
entre
entre
entre
1
1
1
1
distância entre
distância entre
distância entre
distância entre
◦
◦
◦
◦
e
e
e
e
3
3
3
3
2;
3;
4;
5;
◦
◦
◦
◦
Calcular a
Calcular a
Calcular a
Calcular a
distância entre
distância entre
distância entre
distância entre
2
2
2
2
e
e
e
e
1;
3;
4;
5;
e
e
e
e
◦
◦
◦
◦
Calcular a
Calcular a
Calcular a
Calcular a
distância entre
distância entre
distância entre
distância entre
4
4
4
4
e
e
e
e
1.
2.
3.
5.
1;
2;
4;
5;
Calcular a
Calcular a
Calcular a
Calcular a
distância entre
distância entre
distância entre
distância entre
5
5
5
5
e
e
e
e
1;
2;
3;
4;
5
4
5
3
4
3
2
3
2
1
0
f(x)
2
2
1
1
2
1
3
0
1
1
2
3
5
1
0
1
0
1
0



Um algoritmo que utiliza computação
dinâmica permite computar a solução para
cada subproblema uma única vez;
Executando o algoritmo uma vez é possível
obter todos os resultados, que armazenados
não precisam mais ser calculados.
O uso da programação dinâmica reduz o
custo de processamento.




Programação Dinâmica. Disponível em:
<http://pt.wikipedia.org/wiki/Programa%C3%A7
%C3%A3o_din%C3%A2mica>
ALGORITIMOS AVANÇADOS, PROGRAMAÇÃO
DINÂMICA. Disponível em:
<http://agilextremme.blogspot.com//>
Programação Dinâmica. Disponível em:
<http://vidageek.net/2008/02/11/programacao
-dinamica/>
Programação Dinâmica. Souza, Cid C. de.
Disponível em: <http://vidageek.net/wpcontent/uploads/2008/02/progdin.pdf>