Aula nº 14 – 27/11/2000

(Continuação de Dynamic Programing)

Índice

ÁRVORE DE EXPRESSÃO

TRIANGULAÇÃO DE POLIGONOS

Árvore de expressão

Podemos passar os valores da tabela para uma árvore.

Com as matrizes A1 A2 A3 A4 temos a seguinte árvore:

A1 A2 A3 A4

A1 A2A3A4 A1 A2 A3 A4 A1 A2 A3 A4

A2A3 A4 A2 A3A4 A1 A2 A3 A4 A1 A2A3 A1A2 A3

A2 A3 A3 A4 A2 A3 A1 A2

Depois de calcularmos os primeiros A2A3, A3A4 e A1A2 já não é necessário calcular os subproblemas idênticos, porque já guardou esse valor.

Quando temos um problema recursivo, para o melhor usarmos o Dynamic Programing para fazer a memorização dos resultados, melhorando assim a complexidade do algoritmo.

Como sabemos se podemos utilizar o Dynamic Programing ?

O Dynamic Programing serve para resolver problemas que sejam para minimizar.

Outro dos subproblemas em que o Dynamic Programing é usado é triangulação de poligonos.

Voltar ao início

Triangulação de polígonos

Exemplo:

Poligono com 6 vértices.

Algumas triangulações possíveis:

1-

2-

3-

è Quantos triângulos tem um poligono?

No exemplo tem 4.

Para n vértices vamos obter n-2 triângulos e n-3 arestas.

A distância entre as arestas interiores é que varia.

Temos muitas triangulações possíveis , logo para acharmos o óptimo temos que dar valores (pesos) às arestas.

Quando cortamos um subproblema, temos que ter a mesma natureza do problema.

V5 V4

V6

V3

V7

V1 V2

Custo global = C1+C2+|V1V4|+|v4V5|+|V5V1|= C1+C2+W(V1V4V5), em que W(V1V4V5) é o peso das arestas.

W(V1V4V5)

Se C1 é óptimo e C2 é óptimo, das arestas a solução é óptima.

Dado o polígono:

Vamos obter a seguinte árvore de expressão.

Voltar ao início