Programação Dinâmica em Algoritmos

Prévia do material em texto

Complexidade de Algoritmos
Edson Prestes
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
u=1
i=1
j=2
u=1
i=2
j=3
j
i
u=2
i=1
j=3
u=2
i=2
j=4
u=1 u=2
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Considere
Calcule a sequência ótima de multiplicações e o preenchimento da matriz usada na 
programação dinâmica. Lembre-se da linha 5.
Seqüência ótima M = ((M1 x M 2 )x M3 )x M 4
Complexidade de Algoritmos
 Inicialmente, a entrada é decomposta em partes mínimas e resolvidas.
 A cada passo, os resultados parciais são combinados dando respostas para os 
subproblemas cada vez maiores, até que se obtenha uma resposta para o problema original.
 A decomposição é feita uma única vez e, além disso, os casos menores são tratados 
antes dos maiores.
Este método é chamado ascendente, ao contrário dos métodos recursivos, que são 
chamados descendentes.
Projeto e Análise de Algoritmos
Idéias básicas da programação dinâmica
Objetiva construir uma resposta ótima através da combinação das respostas obtidas para 
partes menores do problema (subproblemas).
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Complexidade: Multiplicação de matrizes
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
 Recebe como entrada um vetor B : vetor [ 0..n ] de IN , com as dimensões das n 
matrizes
 Fornece como saída um natural (m[1, n]) , correspondente ao número mínimo de 
multiplicações para o produto.
 Usa como área auxiliar de armazenamento uma matriz m : M, sendo 
 M := matriz [ 1..n, 1..n ] de Naturais.
É Assumido que o tamanho da entrada é o número n de matrizes a serem 
multiplicadas.
As operações aritméticas sobre os naturais são consideradas operações 
fundamentais.
O algoritmo Multi_Mat 
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
A inicialização
Inicializa a diagonal principal
A operação m[i , i] ← 0 é executada n vezes
desemp[ Inicialização ] = n . 1 = n;
Logo, 
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
A iteração nas linhas de 2 a 7 executa n - 1 vezes as linhas de 3 a 6
Considere mu os elementos da matriz acima da diagonal principal que são atualizados a 
cada iteração da linha 2. 
No início da u-ésima iteração dim( mu ) = n - u.
Executa
n-1 vezes
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
j
i
u=1 u=2
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
A maior contribuição do corpo do laço é dada pela linha 5.
Quantos valores intermediários têm que ser verificados 
para determinar o valor a ser armazenado em M[i,j] ?
Na u-ésima iteração temos,
A cada valor de k realizamos 4 operações aritméticas, logo
Desemp[Linha 5] (mu) = 4.u
(j – 1) - i + 1 = j - i = u 
(de acordo com a linha 4)
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Logo, o desempenho das linhas de 3 a 6
na u-ésima iteração é igual a
Como u varia de 1 a n-1, o desempenho da iteração é igual a 
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
A ordem da complexidade pessimista do algoritmo de Multicação de Matrizes é dada 
pela soma das três contribuições : inicialização, iteração e finalização.
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
O problema consiste em determinar caminhos de custo mínimo entre cada par de 
vértices de um grafo.
A programação dinâmica é aplicada sobre um conjunto I de vértices intermediários, o qual 
é incrementado a cada passo.
A idéia é determinar os caminhos de custo mínimo com a restrição de usar como vértices 
intermediários apenas os vértices do conjunto I.
O problema de caminhos de custo mínimo em grafo orientado. 
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Considere um grafo orientado G e a sua matriz de custos:
Considere como vértice intermediário o vértice v1 e m um valor inteiro grande.
O caminho de v3 a v2 passando por v1 tem comprimento 7+3=10 < m. 
O caminho de v2 a v3 passando por v1 tem comprimento m+6 >2.
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Considere como vértice intermediário o vértice v2. 
Considere como vértice intermediário o vértice v3. 
O caminho de v2 a v1 passando por v3 com comprimento 2+7 = 9 < m 
O caminho de v1 a v2 passando por v3 tem comprimento 5+10>3
O caminho de v1 a v3 passando por v2 com comprimento 3+2 = 5 < 6 
O caminho de v3 a v1 passando por v2 tem comprimento 10+m>7
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Inicialização
Iteração
Finalização
Complexidade de Algoritmos
 recebe como entrada um grafo orientado G com conjunto V de vértices e 
matriz de custos 
 fornece como saída uma matriz com os custos dos melhores caminhos entre 
os vértices de G)
 O tamanho da entrada corresponde ao número n de vértices de G.
 As operações fundamentais são as manipulações com os vértices e as 
matrizes.
Projeto e Análise de Algoritmos
O algoritmo
Complexidade de Algoritmos
A inicialização
Projeto e Análise de Algoritmos
Logo,
Algoritmo
Complexidade de Algoritmos
A Iteração
Projeto e Análise de Algoritmos
Algoritmo
A quantidade de elementos do Conjunto I varia com 
a iteração. Portanto no final da j-ésima iteração 
temos | I j | = j
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Temos
Algoritmo
Olhando as linhas de 11 a 15.
Na i-ésima iteração,
Desemp[linha 9-linha 10] = (n-i+1)+1
Olhando as linhas 9 e 10.
Desemp[linha 9] = n-i+1
Desemp[linha 10] =1
Note que o enquanto das linhas 8-16 é executado n vezes, ou seja , o i 
varia de 1 até n
Complexidade de Algoritmos
A iteração é executada n vezes
Projeto e Análise de Algoritmos
Algoritmo
Combinando os desempenhos obtidos anteriormente, temos
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
Sabemos
Complexidade de Algoritmos
Projeto e Análise de Algoritmos
A complexidade pessimista da Programação Dinâmica é
A complexidade pessimista da iteração é dada por