Programação Dinâmica
Profa. Sandra de Amo
Bacharelado em Ciência da Computação – UFU
Disciplina de Análise de Algoritmos
Um exemplo de motivação
Problema: encontrar o caminho mais curto
entre dois vértices S e A em um grafo
dirigido acíclico.
Algoritmo de Dijkstra resolve este problema
em tempo O(|V|2) ou O((|E|+|V|) log(|V|)
(dependendo do tipo de implementação
da fila com prioridades)
Uma outra técnica para resolver
este problema
- Grafos acíclicos dirigidos são linearizáveis
Linearização: vértices podem ser ordenados de modo que qualquer
uv sempre vai da esquerda para a direita seguindo a ordem dos vértices
Por que isto ajuda na hora de encontrar o menor caminho entre dois vértices,
por exemplo S para D ?
Encontrando o menor caminho,
usando a linearização do grafo
A única maneira de chegar a D a partir de S, é vindo de B ou de C
dist(D) = comprimento total do menor caminho entre S e D
= min{ dist(B) + 1, dist(C) + 3 }
Problema
original
Subproblema
Subproblema
Encontrando o menor caminho,
usando a linearização do grafo
dist(D) = comprimento total do menor caminho entre S e D
= min{ dist(B) + 1, dist(C) + 3 }
dist(B) = dist(A) + 6
dist(A) = min{ dist(C) + 4, dist(S) + 1}
dist(C) = dist(S) + 2
dist(S) = 0
Temos 4 subproblemas: dist(B), dist(A), dist(C) e dist(S) a resolver
A ordem dos vértices dada pela linearização do grafo, induz uma ordem
nos subproblemas !!
Programação dinâmica:
características principais da técnica
A solução de um problema P se reduz a
• resolver completamente um conjunto de subproblemas P1, ..., Pn
• Os subproblemas são ORDENADOS
• Subproblemas são resolvidos em ordem crescente
• Armazena-se as soluções obtidas na etapa k para resolver o problema da etapa
k+1.
Exemplo:
dist(D) = comprimento total do menor caminho entre S e D
= min{ dist(B) + 1, dist(C) + 3 } = min{7+1, 2+3} = 5
dist(B) = dist(A) + 6
 dist(B) = 7
dist(A) = min{ dist(C) + 4, dist(S) + 1}
dist(C) = dist(S) + 2
dist(S) = 0
 dist(C) = 2
 dist(A) = min{2+4, 0+1} = 1
dist(D) = comprimento total do menor caminho entre S e D
= min{ dist(B) + 1, dist(C) + 3 } = min{7+1, 2+3} = 5
dist(B) = dist(A) + 6
 dist(B) = 7
dist(A) = min{ dist(C) + 4, dist(S) + 1}
dist(C) = dist(S) + 2
 dist(C) = 2
dist(S) = 0
Caminho mais curto: S – C, C - D
 dist(A) = min{2+4, 0+1} = 1
Algoritmo para Caminho mais curto
usando PD
Input: Grafo G = (V,E) acíclico, vértice inicial S
Output: Um array dist com |V| posições contendo na posição do vértice A, o
comprimento do caminho mais curto de S para A.
•
•
•
•
•
•
•
•
Lineariza G; (O(|V| + |E|)
Para todo vértice x
dist(x) = inf
dist(S) = 0
Para cada v  V – {S}, na ordem linear
Para cada aresta e = (u,v) ∈ E
Ke = dist(u) + l(u,v) % dist(u) já foi calculado, pois u vem antes
de v na ordem !!
dist(v) = min{Ke}
Análise de Complexidade
• Complexidade PD:
O(|V|+|E|) + O(|V|) + O(|V| + |E|) = O(|V| + |E|)
• Dijkstra:
O(|V|2) ou O((|E| + |V|).log(|V|)
• PD é melhor que Dijkstra (mas só funciona para
grafos acíclicos dirigidos !)
Programação Dinâmica
• Paradigma algoritmo bastante poderoso
• Um problema P é reduzido a uma sequência ordenada de
subproblemas P1, P2,...,Pn = P
• Resolve-se completamente cada subproblema na ordem até chegar
a P.
• A solução de um problema Pk consiste em aplicar uma função
simples às soluções (já encontradas) de problemas Pi, com i<k.
• Técnica de planejamento introduzida por Richard Bellman nos
anos 50.
• O termo programação dinâmica era utilizado no sentido de
planejamento dinâmico !
Um outro exemplo:
Subsequências crescentes mais longas
Seja S uma sequência de números naturais {a1,a2,...,an}
Uma subsequência é um subconjunto de S considerado em
sequência: ai1, ai2, ..., aik
Uma subsequência crescente é uma subsequência de S onde os
números são pegos em ordem estritamente crescente
ai1 < ai2 < ... < aik
Exemplo : S = 5, 2, 8, 6, 3, 6, 9, 7
Subsequência crescente : 2, 3, 6, 9
Problema: Encontrar a subsequência crescente mais longa.
Como reduzir o problema a um
problema de grafos
Associar a S (sequência original) um grafo dirigido acíclico:
Vértices = números da sequência S
Aresta (u,v): se u < v e u aparece antes de v na sequência S
subsequência crescente mais longa = caminho mais longo no grafo
Como usar a técnica de PD para
resolver o problema ?
1. Precisamos encontrar os subproblemas
2. Ordenar os subproblemas em ordem crescente
3. Encontrar uma função que opera sobre resultados de subproblemas já
resolvidos em etapas i < k, a fim de resolver o problema da etapa k
v0
v7
L(7) = comprimento do caminho mais longo finalizando no vértice v7 =
1 + max{L(0), L(1), L(3), L(4), L(5)}
Solução usando PD
1. Constrói grafo reverso GR= (V,ER)
2. Para todo j =1,2,...,n
3.
Se Lista de adjacências (em GR ) do vértice j ≠
4.
L(j) = 1 + max{ L(i): (j,i)  ER}
5.
L(j) = 0
6. Retorna max{L(j): j = 1,...,n}
L(j) = comprimento do caminho mais longo finalizando em j = subsequência
crescente mais longa finalizando em j.
Análise de Complexidade
Constrói Grafo reverso GR: O(|E| + |V|)
Complexidade:
O(|V| + |E|) + O(n)
Varre os vértices para determinar
max{L(j): j = 1,...,n
Varre os vértices em ordem crescente de GR e as listas de
adjacências de cada vértice de GR
Pior caso: sequência original está ordenada em ordem crescente
|E| = |V|2
Complexidade = O(|V|2)
Recursão versus PD
Pior Caso: a sequência está ordenada em ordem crescente.
ARVORE DE
RECURSÃO
Profundidade = n
Nr. de nós = O(2n)
Complexidade = O(2|V|)
Execuções Repetidas !!!