1 of 164

Técnicas de Análise de Algoritmo

Programação Dinâmica

Alysson Milanez

2 of 164

Na aula passada...

2

3 of 164

Na aula passada...

Divisão e conquista

​

3

4 of 164

Programação Dinâmica

4

5 of 164

Programação Dinâmica

Assim como o método de divisão e conquista, a programação dinâmica resolve problemas por meio da combinação de soluções para subproblemas.

​

O termo programação se refere a um método tabular, não a codificação em si - escrita de código.

5

6 of 164

Programação Dinâmica

Como vimos na aula passada, os algoritmos de divisão e conquista particionam o problema em subproblemas independentes, resolvem os subproblemas recursivamente, e então combinam suas soluções para resolver o problema original.

6

7 of 164

Programação Dinâmica

Por outro lado, a programação dinâmica é aplicável quando os subproblemas não são independentes, isto é, quando há compartilhamento de subproblemas pelos subproblemas.

7

8 of 164

Programação Dinâmica

Nesse contexto, um algoritmo de divisão e conquista trabalha mais que o necessário, resolvendo repetidamente os subproblemas comuns.

​

Um algoritmo de programação dinâmica resolve cada subproblema uma vez só e então grava sua resposta em uma tabela, evitando assim o trabalho de recalcular a resposta toda vez que o subproblema é encontrado.

8

9 of 164

Programação Dinâmica

A programação dinâmica em geral é aplicada a problemas de otimização.

​

Em tais problemas, pode haver muitas soluções possíveis. Cada solução tem um valor, e desejamos encontrar uma solução com um valor ótimo (mínimo ou máximo).

9

10 of 164

Programação Dinâmica

Chamamos tal solução uma solução ótima para o problema, em lugar de a chamarmos a solução ótima, pois podem existir várias soluções que alcançam o valor ótimo.

10

11 of 164

Programação Dinâmica

Um algoritmo de programação dinâmica pode ser dividido em quatro etapas:

  1. Caracterizar a estrutura de uma solução ótima.

11

12 of 164

Programação Dinâmica

Um algoritmo de programação dinâmica pode ser dividido em quatro etapas:

  • Caracterizar a estrutura de uma solução ótima.
  • Definir recursivamente o valor de uma solução ótima.

12

13 of 164

Programação Dinâmica

Um algoritmo de programação dinâmica pode ser dividido em quatro etapas:

  • Caracterizar a estrutura de uma solução ótima.
  • Definir recursivamente o valor de uma solução ótima.
  • Calcular o valor de uma solução ótima em um processo de baixo para cima (bottom-up).

13

14 of 164

Programação Dinâmica

Um algoritmo de programação dinâmica pode ser dividido em quatro etapas:

  • Caracterizar a estrutura de uma solução ótima.
  • Definir recursivamente o valor de uma solução ótima.
  • Calcular o valor de uma solução ótima em um processo de baixo para cima (bottom-up).
  • Construir uma solução ótima a partir de informações calculadas.

14

15 of 164

Programação Dinâmica

As etapas 1 a 3 formam a base de uma solução de programação dinâmica para um problema.

​

A etapa 4 pode ser omitida se apenas o valor de uma solução ótima é exigido.

15

16 of 164

Programação Dinâmica

Quando executamos a etapa 4, às vezes mantemos informações adicionais durante a computação na etapa 3, a fim de facilitar a construção de uma solução ótima.

16

17 of 164

Programação de linha de montagem

17

18 of 164

Programação de linha de montagem

Nosso primeiro exemplo de programação dinâmica resolve um problema industrial.

​

A C. Motors Co. produz automóveis em uma fábrica que tem duas linhas de montagem.

​

​

18

19 of 164

Programação de linha de montagem

19

20 of 164

Programação de linha de montagem

Um chassi de automóvel entra em cada linha de montagem, tem as peças adicionadas a ele em uma série de estações, e um automóvel pronto sai no final da linha.

​

Cada linha de montagem tem n estações, numeradas com j = 1, 2, ..., n.

​

20

21 of 164

Programação de linha de montagem

Denotamos a j-ésima estação na linha i (onde i é 1 ou 2) por Si,j. A j-ésima estação na linha 1 (S1,j) executa a mesma função que a j-ésima estação na linha 2 (S2,j). Porém, as estações foram construídas em épocas diferentes e com tecnologias diferentes, de forma que o tempo exigido em cada estação varia, até mesmo entre as estações na mesma posição nas duas linhas.

21

22 of 164

Programação de linha de montagem

Denotamos o tempo de montagem exigido na estação Si,j por ai,j.

​

Como mostra a figura, um chassi entra na estação 1 de uma das linhas de montagem e avança de cada estação para a seguinte. Também há um tempo de entrada ei para o chassi entrar na linha de montagem i, e um tempo de saída xi para o automóvel concluído sair da linha de montagem i.

22

23 of 164

Programação de linha de montagem

23

24 of 164

Programação de linha de montagem

Um vez que um chassi entra em uma linha de montagem, ele percorre apenas essa linha. O tempo para ir de uma estação à seguinte dentro da mesma linha de montagem é desprezível. Às vezes, chega um pedido especial de urgência, e o cliente quer que o automóvel seja fabricado o mais rápido possível.

24

25 of 164

Programação de linha de montagem

Para pedidos de urgência, o chassi passa ainda pelas n estações em ordem, mas o gerente da fábrica pode passar o automóvel parcialmente concluído de uma linha de montagem para a outra após qualquer estação. O tempo para transferir um chassi da linha de montagem i depois da passagem pela estação Si,j é ti,j, onde i = 1,2 e j = 1,2,...,n-1 (pois, após a n-ésima estação, a montagem se completa).

25

26 of 164

Programação de linha de montagem

O problema é determinar que estações escolher na linha 1 e quais escolher na linha 2 para minimizar o tempo total de passagem de um único automóvel pela fábrica.

​

Na figura a seguir o tempo total mais rápido resulta da escolha das estações 1, 3 e 6 da linha 1 e das estações 2, 4 e 5 da linha 2.

26

27 of 164

Programação de linha de montagem

27

28 of 164

Programação de linha de montagem

A maneira óbvia, de "força bruta", de minimizar o tempo de passagem pela fábrica é inviável quando existem muitas estações. Se recebemos uma lista de quais estações usar na linha 1 e quais usar na linha 2, é fácil calcular no tempo Θ(n) quanto tempo um chassi demora para passar pela fábrica.

28

29 of 164

Programação de linha de montagem

Infelizmente, há 2n maneiras possíveis de escolher estações, o que observamos visualizando o conjunto de estações usadas na linha 1 como um subconjunto de {1,2,...,n} e notando que existem 2n subconjuntos.

​

​

29

30 of 164

Programação de linha de montagem

Desse modo, a determinação do caminho mais rápido pela fábrica enumerando todos os modos possíveis e calculando quanto tempo cada um deles demora exigiria o tempo Ω(2n), que é inviável quando n é grande.

30

31 of 164

Programação de linha de montagem

Etapa 1: A estrutura do caminho mais rápido pela fábrica

​

A primeira etapa do paradigma de programação dinâmica é caracterizar a estrutura de uma solução ótima. Para o problema de programação de linha de montagem, podemos executar essa etapa como a seguir. Vamos considerar o modo mais rápido possível para um chassi seguir desde o ponto de partida passando pela estação S1,j.

31

32 of 164

Programação de linha de montagem

Se j = 1, só existe um caminho que o chassi poderia ter seguido, e é fácil descobrir quanto tempo ele demora para passar pela estação S1,j. Contudo, para j = 2, 3, ..., n, há duas opções: o chassi poderia vir da estação S1,j-1 e depois seguir diretamente para a estação S1,j, sendo desprezível o tempo para ir da estação j-1 para a estação j na mesma linha.

32

33 of 164

Programação de linha de montagem

Como alternativa, o chassi poderia vir da estação S2,j-1 e depois ser transferido para a estação S1,j, sendo o tempo de transferência t2,j-1. Vamos considerar essas duas possibilidades separadamente, mas veremos que elas têm muito em comum.

33

34 of 164

Programação de linha de montagem

Primeiro, vamos supor que o caminho mais rápido passando pela estação S1,j seja pela estação S1,j-1. A observação fundamental é que o chassi deve ter tomado um caminho mais rápido desde o ponto de partida e através da estação S1,j-1.

​

Por quê?

34

35 of 164

Programação de linha de montagem

Se houvesse um caminho mais rápido através da estação S1,j-1, poderíamos utilizar esse caminho mais rápido como substituto para produzir um caminho mais rápido pela estação S1,j: uma contradição.

35

36 of 164

Programação de linha de montagem

De modo semelhante, vamos supor agora que a passagem mais rápida pela estação S1,j seja feita pela estação S2,j-1.

​

Observamos que chassi deve ter tomado um caminho mais rápido desde o ponto de partida, passando pela estação S2, j-1.

36

37 of 164

Programação de linha de montagem

O raciocínio é o mesmo: se existisse um caminho mais rápido passando pela estação S2,j-1, poderíamos utilizar esse caminho mais rápido como substituto para produzir uma passagem mais rápida através da estação S1,j, o que seria uma contradição.

37

38 of 164

Programação de linha de montagem

Em termos mais gerais, podemos dizer que, no caso da programação da linha de montagem, uma solução ótima para um problema (encontrar o caminho mais rápido passando pela estação S1,j) contém em seu interior uma solução ótima para subproblemas (encontrar a passagem mais rápida por S1, j-1 ou S2, j-1).

38

39 of 164

Programação de linha de montagem

Vamos nos referir a essa propriedade como Subestrutura ótima, e ela é uma das indicações da aplicabilidade da programação dinâmica.

39

40 of 164

Programação de linha de montagem

Usamos a subestrutura ótima para mostrar que podemos construir uma solução ótima para um problema a partir de soluções ótimas para subproblemas. No caso da programação da linha de montagem, o raciocínio é dado a seguir.

Se examinarmos um caminho mais rápido através da estação S1,j, ele tem de passar pela estação j-1 na linha 1 ou na linha 2.

40

41 of 164

Programação de linha de montagem

Desse modo, o caminho mais rápido pela estação S1,j é:

  • O caminho mais rápido pela estação S1,j-1, e depois diretamente pela estação S1,j.
  • O caminho mais rápido pela estação S2,j-1, uma transferência da linha 2 para a linha 1, e depois através da estação S1,j.

41

42 of 164

Programação de linha de montagem

Usando o raciocínio simétrico, o caminho mais rápido através da estação S2,j é:

  • O caminho mais rápido pela estação S2,j-1, e depois diretamente pela estação S2,j.
  • O caminho mais rápido pela estação S1,j-1, uma transferência da linha 1 para a linha 2, e depois através da estação S2,j.

42

43 of 164

Programação de linha de montagem

Para resolver o problema de encontrar o caminho mais rápido através da estação j de uma das linhas, resolvemos os subproblemas de encontrar os caminhos mais rápidos pela estação j-1 em ambas as linhas.

43

44 of 164

Programação de linha de montagem

Desse modo, podemos elaborar uma solução ótima para uma instância do problema de programação da linha de montagem pela elaboração de soluções ótimas para subproblemas.

44

45 of 164

Programação de linha de montagem

Etapa 2: Uma solução recursiva

​

A segunda etapa do paradigma de programação dinâmica é definir recursivamente o valor de uma solução ótima em termos das soluções ótimas para subproblemas.

45

46 of 164

Programação de linha de montagem

No caso do problema de programação da linha de montagem, escolhemos como nossos subproblemas os problemas de encontrar o caminho mais rápido pela estação j em ambas as linhas, para j= 1, 2, ..., n.

​

Seja fi[j] o tempo mais rápido possível para levar um chassi desde o ponto de partida até a estação Si,j.

46

47 of 164

Programação de linha de montagem

Nosso objetivo final é descobrir o tempo mais rápido para levar um chassi por todo o percurso na fábrica, que denotamos por f*. O chassi tem de passar por todo o caminho até a estação n na linha 1 ou na linha 2, e depois até a saída da fábrica.

47

48 of 164

Programação de linha de montagem

Tendo em vista que o mais rápido desses caminhos é o caminho mais rápido através da fábrica inteira, temos

​

f* = min(f1[n] + x1, f2[n] + x2)

48

49 of 164

Programação de linha de montagem

Também é fácil raciocinar sobre f1[1] e f2[1]. Para chegar até a estação 1 em qualquer linha, basta um chassi ir diretamente até essa estação. Assim,

​

f1[1] = e1 + a1,1,

f2[1] = e2 + a2,1.

49

50 of 164

Programação de linha de montagem

Agora, vamos considerar como calcular fi[j] para j = 2, 3, ..., n (e i = 1, 2). Concentrando nossa atenção em f1[j], lembramos que o caminho mais rápido pela estação S1,j é o caminho mais rápido pela estação S1,j-1, e depois diretamente pela estação S1,j, ou o caminho mais rápido pela estação S2,j-1, uma transferência da linha 2 para a linha 1, e depois pela estação S1,j.

50

51 of 164

Programação de linha de montagem

No primeiro caso, temos f1[j]= f1[j-1] + a1,j e, no último caso, f1[j]= f2[j-1] + t2,j-1 + a1,j. Desse modo,

​

f1[j] = min(f1[j-1] + a1,j, f2[j-1] + t2,j-1 + a1,j).

​

para j= 2, 3, ..., n.

51

52 of 164

Programação de linha de montagem

Simetricamente, temos

​

f2[j]= min(f2[j-1] + a2,j, f1[j-1] + t1,j-1 + a2,j).

​

para j= 2, 3, ..., n. Combinando essas equações, obtemos as equações recursivas

​

​

52

53 of 164

Programação de linha de montagem

53

54 of 164

Programação de linha de montagem

Os valores de fi[j] e f* para a instância apresentada a seguir.

54

55 of 164

Programação de linha de montagem

55

56 of 164

Programação de linha de montagem

Os fi[j] valores fornecem os valores de soluções ótimas para subproblemas. Para nos ajudar a acompanhar a construção de uma solução ótima, vamos definir li[j] como o número da linha, 1 ou 2, cuja estação j-1 é usada em um caminho mais rápido pela estação Si,j. Aqui, i = 1,2 e j = 2,3,...,n. (Não definimos li[1] porque nenhuma estação precede a estação 1 em qualquer linha).

56

57 of 164

Programação de linha de montagem

Os valores de li[j] e l* para a instância apresentada a seguir.

57

58 of 164

Programação de linha de montagem

58

59 of 164

Programação de linha de montagem

Também definimos l* como a linha cuja estação n é usada em um caminho mais rápido pela fábrica inteira. Os li[j] valores nos ajudam a acompanhar um caminho mais rápido. Usando os valores de l* e li[j] mostrados anteriormente, seria possível acompanhar um caminho mais rápido pela fábrica mostrada na figura como a seguir.

​

​

59

60 of 164

Programação de linha de montagem

Começando com l* = 1, usamos a estação S1,6. Agora, examinamos l1[6], que é 2, e então usamos a estação S2,5. Continuando, examinamos l2[5] = 2 (usamos a estação S2,4), l2[4] = 1 (estação S1,3), l1[3] = 2 (estação S2,2) e l2[2] = 1 (estação S1,1).

60

61 of 164

Programação de linha de montagem

Etapa 3: Cálculo dos tempos mais rápidos

​

Nesse ponto, seria uma simples questão de escrever um algoritmo recursivo baseado na equação [f* = min(f1[n] + x1, f2[n] + x2)] e nas recorrências para calcular o caminho mais rápido pela fábrica.

61

62 of 164

Programação de linha de montagem

Existe um problema com tal algoritmo recursivo: seu tempo de execução é exponencial em n. Para ver por que, seja ri(j) o número de referências feitas a fi[j] em um algoritmo recursivo. A partir da equação, temos

​

r1(n) = r2(n) = 1.

62

63 of 164

Programação de linha de montagem

Pelas recorrências temos

r1(j) = r2(j) = r1(j+1) + r2(j+1)

​

para j = 1,2,...,n-1. ri(j) = 2n-j. Portanto, f1[1] sozinho é referenciado 2n-1 vezes.

​

O número total de referências a todos os fi[j] valores é Θ(2n).

63

64 of 164

Programação de linha de montagem

Podemos fazer muito melhor se calcularmos os fi[j] valores em uma ordem diferente do modo recursivo. Observe que, para j >= 2, cada valor de fi[j] depende apenas dos valores de f1[j-1] e f2[j-1]. Calculando os fi[j] valores na ordem de números de estação j crescentes - da esquerda para a direita, podemos calcular o caminho mais rápido pela fábrica e o tempo que ele demora, no tempo Θ(n).

64

65 of 164

Programação de linha de montagem

O procedimento FASTEST-WAY toma como entrada os valores ai,j, ti,j, ei e xi, bem como n, o número de estações em cada linha de montagem.

65

66 of 164

Programação de linha de montagem

FASTEST-WAY(a,t,e,x,n){

f1[1] = e1 + a1,1

f2[1] = e2 + a2,1

for j = 2 to n do {

if f1[j-1] + a1,j <= f2[j-1] + t2,j-1 + a1,j then

f1[j] = f1[j-1] + a1,j

l1[j] = 1

else

f1[j] = f2[j-1] + t2,j-1 + a1,j

l1[j] = 2

66

67 of 164

Programação de linha de montagem

if f2[j-1] + a2,j <= f1[j-1] + t1,j-1 + a2,j then

f2[j] = f2[j-1] + a2,j

l2[j] = 2

else

f2[j] = f1[j-1] + t1,j-1 + a2,j

l2[j] = 1

}

67

68 of 164

Programação de linha de montagem

if f1[n] + x1 <= f2[n] + x2 then

f* = f1[n] + x1

l* = 1

else

f* = f2[n] + x2

l* = 2

}

68

69 of 164

Programação de linha de montagem

FASTEST-WAY funciona como a seguir. Inicialmente f1[1] e f2[1] são calculados.

​

FASTEST-WAY(a,t,e,x,n){

f1[1] = e1 + a1,1

f2[1] = e2 + a2,1

69

70 of 164

Programação de linha de montagem

Em seguida, o laço for calcula fi[j] e li[j] para i = 1,2 e j = 2,3,...,n.

​

70

71 of 164

Programação de linha de montagem

Inicialmente são calculados os valores de f1[j] e l1[j] usando a equação f1[j] = min(fi[j-1] + a1,j, f2[j-1] + t2,j-1 + a1,j).

for j = 2 to n do {

if f1[j-1] + a1,j <= f2[j-1] + t2,j-1 + a1,j then

f1[j] = f1[j-1] + a1,j

l1[j] = 1

else

f1[j] = f2[j-1] + t2,j-1 + a1,j

l1[j] = 2

71

72 of 164

Programação de linha de montagem

Depois são calculados os valores de f2[j] e l2[j] usando a equação f2[j]= min(f2[j-1] + a2,j, f1[j-1] + t1,j-1 + a2,j).

​

if f2[j-1] + a2,j <= f1[j-1] + t1,j-1 + a2,j then

f2[j] = f2[j-1] + a2,j

l2[j] = 2

else

f2[j] = f1[j-1] + t1,j-1 + a2,j

l2[j] = 1

}

72

73 of 164

Programação de linha de montagem

Por fim, f* e l* são calculadas.

​

if f1[n] + x1 <= f2[n] + x2 then

f* = f1[n] + x1

l* = 1

else

f* = f2[n] + x2

l* = 2

​

73

74 of 164

Programação de linha de montagem

Como as partes de fora do laço demoram um tempo constante, e como cada uma das n-1 iterações do laço for demora tempo constante, o procedimento inteiro demora o tempo Θ(n).

74

75 of 164

Programação de linha de montagem

Um modo de visualizar o processo de computação dos valores de fi[j] e li[j] é como se estivéssemos preenchendo entradas de tabelas. Preenchemos a tabela contendo valores de fi[j] e li[j] da esquerda para a direita (e de cima para baixo dentro de cada coluna). Para preencher uma entrada fi[j], precisamos dos valores de f1[j-1] e f2[j-1] e, sabendo que já calculamos e armazenamos esses valores, nós os descobrimos simplesmente observando a tabela.

75

76 of 164

Programação de linha de montagem

Etapa 4: Construção do caminho mais rápido pela fábrica

​

Tendo calculado os valores de fi[j], f*, li[j] e l*, precisamos construir a sequência de estações usadas no caminho mais rápido pela fábrica.

​

O procedimento a seguir imprime as estações usadas, em ordem decrescente de número de estação.

76

77 of 164

Programação de linha de montagem

PRINT-STATIONS(l,n){

i = l*

imprimir "linha" i ", estação " n

for j = n downto 2 do

i = li[j]

imprimir "linha" i ", estação " j-1

}

77

78 of 164

Programação de linha de montagem

Aplicando PRINT-STATIONS sobre este exemplo

78

79 of 164

Programação de linha de montagem

Obtemos

linha 1, estação 6

linha 2, estação 5

linha 2, estação 4

linha 1, estação 3

linha 2, estação 2

linha 1, estação 1

79

80 of 164

Multiplicação de cadeias de matrizes

80

81 of 164

Multiplicação de cadeias de matrizes

Nesse exemplo veremos o uso de programação dinâmica para resolver o problema de multiplicação de cadeias de matrizes.

​

Recebemos uma sequência/cadeia <A1, A2, ... An> de n matrizes a serem multiplicadas e desejamos calcular o produto

A1.A2...An

81

82 of 164

Multiplicação de cadeias de matrizes

Podemos avaliar a expressão A1.A2...An usando o algoritmo padrão de pares de matrizes como uma sub-rotina, uma vez que o tenhamos colocado entre parênteses para solucionar todas as ambiguidades no modo como as matrizes são multiplicadas entre si.

82

83 of 164

Multiplicação de cadeias de matrizes

Um produto de matrizes é completamente colocado entre parênteses se ele for uma única matriz ou produto de dois produtos de matrizes completamente colocados entre parênteses, cercado por parênteses. A multiplicação de matrizes é associativa, e assim todas as colocações entre parênteses resultam no mesmo produto.

83

84 of 164

Multiplicação de cadeias de matrizes

Por exemplo, se a cadeia de matrizes é <A1, A2, A3, A4>, o produto A1.A2.A3.A4 pode ser completamente colocado entre parênteses de cinco modos distintos:

(A1(A2(A3A4)))

​

84

85 of 164

Multiplicação de cadeias de matrizes

Por exemplo, se a cadeia de matrizes é <A1, A2, A3, A4>, o produto A1.A2.A3.A4 pode ser completamente colocado entre parênteses de cinco modos distintos:

(A1(A2(A3A4)))

(A1((A2A3)A4))

​

85

86 of 164

Multiplicação de cadeias de matrizes

Por exemplo, se a cadeia de matrizes é <A1, A2, A3, A4>, o produto A1.A2.A3.A4 pode ser completamente colocado entre parênteses de cinco modos distintos:

(A1(A2(A3A4)))

(A1((A2A3)A4))

((A1A2)(A3A4))

​

86

87 of 164

Multiplicação de cadeias de matrizes

Por exemplo, se a cadeia de matrizes é <A1, A2, A3, A4>, o produto A1.A2.A3.A4 pode ser completamente colocado entre parênteses de cinco modos distintos:

(A1(A2(A3A4)))

(A1((A2A3)A4))

((A1A2)(A3A4))

((A1(A2A3))A4)

​

87

88 of 164

Multiplicação de cadeias de matrizes

Por exemplo, se a cadeia de matrizes é <A1, A2, A3, A4>, o produto A1.A2.A3.A4 pode ser completamente colocado entre parênteses de cinco modos distintos:

(A1(A2(A3A4)))

(A1((A2A3)A4))

((A1A2)(A3A4))

((A1(A2A3))A4)

(((A1A2)A3)A4)

88

89 of 164

Multiplicação de cadeias de matrizes

O modo como uma cadeia de matrizes é colocada entre parênteses tem alto impacto no custo da avaliação do produto. Consideremos primeiro o custo de multiplicar duas matrizes. Um algoritmo é apresentado a seguir. Os atributos linhas e colunas são os números de linhas e colunas em uma matriz.

89

90 of 164

Multiplicação de cadeias de matrizes

MATRIX-MULTIPLY(A, B)

if colunas[A] != linhas[B] then

error "dimensões incompatíveis"

else

for i = 1 to linhas[A] do

for j = 1 to colunas[B] do

C[i, j] = 0

for k = 1 to colunas[A] do

C[i, j] = C[i,j] + A[i,k].B[k,j]

return C

90

91 of 164

Multiplicação de cadeias de matrizes

Podemos multiplicar duas matrizes A e B somente se elas forem compatíveis: o número de colunas de A deve ser igual ao número de linhas de B.

​

Se A é uma matriz pxq e B é uma matriz qxr, a matriz resultante C é uma matriz pxr.

91

92 of 164

Multiplicação de cadeias de matrizes

O tempo para calcular C é dominado pelo número de multiplicações escalares no interior do 3º laço, que é p.q.r.

​

for i = 1 to linhas[A] do

for j = 1 to colunas[B] do

C[i, j] = 0

for k = 1 to colunas[A] do

C[i, j] = C[i,j] + A[i,k].B[k,j]

92

93 of 164

Multiplicação de cadeias de matrizes

Para ilustrar os diferentes custos resultantes da colocação dos parênteses de um produto de matrizes de maneiras distintas, consideremos o problema de uma cadeia <A1, A2, A3> de três matrizes.

​

Suponhamos que as dimensões sejam: 10x100, 100x5 e 5x50, respectivamente.

93

94 of 164

Multiplicação de cadeias de matrizes

Se multiplicarmos as matrizes de acordo com a colocação dos parênteses ((A1A2)A3), executaremos 10.100.5 = 5.000 multiplicações escalares para calcular o produto de matrizes A1A2 10 x 5, mais outras 10.5.50 = 2.500 multiplicações escalares para multiplicar essa matriz por A3, produzindo um total de 7.500 multiplicações escalares.

94

95 of 164

Multiplicação de cadeias de matrizes

Se, em vez disso, multiplicarmos de acordo com a colocação dos parênteses (A1(A2A3)), executamos 100.5.50 = 25.000 multiplicações escalares para calcular o produto de matrizes A2A3 100x50, mais outras 10.100.50 = 50.000 multiplicações escalares para multiplicar A1 por essa matriz, dando um total de 75.000 multiplicações escalares.

​

95

96 of 164

Multiplicação de cadeias de matrizes

Desse modo, o cálculo do produto de acordo com a primeira colocação dos parênteses é 10 vezes mais rápido.

96

97 of 164

Multiplicação de cadeias de matrizes

O problema de multiplicação de cadeias de matrizes pode ser assim enunciado: dada uma cadeia <A1, A2, ..., An> de n matrizes na qual para i = 1,2,...,n, a matriz Ai tem dimensão pi-1pi, coloque completamente entre parênteses o produto A1A2...An de modo que minimize o número de multiplicações escalares.

97

98 of 164

Multiplicação de cadeias de matrizes

Observem que nesse problema não estamos realmente multiplicando matrizes, nossa meta é apenas determinar uma ordem para multiplicá-las com o custo mais baixo. Em geral, o tempo investido para determinar essa ordem ótima é compensado pelo tempo economizado na hora de realmente multiplicar as matrizes.

98

99 of 164

Multiplicação de cadeias de matrizes

Etapa 1: A estrutura de uma colocação ótima dos parênteses

​

A primeira etapa do paradigma PD é encontrar a subestrutura ótima, e depois usá-la para construir uma solução ótima para o problema a partir de soluções ótimas para subproblemas.

99

100 of 164

Multiplicação de cadeias de matrizes

Para este problema, podemos executar essa etapa do seguinte modo: Por comodidade, adotaremos a notação Ai,j, onde i <= j para a matriz que resulta da avaliação do produto Ai.Ai+1...Aj.

​

Se o problema é não trivial, isto é, i < j, qualquer colocação ótima dos parênteses do produto AiAi+1...Aj deve dividir o produto entre Ak e Ak+1 para algum inteiro k: i <= k < j.

100

101 of 164

Multiplicação de cadeias de matrizes

Ou seja, para algum valor de k, primeiro calculamos as matrizes Ai..k e Ak+1..j, e depois multiplicamos os dois para gerar o produto final Ai..j.

​

O custo dessa colocação dos parênteses é portanto o custo de calcular a matriz Ai..k, mais o custo de calcular Ak+1..j, mais o custo de multiplicá-las uma pela outra.

101

102 of 164

Multiplicação de cadeias de matrizes

A subestrutura ótima é a seguinte: Suponha que uma colocação dos parênteses de AiAi+1...Aj divida o produto entre Ak e Ak+1. Então, a colocação dos parênteses da subcadeia "prefixo" AiAi+1...Ak dentro dessa colocação ótima dos parênteses de AiAi+1...Aj deve ser uma colocação ótima dos parênteses de AiAi+1...Ak.

​

Por quê?

102

103 of 164

Multiplicação de cadeias de matrizes

Se existisse um modo menos dispendioso de colocar entre parênteses AiAi+1...Ak, a substituição dessa colocação dos parênteses na colocação ótima dos parênteses AiAi+1...Aj produziria outra colocação dos parênteses de AiAi+1...Aj cujo custo seria mais baixo que o custo ótimo: uma contradição.

103

104 of 164

Multiplicação de cadeias de matrizes

Uma observação similar é válida para a colocação dos parênteses da subcadeia Ak+1Ak+2...Aj na colocação ótima dos parênteses de AiAi+1...Aj: ela deve ser uma colocação ótima dos parênteses de Ak+1Ak+2...Aj.

104

105 of 164

Multiplicação de cadeias de matrizes

Agora podemos usar nossa subestrutura ótima para construir uma solução ótima para o problema a partir dos subproblemas.

​

Qualquer solução para instâncias não triviais do problema nos leva a dividir o produto e qualquer solução ótima contém dentro dela soluções ótimas para os subproblemas.

105

106 of 164

Multiplicação de cadeias de matrizes

Desse modo, podemos construir uma solução ótima para uma instância do problema dividindo-o em dois subproblemas, encontrando soluções ótimas para instâncias de subproblemas, e depois combinando essas soluções. Precisamos assegurar que consideraremos todos os lugares possíveis para a divisão do produto, de forma a garantirmos a opção ótima.

106

107 of 164

Multiplicação de cadeias de matrizes

Etapa 2: Uma solução recursiva

​

No caso desse problema, escolhemos como nossos subproblemas os problemas de determinar o custo mínimo de uma colocação de parênteses de Ai...Aj para 1 <= i <= j <= n. Seja m[i,j] o número mínimo de multiplicações escalares necessárias para calcular a matriz Ai..j, para o problema completo, o custo de um caminho mais econômico seria portanto m[1,n].

107

108 of 164

Multiplicação de cadeias de matrizes

Podemos definir m[i,j] recursivamente: Se i == j, o problema é trivial; a cadeia consiste em apenas uma matriz Ai..i = Ai, não sendo necessárias multiplicações escalares para o cálculo do produto.

​

Desse modo, m[i,j] = 0 para i = 1,2,...,n. Para calcular m[i,j] quando i < j, tiramos proveito da estrutura de uma solução ótima da Etapa 1.

108

109 of 164

Multiplicação de cadeias de matrizes

Suponhamos que a colocação ótima dos parênteses divida o produto AiAi+1...Aj entre Ak e Ak+1, onde i <= k < j. Então, m[i,j] é igual ao custo mínimo para calcular os subprodutos Ai..k e Ak+1..j, mais o custo de multiplicar essas duas matrizes.

109

110 of 164

Multiplicação de cadeias de matrizes

Recordando que cada matriz Ai é pi-1pi, vamos que o cálculo do produto de matrizes Ai..kAk+1..j exige pi-1pkpj multiplicações escalares. Desse modo, obtemos

m[i,j] = m[i,k] + m[k+1,j] + pi-1pkpj.

110

111 of 164

Multiplicação de cadeias de matrizes

Essa equação recursiva pressupõe que conhecemos o valor de k, o que não ocorre. :(

​

Porém, há apenas j-i valores possíveis para k, isto é, k = i, i+1, ..., j-1. Como a colocação ótima dos parênteses deve usar um desses valores para k, precisamos apenas verificar todos eles para encontrar o melhor.

111

112 of 164

Multiplicação de cadeias de matrizes

Desse modo, nossa definição recursiva para o custo mínimo de colocar entre parênteses o produto AiAi+1...Aj se torna

0 se i = j

m[i,j] =

min{m[i,k] + m[k+1,j] + pi-1pkpj} se i < j

112

113 of 164

Multiplicação de cadeias de matrizes

Os valores de m[i,j] fornecem os custos de soluções ótimas para subproblemas. Para nos ajudar na construção de uma solução ótima, vamos definir s[i,j] como um valor de k no qual podemos dividir o produto AiAi+1...Aj para obter uma colocação ótima dos parênteses: s[i,j] é igual a um valor k tal que m[i,j] = m[i,k] + m[k+1,j] + pi-1pkpj.

113

114 of 164

Multiplicação de cadeias de matrizes

Etapa 3: Como calcular os custos ótimos

Vamos construir um algoritmo recursivo para calcular o custo mínimo m[1,n] para multiplicar as matrizes. No entanto, esse algoritmo demora um tempo exponencial - ele é igual ao método força bruta para verificar cada maneira de colocar o produto entre parênteses.

114

115 of 164

Multiplicação de cadeias de matrizes

O importante é vermos que temos relativamente poucos subproblemas: um problema para cada opção de i e j que satisfaz a 1 <= i <= j <= n, ou (n 2) + n = Θ(n2) no total.

​

115

116 of 164

Multiplicação de cadeias de matrizes

Um algoritmo recursivo pode encontrar cada subproblema muitas vezes em diferentes ramificações da árvore de recursão. Essa propriedade de superpor subproblemas é a segunda indicação da aplicabilidade da programação dinâmica.

116

117 of 164

Multiplicação de cadeias de matrizes

Em vez de calcular recursivamente a solução para a recorrência, executamos a terceira etapa do paradigma de programação dinâmica e calculamos o custo ótimo usando uma abordagem tabular de baixo para cima.

117

118 of 164

Multiplicação de cadeias de matrizes

O pseudocódigo MATRIX-CHAIN-ORDER pressupõe que a matriz Ai tem dimensões pi-1 X pi para i = 1,2,...,n. A entrada é uma sequência p = <p0,p1,...,pn>, onde comprimento[p] = n+1. O procedimento utiliza uma tabela auxiliar m[1..n,1..n] para armazenar os custos de m[i,j] e uma tabela auxiliar s[1..n, 1..n] que registra qual índice de k alcançou o custo ótimo no cálculo de m[i,j]. Usaremos s para construir uma solução ótima.

118

119 of 164

Multiplicação de cadeias de matrizes

Para implementar corretamente a abordagem de baixo para cima, precisamos determinar que entradas da tabela são usadas para calcular m[i,j]. A equação de recorrência mostra que o custo m[i,j] de calcular um produto de cadeias de matrizes para j-i+1 só depende dos custos de calcular os produtos de cadeias de matrizes de menos de j-i+1 matrizes.

119

120 of 164

Multiplicação de cadeias de matrizes

Isto é, para k = i, i+1, ..., j-1, a matriz Ai..k é um produto de k-i+1 < j-i+1 matrizes, e a matriz Ak+1..j é um produto de j-k < j-i+1 matrizes. Assim, o algoritmo deve preencher a tabela m de uma forma que corresponda a resolver o problema de colocação dos parênteses em cadeias de matrizes de comprimento crescente.

120

121 of 164

Multiplicação de cadeias de matrizes

MATRIX-CHAIN-ORDER(p)

n = comprimento[p]-1

for i = 1 to n do m[i,i] = 0

for l = 2 to n do // l eh o comprimento da cadeia

for i = 1 to n-l+1 do

j = i+l-1

m[i,j] = ∞

for k = i to j-1 do

q = m[i,k] + m[k+1,j] + pi-1pkpj

if q < m[i,j] then

m[i,j] = q

s[i,j] = k

return m e s

​

121

122 of 164

Multiplicação de cadeias de matrizes

O algoritmo calcula primeiro m[i,i] = 0 para i = 1, 2, ..., n (custos mínimos para cadeias de comprimento 1).

122

123 of 164

Multiplicação de cadeias de matrizes

MATRIX-CHAIN-ORDER(p)

n = comprimento[p]-1

for i = 1 to n do m[i,i] = 0

for l = 2 to n do // l eh o comprimento da cadeia

for i = 1 to n-l+1 do

j = i+l-1

m[i,j] = ∞

for k = i to j-1 do

q = m[i,k] + m[k+1,j] + pi-1pkpj

if q < m[i,j] then

m[i,j] = q

s[i,j] = k

return m e s

​

123

124 of 164

Multiplicação de cadeias de matrizes

Em seguida ele usa a recorrência para calcular m[i,i+1] para i = 1,2,...,n-1 (os custos mínimos para cadeias de comprimento l = 2) durante a primeira execução do segundo laço. Na segunda passagem, ele calcula os custos mínimos para cadeias de comprimento l = 3 e assim por diante. Em cada etapa, o custo m[i,j] calculado no quarto laço depende apenas das entradas de tabela m[i,k] e m[k+1,j] já calculadas.

​

124

125 of 164

Multiplicação de cadeias de matrizes

MATRIX-CHAIN-ORDER(p)

n = comprimento[p]-1

for i = 1 to n do m[i,i] = 0

for l = 2 to n do // l eh o comprimento da cadeia

for i = 1 to n-l+1 do

j = i+l-1

m[i,j] = ∞

for k = i to j-1 do

q = m[i,k] + m[k+1,j] + pi-1pkpj

if q < m[i,j] then

m[i,j] = q

s[i,j] = k

return m e s

​

125

126 of 164

Multiplicação de cadeias de matrizes

A figura ilustra esse procedimento em uma cadeia de n = 6 matrizes.

126

127 of 164

Multiplicação de cadeias de matrizes

As dimensões das matrizes são:

matriz dimensão

A1 30 x 35

A2 35 x 15

A3 15 x 5

A4 5 x 10

A5 10 x 20

A6 20 x 25

​

127

128 of 164

Multiplicação de cadeias de matrizes

Tendo em vista que definimos m[i,j] somente para i = j, apenas a porção da tabela m estritamente acima da diagonal principal é usada. Na figura a tabela é girada para fazer a diagonal principal ficar disposta horizontalmente. A cadeia de matrizes é listada ao longo da parte inferior.

​

128

129 of 164

Multiplicação de cadeias de matrizes

Usando-se esse layout, o custo mínimo m[i,j] para multiplicar uma subcadeia de matrizes pode ser encontrado na interseção de linhas dispostas a nordeste de Ai e a noroeste de Aj. Cada linha horizontal na tabela contém as entradas para cadeias de matrizes do mesmo comprimento.

129

130 of 164

Multiplicação de cadeias de matrizes

MATRIX-CHAIN-ORDER calcula as linhas desde a parte inferior até a parte superior e da esquerda para a direita dentro de cada linha. Inspecionando a estrutura dos laços aninhados podemos notar um tempo de execução O(n3). O algoritmo exige o espaço Θ(n2) para armazenar as tabelas m e s. Portanto, ele é muito mais eficiente que o método força bruta de enumerar todas as possíveis colocações de parênteses.

130

131 of 164

Multiplicação de cadeias de matrizes

Etapa 4: A construção de uma solução ótima

​

Embora MATRIX-CHAIN-ORDER determine o número ótimo de multiplicações escalares necessárias para calcular um produto de cadeias de matrizes, ele não mostra diretamente como multiplicá-las.

​

​

​

131

132 of 164

Multiplicação de cadeias de matrizes

Não é difícil construir uma solução ótima a partir das informações armazenadas na tabela s. Cada entrada s[i,j] registra o valor de k tal que a colocação ótima dos parênteses de Ai...Aj divide o produto entre Ak e Ak+1. Desse modo, sabemos que a multiplicação final no cálculo ótimo de A1..n, é A1..s[1,n]As[1,n+1]..n. Essas multiplicações podem ser calculadas recursivamente.

​

​

132

133 of 164

Multiplicação de cadeias de matrizes

O procedimento PRINT-OPTIMAL-PARENS imprime uma colocação ótima dos parênteses dada a tabela s calculada por MATRIX-CHAIN-ORDER e os índices i e j.

133

134 of 164

Multiplicação de cadeias de matrizes

PRINT-OPTIMAL-PARENS(s, i, j)

if i == j then print "A"i

else

print "("

PRINT-OPTIMAL-PARENS(s, i, s[i,j])

PRINT-OPTIMAL-PARENS(s, s[i,j]+1, j)

print ")"

​

134

135 of 164

Multiplicação de cadeias de matrizes

No exemplo da figura, a chamada a PRINT-OPTIMAL-PARENS(s, 1, 6) imprime a colocação dos parênteses ((A1(A2A3))((A4A5)A6)).

135

136 of 164

Elementos de Programação Dinâmica

136

137 of 164

Elementos de Programação Dinâmica

Embora já tenhamos visto dois exemplos do uso de programação dinâmica, vocês podem estar imaginando quando o método deve ser aplicado. Quando devemos buscar uma solução de programação dinâmica para um problema?

​

Veremos os dois elementos essenciais para que PD seja aplicável: subestrutura ótima e superposição de problemas.

137

138 of 164

Subestrutura ótima

O primeiro passo para resolver um problema de otimização por PD é caracterizar a estrutura de uma solução ótima. Um problema apresenta subestrutura ótima se uma solução ótima para o problema contém em seu interior soluções ótimas para subproblemas. Sempre que um problema apresenta uma subestrutura ótima, isso indica que PD poderia se aplicar.

138

139 of 164

Subestrutura ótima

Em PD, construímos uma solução ótima para o problema a partir de soluções ótimas para subproblemas. Em consequência, devemos assegurar que o intervalo de subproblemas que consideramos inclui os que são usados em uma solução ótima.

139

140 of 164

Subestrutura ótima

Padrão comum na descoberta de uma subestrutura ótima:

1. Mostrar que uma solução para o problema consiste em fazer uma escolha. Essa escolha deixa um ou mais subproblemas a serem resolvidos.

2. Supor que, para um dado problema, você tem a escolha que conduz a uma solução ótima.

140

141 of 164

Subestrutura ótima

3. Dada essa escolha, determinar quais subproblemas resultam dela e como caracterizar melhor o espaço de subproblemas resultante.

4. Mostrar que as soluções para os subproblemas devem ser ótimas, usando uma técnica de "recortar e colar". Para isso, supõe-se que as soluções dos subproblemas não são ótimas e deriva-se uma contradição.

141

142 of 164

Subestrutura ótima

Para caracterizar o espaço de subproblemas, uma boa regra prática é mantê-lo o mais simples possível e expandí-lo em caso de necessidade. A subestrutura ótima varia nos domínios de problemas de duas maneiras:

1. O número de subproblemas que são usados em uma solução ótima para o problema original;

2. O número de opções que temos para determinar de qual(is) subproblema(s) usar em uma solução ótima.

142

143 of 164

Subestrutura ótima

O tempo de execução de um algoritmo de PD depende do produto de dois fatores: o número de subproblemas globais e quantas escolhas observamos para cada subproblema.

​

PD usa a subestrutura ótima de baixo para cima: primeiro encontramos soluções ótimas para subproblemas e, resolvendo-os, encontramos uma solução ótima para o problema.

143

144 of 164

Subestrutura ótima - sutilezas

Devemos ter cuidado para não presumir que a subestrutura ótima é aplicável quando ela não o é.

144

145 of 164

Subproblemas superpostos

Um problema de otimização tem subproblemas superpostos quando um algoritmo recursivo reexamina o mesmo problema inúmeras vezes - o algoritmo resolve os mesmos subproblemas repetidas vezes ao invés de gerar novos subproblemas. Em geral, o número total de subproblemas distintos é um polinômio no tamanho de entrada.

​

​

​

145

146 of 164

Subproblemas superpostos

Em contraste, um problema para o qual uma abordagem de dividir e conquistar é satisfatória quase sempre gera problemas completamente novos em cada passo da recursão.

146

147 of 164

Subproblemas superpostos

Os algoritmos de PD costumam tirar proveito de subproblemas superpostos resolvendo cada subproblema uma vez, e depois armazenando a solução em uma tabela, onde ela possa ser examinada quando necessário, usando-se um tempo constante por pesquisa.

147

148 of 164

Subproblemas superpostos

Sempre que uma árvore de recursão para a solução recursiva natural para um problema contém o mesmo subproblema repetidamente, e o número total de subproblemas diferentes é pequeno, é interessante checar se a programação dinâmica é aplicável.

148

149 of 164

Memoização

149

150 of 164

Memoização

Variação de programação dinâmica que mantém a eficiência habitual mas faz uso de uma estratégia top-down. A ideia, embora ineficiente, é memoizar o algoritmo recursivo natural. Como na PD comum, mantemos uma tabela com soluções de subproblemas, mas a estrutura de controle para preencher a tabela é mais similar ao algoritmo recursivo.

150

151 of 164

Memoização

Um algoritmo recursivo memoizado mantém uma entrada em uma tabela para a solução de cada subproblema. Cada entrada da tabela contém inicialmente um valor especial para indicar que a entrada ainda tem de ser preenchida.

151

152 of 164

Memoização

Quando o subproblema é encontrado pela primeira vez, sua solução é calculada e depois armazenada na tabela. Em cada momento posterior em que o subproblema é encontrado, o valor armazenado é apenas pesquisado e retornado.

152

153 of 164

Memoização

MEMOIZED-MATRIX-CHAIN(p)

n = comprimento[p]-1

for i = 1 to n do

for j = i to n do

m[i,j] = ∞

return LOOKUP-CHAIN(p,1,n)

​

153

154 of 164

Memoização

LOOKUP-CHAIN(p, i, j)

if m[i,j] < ∞ then return m[i,j]

if i == j then m[i,i] = 0

else

for k = i to j-1 do

q = LOOKUP-CHAIN(p,i,k) + LOOKUP-CHAIN(p, k+1, j) + pi-1pkpj

if q < m[i,j] then m[i,j] = q

return m[i,j]

154

155 of 164

Memoização

MEMOIZED-MATRIX-CHAIN, como MATRIX-CHAIN-ORDER, mantém uma tabela m de valores calculados de m[i,j]. Inicialmente cada entrada da tabela contém o valor ∞ para indicar que a entrada ainda tem de ser preenchida. Quando LOOKUP-CHAIN é chamado, se m[i,j] < ∞, o procedimento simplesmente retorna o custo anteriormente calculado. Do contrário, o custo é calculado, armazenado em m[i,j] e retornado.

155

156 of 164

Memoização

Assim, LOOKUP-CHAIN sempre retorna o valor de m[i,j] mas só o calcula na primeira vez que é chamado com os parâmetros i e j.

156

157 of 164

Memoização

De modo similar ao algoritmo de PD, MEMOIZED-MATRIX-CHAIN é executado em O(n3).

​

Em resumo, o problema de multiplicação de cadeias de matrizes pode ser resolvido em tempo O(n3) seja por um algoritmo memoizado top-down ou por um bottom-up de programação dinâmica.

157

158 of 164

Resumindo...

158

159 of 164

Programação Dinâmica

A programação dinâmica se aplica tipicamente a problemas de otimização em que uma série de escolhas deve ser feita, a fim de se alcançar uma solução ótima.

​

​

159

160 of 164

Programação Dinâmica

À medida que as escolhas são feitas, frequentemente surgem subproblemas da mesma forma. A programação dinâmica é eficaz quando um dado subproblema pode surgir a partir de mais de um conjunto parcial de escolhas; a técnica chave é armazenar a solução para cada um desses subproblemas, prevendo-se a hipótese de ele reaparecer.

160

161 of 164

Referências

161

162 of 164

Referências

T. Cormen, C. Leiserson, R. Rivest, C. Stein. Algoritmos - Teoria e Prática (tradução da 2ª Ed. Americana), Ed. Campus (2002).

Capítulo 15

162

163 of 164

Referências

E. Horowitz, S. Sahni, S. Rajasekaran. Computer Algorithms.

Capítulo 5

​

M. Soltys. An Introduction to the Analysis of Algorithms. 2nd edition.

Capítulo 4

163

164 of 164

Técnicas de Análise de Algoritmo

Programação Dinâmica

Alysson Milanez