análise de algoritmos

RESUMO AA1

Programação Dinâmica – 4 PASSOS:
1 - Caracterizar a estrutura de uma solução ótima.
2 - Definir recursivamente o valor de uma solução ótima.
3 - Calcular o valor de uma solução ótima em um processo bottom-up.
4 - Construir a solução ótima a partir das informações já calculadas

1 – Escalonamento de Intervalos Ponderados
Dada uma coleção S de intervalos, encontrar uma subcoleção disjunta com o máximo valor possível.

Sub Estrutura Ótima:
Suponha que C seja um conjunto de intervalos que forma a solução ótima para um problema de {1,...,n} intervalos, então C tem valor máximo.
Mas além disso, C contém um subconjunto de intervalos C1 que representa um subproblema, então se C1 não for formado por intervalos disjuntos ou não apresentar valor máximo, é possível substituí-lo por um conjunto de intervalos disjuntos e com valor máximo.
Dessa forma C não teria valor máximo, portanto contradição. Se C é solução ótima, qualquer subproblema de C, será solução ótima.

Função recursiva: 0 se j = 0 OPT(j) = max(vj + OPT( p(j) ), OPT( j-1) )

Calcula-OPT-Iterativo { M[0] = 0 for j = 1 to n M[j] = Max( Vj + M[ p(j) ], M[ j-1 ] ) } Encontra_Solucao(j) { if (j = 0) nada else if (vj + M[ p(j) ] > M[ j-1 ]) print j Encontra_Solucao( p(j) ) else Encontra_Solucao( j-1 ) }

Ordenar os intervalos: O(nlogn)
Calcula-OPT-Iterativo: O(n)
Encontrar p: O(n²) ou O(nlogn)
Constrói Solução: O(n)
Espaço: O(n)

2 – Menor Caminho Entre Pares de Vértices
Dado um conjunto de vértices e arestas com pesos, deseja-se saber o menor caminho (menor custo) para cada par de vértices. Isto pode nos ajudar por exemplo a traçar rotas de viagens

SubEstrutura Ótima:
Seja p= um caminho mais curto entre o par de vértices v1 a vn. Seja i e j tais que