Parte 3 Técnicas de projeto de algoritmos. Setembro 2004Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro2 Divisão e conquista Algoritmos gulosos

Parte 3

Técnicas de projeto de algoritmos

Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 2

• Divisão e conquista• Algoritmos gulosos• Programação dinâmica• Caminhamento em grafos• Heurísticas

Técnicas de projeto de algoritmos

Divisão e conquista


function DC (x) se {x é suficientemente pequeno ou simples} então

return ADHOC(x)senão decompor x em x1, x2, …, xK

para i = 1 até K faça yi DC (xi); recombinar os yi para obter y return y


Top downRecorrenteBalanceamento

Pesquisa bináriaMerge Sort

Princípio básico:


Entrada: a1,, a2 , …, an Saída: MIN, MAXcom: MIN min { a1, a2 , … , an }

MAX= max{ a1, a2 , … , an }

trivial: determinar MIN: (n-1) comparações determinar MAX: (n-1) comparações

2n-2 comparações

melhorado:MIN, MAX a1

para i = 2 até n faça se ai > MAX então MAX ai

senão se ai < MIN então MIN ai

Máximo e mínimo

melhor caso: ai n-1 comparações

pior caso: ai 2n-1comparações


Máximo e mínimoprocedure MaxMin(i, j, fmax, fmin) integer i, jglobal n, A(1:n) case

: i=j fmax, fmin A(i) : i=j-1 se A(i) < A(j) então

fmax A(j) fmin A(i)

else fmax A(i) fmin A(j)

: else meio (i+j)/2 MaxMin(i, meio, gmax , gmin) MaxMin(meio+1, j, hmax , hmin) fmax max(hmax , gmax) fmin min(hmin , gmin)

endcase

T(n) = O(1) + 2·T(n/2)T(n) = O(n)



nOnT

OcnTnT

clog)1(

nOnT

OcnTcnT

)1(

acnOnT

caOcnTanTlog

com)1(

Pesquisa binária

max min

Multiplicação de polinômios

kcn



)(:

log:

:

log acnOnTca

nnOnTca

nOnTca

)(nOcnTanTcn k

mergesort

multiplicação de polinômios


Dado um vetor a1, a2, …, an obter o k-ésimo menor elemento

Problema de seleção

ai xai x

• ordenação: O(n log n) + O(k) • k pequeno: O(k·n)• É possível fazer melhor do que isso?

Reorganizar o vetor a em relação a um pivô x:


partition(A, p, r, x) i p-1j r+1

enquanto TRUE faça repita j j -1 até que A[j] x repita i i+1 até que A[i] x se i < j então troca A[i] ↔ A[j] senão retornar j

fim


A

p r

x

Complexidade: O(n)


jA[j] 5

Exemplo:

X = 5

A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] 5 3 2 6 4 1 3 7

jA[j] 5

3 5

iA[i] 5

iA[i] 5

iA[i] 5

ji jA[j] 5

1 6

iA[i] 5

jA[j] 5

iA[i] 5


Determinar o k-ésimo menor elemento:Se |P1| k procurar o k-ésimo em P1

Se |P1| k procurar o k-|P1| ésimo em P2

usar o algoritmo de partição


X X

P1 P2


Select(k,n):

1. Dividir os n elementos em n/5 grupos de 5 elementos cada.

2. Extrair a mediama de cada um dos n/5 grupos de 5 elementos cada.

3. Extrair recursivamente a mediana das n/5 medianas usando select: Select (n/10,n/5). Seja x esta mediana:




m1 m2 m3 m5 m6 m7X

103

5213: nnxElementos


4. Particionar os dados de entrada utilizando x como pivô usando o algoritmo partition

5. Sejam b1 e b2 o número de elementos em cada partição.Se k b1: aplicar select para obter o k-ésimo da 1a parteSe k > b1: aplicar select para obter o (k-b1)-ésimo da 2a parte(recursivamente)


nOnT

nOnTnTnT

nnTnOnTOnnOnT

1075

10351

5



“força bruta”:para i = 0 até 2n-2 faça

r(i) 0;para i = 0 até n-1 faça para j = 0 até n-1 faça

r(i+j) r(i+j) + p(i)·q(j); T(n) = O(n2)

Polinômio de grau n-1 tem n termos

11

2210

n

n xaxaxaa

Entrada: p(x) e q(x) têm tamanho nSaída : r(x)=p(x)·q(x)



n=2k

p(x) + q(x) O(n)p(x) · q(x) O(n2), computacionalmente mais caro

Idéia: substituir “·” por “+”

2

11011000

22101010

xbaxbababa

xcxccxbbxaa


201

1010

1

112

000

?

cccc

bbaac

c

bac

bac

aux

aux

a0b0

a0b1 a1b1

a1b0

a0+ a1

b0+b1

|b1 |b0 |

a0 a1

41

12 portroca



2/

1)2/(1)2/(2/

1)2/(10

2

2

1)2/(

1)2/(

12,

,1 tem)(),(

nlrrl

nrrll

nnnr

nl

rl

rl

nrl

nrl

xxqxpxqxpxxqxpxqxpxqxp

xpxppxp

xpxppxp

ngrauxqxqxpxp

ngrauxqxpxxqxqxq

xxpxpxp

n

n


4 multiplicações1 adição



2

2/4

nOnT

nOnTnT

Complexidade:

rlauxm

rlrlaux

m

rrr

lll

xr

nml

rrrr

qqppr

r

qpr

qpr

xrxrrxr

?

2/

É necessário resolver menos de quatro problemas



aOTA

OT

cccnA

ccnA

cnAnA

cnnT

nnT

ncnTnTnOnTnT

1222

12

8/23

23

23

4/23

23

2/23

2/2/

23

2/32/3



cnac

nAnnT

cn

ac

cac

cca

canA

n

n

n

n

nn

nn

232

232

2232

2232

23

123123

23

2log

2log

2

2log

22

2

log

loglog

loglog



58.1

5849.1

)3(log

))(log3(log

log3log

22

22

222

222

232

2

22

22

2log

nOnT

cnnac

cnnac

cnac

cnac

cnacnT

n

n

n


Multiplicação de matrizes

3

1

nO

bac

BAn

kjkkiij

nnnn


Hipótese: n=2k

Particionar A e B em quatro submatrizes n/2 x n/2

2222122122

2122112121

2212121112

2112111111

2221

1211

2221

1211

2221

1211

BABACBABACBABACBABAC

CC

CC

BB

BB

AA

AA


Multiplicação de matrizesMultiplicação de matrizes

A · B: oito multiplicações de matrizes (n/2)Adicionar duas matrizes n/2 x n/2 : O(n2)

)()(

2)()2/(8

2)1()(

3

2

nOnT

nnOnT

nOnT



)()()()(

)()()(

)()()(

22212212

12111121

221211

112122

221211

112221

22112211

BBAAVBBAAU

BAATBBASBBAR

BAAQBBAAP

Aumentar o número de adições de matrizes para diminuir o número de multiplicações: método de Strassen

UQRPC

SQC

TRC

VTSPC

22

21

12

11

7 multiplicações18 adições



81.27log

7log4log7log4log

loglog

2

122

2

2

2222

2

2

747

)1(747

47

471

27

21)(

nOnO

ncn

cn

TannT

nOnT

nOnT

nn

kk


Problema do par mais próximo

• Problema do par mais próximo: dados n pontos no plano com coordenadas (xi, yi), i=1,…n, obter o par de pontos mais próximo

• “Força bruta”: calcular todas as n(n-1)/2 distâncias: O(n2)

É possível fazer melhor do que isso?

1. Ordenar todos n pontos pelas coordenadas xi O(n log n)



2. Separar os pontos em duas metades, de acordo com a ordenação pelas coordenadas xi

P1 P2

d1: menor distância entre pontos de P1

d2: menor distância entre pontos de P2

Verificar se existe A1 P1 e A2 P2 tais que:

d(A1,A2) = d < min{d1,d2}

d1 e d2 podem ser calculados recursivamente.

Falta calcular d = min {d(A1,A2): A1 P1 e A2 P2}.



T(n) = 2.T(n/2) + O(n) T(n) = O(n log n)

Como calcular d em O(n)?

P1P2

d1

d2

= min {d1,d2}

Só é necessário calcular d se d < .

Só é necessário examinar uma faixa de pontos a distância da reta vertical que separa P1 e P2.



• Muitos pontos são eliminados, mas no pior caso podem restar O(n) pontos nesta faixa: o cálculo de d continuaria O(n2).

• É possível mostrar que na média há na média. nOnO 2

para i =1 até #pontos_na_faixa-1 façapara j = i+1 até #pontos_na_faixa-1 faça se d(pi, pj) < então

d(pi, pj)

Como melhorar?



• As coordenadas y dos dois pontos que definem d diferem por no máximo , senão d > .

• Se os pontos na faixa estão ordenados em ordem crescente pelas coordenadas y, se d(pi,pj) > pode-se abandonar a

análise de pi e passar-se a pi+1.

• Hipótese: pontos na faixa ordenados por yi.

para i =1 até #pontos_na_faixa-1 façapara j = i+1 até #pontos_na_faixa-1 faça se |yi - yj| > então examinar pi+1 e sair do loop interno

senão se d(pi,pj) < então d(pi, pj)



i

• Não pode haver mais do que oito pontos no retângulo x .• Um deles é o ponto sendo examinado. • Verificar no máximo sete pontos: pode ser feito em O(1).



• Ordenar os pontos pelas coordenadas x.

• Dividir o conjunto em duas partes P1 e P2.

• Recursivamente calcular as distâncias d1 e d2.

• Fazer ← min {d1,d2}.

• Eliminar os pontos a uma distância superior a da linha de separação.

• Ordenar os pontos na faixa de acordo com as coordenadas y.• Investigar os pontos na ordem e computar a distância de cada

um deles a no máximo sete vizinhos. Se alguma distância for menor do que , então atualizar .

Algoritmo 1:

T(n) = O(n log n) + 2.T(n/2) + O(1) + O(n) + O(n log n) + O(n)



2log

22log

42

2log

242

2

log2

2

2log2

2

21

2 nnnnbnTnT

nnbnTnT

nbnnTnT

nnnOnT

nOnT

nnOnT

kkbnnjkbnnnT

bnnnT

nbnnnTnT

k

j

k

j

jk

kk

jjj

jk

k

2

1

0

1

0

1

0

log

21

2log

2 com2

log2

22

2



• Ordenar os pontos pelas coordenadas x.• Dividir o conjunto em duas partes P1 e P2.• Recursivamente:

• Calcular as distâncias minímas d1 e d2. .

• Ordenar os pontos em P1 e P2 segundo as coordenadas y.• Combinar as duas listas ordenadas em uma única• Fazer ← min {d1,d2}.• Eliminar os pontos a uma distância superior a da linha de

separação. • Investigar os pontos na ordem e computar a distância de cada um

deles a no máximo sete vizinhos. Se alguma distância for menor do que , então atualizar .

Algoritmo 2:

T(n) = 2.T(n/2) + O(n) = O(n log n)

Algoritmos gulosos


• Problema de otimização• Extensões sucessivas de soluções parciais• Sempre escolhe a extensão viável que propicia o maior

ganho (“gula”) • Otimalidade nem sempre garantida• Sistema de subconjuntos: matróide• Algoritmos simples e eficientes• Análise de complexidade: simples

Algoritmos gulosos


• Grafo não-orientado G(V, E): obter S V tal que:i. {u, v} E então uS ou vSii. |S| é mínima

Cobertura por nós mínima

2

1 3

5

4

5

2

1 3

4

|S| = 4

ordem dosvértices

maior grau(guloso)

2

1 3

5

4

|S| = 2

divisãoe conquista

2

1 3

5

4

|S| = 3


• O algoritmo guloso obtém necessariamente a solução ótima?


Solução gulosa Solução ótima



• O algoritmo guloso obtém necessariamente a solução ótima?

grau 1

grau n+1

grau n+2

n+2 nós

n+2 nós

n nós

A solução pode ser muito ruim!

%1002

222

nn

nnnnrelativoerro


Armazenamento em fita

• Entrada: L (l1, l2, …, ln) vetor com comprimentos de n arquivos

a serem armazenados em uma fita suficientemente extensa

• Saída: (j, li(j)) para j=1, …, n

i(j) é o índice do j-ésimo arquivo na fita

n

k

k

jjiln

TMR1 1

)(1

Determinar a ordem de armazenamento dos arquivos na fita, de modo a minimizar o tempo médio TMR (ou total) de recuperação de um arquivo.



7 3 5 2 … 7 3 2 5 …

n

k

k

jijlTMR

TMRTMR

1 1

min min

446

5237237

377

449

2537537

377


• Armazenar arquivos em ordem crescente de tamanhos• Algoritmo auxiliar: ordenar o vetor em O(n log n)

Numa solução ótima não existe

Supondo-se que existisse:

Trocando:


jjll jiji ':)'()(

2 3 5 7 …

Mostrar que o algoritmo é correto

}()2()1(1 1

)( .1.1. niii

n

k

k

jji llnlnl

A

jiji ljnljn )'()( 1'1

B

jiji ljnljn )'()( 11' B-A?



0

).('

).'().'(

'...'.

')()'(

)'()(

)'()()'()(

ijijjiji

jiji

jijijiji

llblblbbjj

ljjljj

ljljljljAB

a troca diminuiria o custo.


)0,(

,...,110

max

1 1

1

1

jj

n

j

n

jjjj

j

n

jjj

n

jjj

ca

bxaba

njx

bxa

xc

em qualquer solução ótima

Problema da mochila


Problema da mochila

• Guloso 1: maior ganho primeiro• Guloso 2: menor volume primeiro• Guloso 3: maior densidade primeiro (densidade = ganho/volume)

Exemplo:

Objeto Ganho Volume1 25 182 24 153 15 10 total 64 43

Volume disponível na mochila = 20


Problema da mochila

É permitido fracionar os objetos

• guloso 1: ganhos decrescentes

• x1: fração do objeto 1 x1 = 1

• volume residual = 20 - 18 = 2

• 15·x2 = 2 x2 = 2/15

• valor total: 25 + 2/15 · 24 = 28.2

x1 x2 x3 ganho

1 2/15 0 28.2

4/9 4/5 0 30.3

Enche a mochila muito rapidamente!


Problema da mochila

x1 x2 x3 valor

1 2/15 0 28.2

4/9 4/5 0 30.3

0 2/3 1 31.0

0 4/5 4/5 31.2

0 1 1/2 31.5

guloso 1

guloso 2

guloso 3

i ci ai ci/ai

1 25 18 ~1.38 32 24 15 1.60 13 15 10 1.50 2b=20


Problema da mochila

Provar que a solução do guloso com o terceiro critério é ótima:

• Ordenar os objetos em ordem decrescente das razões cj/aj

• Solução gulosa: (1, 1, 1, …, 1, gj, 0,…, 0, 0)

• Diminuir o valor de uma variável em A aumentar uma variável em B


Problema da mochila

Hipótese: não é permitido fracionar os objetos

• O algoritmo guloso não obtém necessariamente a solução ótima!

• Por que?• Propor outros algoritmos gulosos: soluções ótimas? contra-

exemplos?• Algoritmo guloso é uma heurística de baixa complexidade.

25 pois 250,1:

24 pois24021103

1321

2

3

2

1

clucroxxxótimo

clucroxxx


• Entrada:

G = (V,E) grafo não-orientado

peso c(e) e E

• Saída: F E tal que

(i) O grafo G’=(V,F) é acíclico e conexo (G’ é gerador de G)

(ii) F é maximal

(iii) c(F) c(e) é mínimoe F

Árvore Geradora de Peso Mínimo


8

Exemplos de árvores geradoras:

3

4 9

2

2

78

9

8

3

8

A B

CF

D E4 9

2

88

A B

CF

D E

Árvore Geradora de Peso Mínimo

Princípio do algoritmo: a aresta de menor peso sempre pertence à solução ótima

3

47

3

A B

CF

D E

8


L lista com arestas ordenadas em ordem crescente de pesos;F ;count 0;enquanto count < n – 1 e L faça seja (v,w) o próximo arco de L remover (v,w) de L

se v e w não estão na mesma componente início F F {(v,w)} colocar v e w na mesma componente count count + 1

fimfim

Algoritmo de Kruskal


c(e) e

2 (f,c)

2 (c,e)3 (a,b)3 (a,d)4 (a,f)7 (b,c)8 (b,e)8 (e,f)8 (c,d)9 (d,e)9 (b,f)

C(T) = 2 + 2 + 3 + 3 + 4 = 14

3

4 9

2

2

78

9

8

3

8

A

CF

D E

B

Exemplo


6f5e4d3c2b

1aÁrvoreVértice

f c ?6 3

3f5e4d3c2b

1aÁrvoreVértice

c e ?3 5

5f5e4d5c2b

1aÁrvoreVértice

Exemplo


a d ?1 4

5f5e4d5c4b

4aÁrvoreVértice

a f ?4 5

5f5e5d5c5b

5aÁrvoreVértice

b a ?2 1

5f5e4d5c1b

1aÁrvoreVértice

c e ?3 5

5f5e4d5c2b

1aÁrvoreVértice

Exemplo


Ordenar O(m log m) O(m log n)

Testar componentes O(1) m vezes O(m)

Reorganizar componentes O(n) n vezes O(n2)

T(n) = O(m log m) + O(m) + O(n2) =

= O(m log m + n2) = O(m log n + n2)

Complexidade


Union finding:

1) Dado um nó, obter sua componente.

2) Fundir duas componetes.

• Colocar os nós de cada componente em uma árvore e representar a componente pela raiz da árvore.

• Achar a componente: seguir o caminho do nó até a raiz.

• Fundir duas componentes: fazer a raiz de uma componente tornar-se filha da raiz da outra.

– A raiz da árvore mais baixa torna-se filho da raiz da árvore mais alta.

– Altura da árvore log n

Estrutura de dados


31 2 41 2 3

árvore mais baixa árvore mais alta

31 2 4

2

1 43 ...

...

Estrutura de dados


altura log n

Determinar cada componente e testar: O(log n)

Reorganizar componentes: O(1)

Complexidade:

T(n) = O(m log n), melhor do que O(m log n + n2)

Complexidade


• Começar com um nó qualquer.• A cada iteração, adicionar a aresta de menor peso que

conecta um nó já conectado a um nó não conectado.

3

4 9

2

2

78

9

8

3

8

A

CF

D E

B

Algoritmo de Prim


• Seja (k,l) a aresta de menor peso• Para i de 1 a n, fazer:

prox(i) l, se cil < clk

prox(i) k, caso contrário• prox(k), prox(l) 0• Fazer (n-2) iterações:

– Seja j tal que prox(j) 0 e cj,prox(j) é mínimo– Fazer prox(j) 0– Para k de 1 a n, faça Se prox(k) 0 e ck,prox(k) > ckj, então prox(k) j

Complexidade: T(n) = O(n2)

Algoritmo de Prim


e

f c

a 3

4 9

2

2

78

9

8

3

8

d

b

e

2f2

c

4

3

d

a 3 b

Exemplo


• Intercalar 2 arquivos com m e n registros: m + n operações (merge).

• Intercalar diversos arquivos: dois a dois• Diferentes ordens levam a diferentes tempos de processamento:

A = 30B = 20C = 10

registros

A + B = 50 operações(A + B) + C = 60 operaçõesB + C = 30 operações(B + C) + A = 60 operações

Intercalação ótima de arquivos


n4

n3

n2 n1


n1 + n2

n1 + n2 + n3

n1 + n2 + n3 + n4

3n1 + 3n2 + 2n3 + n4


n4 n3 n2 n1


n1 + n2

n3 + n4

(n1 + n2)+ (n3 + n4)

2n1 + 2n2 + 2n3 + 2n4

Menores arquivos primeiro!


• Arquivos: nós externos da árvore binária

• Operações: nós internos

• di: distâncias da raiz ao nó representando o i-ésimo arquivo

• Número total de operações (cópias/deslocamento)

di.qi

(qi é o número de registros no arquivo i)



• Lista L de n árvores• Cada nó na árvore tem 3 campos

– LCHILD:– RCHILD:– PESO: tamanho de um arquivo

procedure TREE(i,n)para i = 1 até n-1

GETNODE (T)LCHILD(T) LEAST (L)RCHILD(T) LEAST (L)WEIGHT(T) WEIGHT(LCHILD(T)) + WEIGHT(RCHILD(T))INSERT(L,T)

return (LEAST(L))



GETNODE(T): novo nó para usar na construção da árvore

LEAST(L): obtém e remove da árvore em L cuja raiz tem menor peso

INSERT(L,T): insere a árvore com raiz T na lista L



5 10 20 30 30L:1 2 3 4 5

GETNODET

LEAST (L) 1 LEAST (L) 2

L:15 20 30 30

6 3 4 5

5 10



30 3035

15 20

5 10

35

15 20

5 10

60

30 30



95

35

15 20

5 10

60

30 30



n – 1 iteraçõesLista L ordenada pelos pesosLEAST O(1)INSERT O(n)

L organizada como um heapLEAST O(log n)INSERT O(log n)

O(n2)

O(n log n)

Prova por induçãoSe L inicialmente contém n 1 árvores-nós isoladas

com pesos q1, ..., qn, então o algoritmo gera uma árvore ótima com estes pesos.



Programação Dinâmica


Motivação

• Problema: determinar o caminho mais curto de 1 a 12 no grafo abaixo

5

4

3

8

7

6

11

10

9

12116

9

7

3

2

4

2

7

11

11

8

654

3

5

6

4

2

5

2

1

2 4

5

9

18

15

7

5

7

7

2 0

• Procedimento backwards

Trajetória ótima de cada nó ao destino final


Motivação


5

4

3

8

7

6

11

10

9

1210

9

7

3

2

4

2

7

11

11

8

654

3

5

6

4

2

5

2

1

2 15

16

7

3

2

9

11

9

10

14 16

• Procedimento forward

Trajetória ótima do nó inicial até cada nó


Motivação


5

4

3

8

7

6

11

10

9

1210+1

6

9

7

3

2

4

2

7

11

11

8

654

3

5

6

4

2

5

2

1

2

7+99+7

14+2 16+0

• Combinação das trajetórias ótimas

Trajetória ótima através de cada nó


Motivação


5

4

3

8

7

6

11

10

9

121

9

7

3

2

4

2

7

11

11

8

654

3

5

6

4

2

5

2

1

2

10+7

Trajetória ótima através de cada nó

• Combinação das trajetórias ótimas


Programação dinâmica

• Aplicação a problemas de decisões seqüenciais: cada decisão aplicada a um estado em determinado estágio leva a um estado do estágio imediatamente seguinte.

• Princípio da otimalidade: uma seqüência ótima de decisões tem a propriedade de que quaisquer que sejam o estado e a decisão inicial, as decisões remanescentes constituem uma seqüência ótima de decisões com relação ao estado decorrente da primeira decisão.

• Alternativamente: “toda subtrajetória da trajetória ótima é ótima com relação a suas extremidades inicial e final”.



• Método exato para resolver problemas de progamação inteira que envolvem apenas decisões seqüenciais, nos quais cada nova decisão depende apenas do estado do sistema, mas não das decisões anteriores (isto é, da forma como este estado foi atingido).

• Principais conceitos envolvidos:– estágios (etapas)– estados– decisões– função critério a ser otimizada



• Roteiro de aplicação:

– Identificar um modelo de decisões seqüenciais através de seus estágios.

– Assegurar-se de que cada solução viável (ou trajetória) pode ser vista como uma seqüência de decisões tomadas a cada estágio, de modo tal que seu custo seja igual à soma dos custos das decisões individuais.

– Definir o conceito de estado como a resultante de todas as decisões relevantes tomadas no passado (caso forward).(alternativamente, definir o conceito de estado como a resultante de todas as decisões relevantes tomadas no futuro no caso backwards)



• Roteiro de aplicação (continuação):

– Determinar as transições de estado possíveis.

– Atribuir o custo de cada transição de estado à decisão correspondente.

– Escrever uma recursão que defina o custo ótimo do estado inicial até o estado final.

• Exemplo de aplicação: problema da mochila


• Problema de programação inteira

• As variáveis inteiras binárias (0-1) representam a decisão de selecionar um objeto ou não.

• Solução não trivial!

• Ordenar as variáveis pelo índice lucro/volume resolve o problema linear apenas, mas não o de programação inteira.

Problema da mochila

• Caso (4): os itens não podem ser fracionados e no máximo uma unidade de cada item pode ser selecionada

njx

bxa

xc

j

n

jjj

j

n

jj

,...,1,1,01

1

: a sujeito

maximizar


Problema da mochila

• Decomposição do problema em estágios

• Em vez de considerar uma solução (x1,x2,...,xn) completa de uma só vez, visualizar o problema como se as decisões fossem tomadas para um item de cada vez.

• Após k decisões, terão sido determinados quais dos primeiros k itens devem ser selecionados e, conseqüentemente, terão sido determinados os valores das variáveis x1,x2,...,xk.

• Neste ponto, o valor acumulado é e o volume acumulado é

.

k

jj xa1j

j

k

jj xc

1


Problema da mochila• Estágio:

cada variável do problema

• Estado: volume total ocupado com as decisões já tomadas

• Decisão: selecionar ou não um item (isto é, fazer xk=1)

• Custo da decisão de selecionar o item k: aumento de ck unidades no lucro parcial acumulado

• Efeito da decisão de selecionar o item k: aumento do volume ocupado (estado) em ak unidades


Problema da mochila• Definição:

yk(u) = lucro máximo que pode ser obtido com volume total igual a u e usando apenas itens do conjunto {1,...,k}

• Quanto vale y0(0)?– y0(0) = 0 (sem objetos selecionados, o peso e o lucro são nulos)

• Definir yk(u) = - se é impossível obter um volume total igual a u apenas com itens dentre os do conjunto {1,...,k}.

• Quanto valem y0(u) e yk(0)? – y0(u) = - para u > 0 (impossível acumular peso sem itens)– yk(0) = 0 para k = 1,2,...,n (nenhum item selecionado)

• Calcular yk(u) para k = 1,...,n e u = 0,...b, a partir de y0(0).


Problema da mochila

• yk(u) = lucro máximo que pode ser obtido com volume total igual a u e usando apenas itens do conjunto {1,...,k}

• Calcular yk(u) para k = 1,...,n e u = 0,...b:

• Interpretação: há duas alternativas para se obter yk(u), dependendo do item k ser selecionado ou não– yk(u) = yk-1(u), se o item k não é usado– yk(u) = yk-1(u-ak)+ck, se o item k é usado

nkbucauyuyb;ku

kuuy

kkkk

k

,...,1;,...,0,)(),(max0,...,1,

0;0,0)(

11


Problema da mochila

• Observar que o lucro associado ao estado resultante de uma decisão depende apenas do valor desta decisão e do estado atual, mas não depende da forma como este último foi atingido.

nkbucauyuyb;ku

kuuy

kkkk

k

,...,1;,...,0,)(),(max0,...,1,

0;0,0)(

11


Problema da mochila

5,...,1},1,0{4233 :a sujeito

3223max

54321

54321

jxxxxxx

xxxxx

j

y5(4) =


Problema da mochila

5,...,1},1,0{4233 :a sujeito

3223max

54321

54321

jxxxxxx

xxxxx

j

5,...,1},1,0{233 :a sujeito

3223max

54321

54321

jxbxxxxx

xxxxx

j

y5(b) =

Valor ótimo = maxb=0,...,4 {y5(b)}


Problema da mochila

y0(4) y5(4)

y0(3) y5(3)

y0(2) y5(2)

y0(1) y5(1)

y0(0) y1(0) y2(0) y3(0) y4(0) y5(0)

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

y0(4)

y0(3)

y0(2)

y0(1)

0 0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

-

-

-

-

0 0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- ?

- ?

- ?

- ?

0 ?

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

-

-

- -

- -

0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

-

- 3

- -

- -

0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- -

- 3

- -

- -

0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- -

- 3

- -

- -

0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - ?

- 3 ?

- - ?

- - ?

0 0 ?

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- -

- 3

- -

- -

0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- -

- 3

- - -

- - -

0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- -

- 3

- - -

- - -

0 0 0

2

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- -

- 3

- - -

- - -

0 0 0

0

2

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- -

- 3 3

- - -

- - -

0 0 0

0

2

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - -

- 3 3

- - -

- - -

0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - -

- 3 3

- - -

- - -

0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - ?

- 3 3 ?

- - - ?

- - - ?

0 0 0 ?

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - -

- 3 3

- - -

- - -

0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - -

- 3 3

- - -

- - - 2

0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - -

- 3 3

- - - -

- - - 2

0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - -

- 3 3

- - - -

- - - 2

0 0 0 0

2

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - -

- 3 3

- - - -

- - - 2

0 0 0 0

2

0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - -

- 3 3 3

- - - -

- - - 2

0 0 0 0

2

0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5

- 3 3 3

- - - -

- - - 2

0 0 0 0

2

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5

- 3 3 3

- - - -

- - - 2

0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 ?

- 3 3 3 ?

- - - - ?

- - - 2 ?

0 0 0 0 ?

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5

- 3 3 3

- - - -

- - - 2

0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5

- 3 3 3

- - - -

- - - 2

0 0 0 0 01

0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5

- 3 3 3

- - - -

- - - 2 2

0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5

- 3 3 3

- - - - 3

- - - 2 2

0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5

- 3 3 3 3

- - - - 3

- - - 2 2

0 0 0 0 0

0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5

- 3 3 3 3

- - - - 3

- - - 2 2

0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5

- 3 3 3 3

- - - - 3

- - - 2 2

0 0 0 0 0

1

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5

- 3 3 3 3

- - - - 3

- - - 2 2

0 0 0 0 0

1

0u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5

- 3 3 3 3

- - - - 3

- - - 2 2

0 0 0 0 0

1

0u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5

- 3 3 3 3

- - - - 3

- - - 2 2

0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5 ?

- 3 3 3 3 ?

- - - - 3 ?

- - - 2 2 ?

0 0 0 0 0 ?

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5

- 3 3 3 3

- - - - 3

- - - 2 2

0 0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5

- 3 3 3 3

- - - - 3

- - - 2 2

0 0 0 0 0 0

0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5

- 3 3 3 3

- - - - 3

- - - 2 2 2

0 0 0 0 0 0

0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5

- 3 3 3 3

- - - - 3

- - - 2 2 2

0 0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5

- 3 3 3 3

- - - - 3

- - - 2 2 2

0 0 0 0 0 0

0

3

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5

- 3 3 3 3

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

0

3

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5

- 3 3 3 3

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5

- 3 3 3 3

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

0

3

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5

- 3 3 3 3 5

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

0

3

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5

- 3 3 3 3 5

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5

- 3 3 3 3 5

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

0

3

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5 6

- 3 3 3 3 5

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

0

3

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5 6

- 3 3 3 3 5

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5


Problema da mochila

- - - 5 5 6

- 3 3 3 3 5

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5

y5(4) = 6

y5(3) = 5

y5(2) = 3

y5(1) = 2

y5(0) = 0


Problema da mochila

- - - 5 5 6

- 3 3 3 3 5

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5

y5(4) = 6

y5(3) = 5

y5(2) = 3

y5(1) = 2

y5(0) = 0


Problema da mochila

- - - 5 5 6

- 3 3 3 3 5

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5

y5(4) = 6

y5(3) = 5

y5(2) = 3

y5(1) = 2

y5(0) = 0


Problema da mochila

- - - 5 5 6

- 3 3 3 3 5

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5

y5(4) = 6

y5(3) = 5

y5(2) = 3

y5(1) = 2

y5(0) = 0

x5=1


Problema da mochila

- - - 5 5 6

- 3 3 3 3 5

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5

y5(4) = 6

y5(3) = 5

y5(2) = 3

y5(1) = 2

y5(0) = 0

x5=1x4=1


Problema da mochila

- - - 5 5 6

- 3 3 3 3 5

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5

y5(4) = 6

y5(3) = 5

y5(2) = 3

y5(1) = 2

y5(0) = 0

x5=1x4=1x3=1


Problema da mochila

- - - 5 5 6

- 3 3 3 3 5

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5

y5(4) = 6

y5(3) = 5

y5(2) = 3

y5(1) = 2

y5(0) = 0

x5=1x4=1x3=1x2=0


Problema da mochila

- - - 5 5 6

- 3 3 3 3 5

- - - - 3 3

- - - 2 2 2

0 0 0 0 0 0

u = 4

u = 3

u = 2

u = 1

u = 0

k = 0 k = 1 k = 2 k = 3 k = 4 k = 5

y5(4) = 6

y5(3) = 5

y5(2) = 3

y5(1) = 2

y5(0) = 0

x5=1x4=1x3=1x2=0x1=0


Problema da mochila

• Os estados em verde e as transições possíveis (arcos com setas) definem um grafo multiestágio para a aplicação da recursão de programação dinâmica.

• Número de operações (tempo de processamento) diretamente proporcional ao produto do tamanho da mochila pelo número de variáveis (preencher inteiramente a matriz de dimensões (b+1)x(n+1)): aplicabilidade limitada aos valores de n e de b

• Caso seja possível levar múltiplas cópias de cada item, aumenta o número de decisões e a complexidade do problema.



• Redução no número total de operações:

21 ... n-1 np “linhas”

A

B

Total de trajetórias de A a B: pn

Total de adições?

Cálculo exaustivo: n.pnProgramação

dinâmica:p + p.p.(n-1) + p n.p2

Cálculo da menortrajetória de A a B



• Observar que o valor da função objetivo associado a um estado depende apenas dele, mas não depende da forma como foi atingido.

• O fato de serem implicitamente descartadas subtrajetórias não-ótimas é que leva à redução significativa do número de operações.



• Identificar decisões e estágios

• Identificar o critério de otimização

• Construir a função critério– Identificar o critério de otimalidade– Para cada decisão relacionar recursivamente os valores do critério

definindo as variáveis de estado necessários

• Considerando as variáveis de estado, fornecer condições de contorno para a função critério.

• Determinar a política ótima para cada estágio e estado.



• (I) Problema de otimização de investimentos: Considere-se um conjunto de n possíveis investimentos, nos quais é possível aplicar no máximo um total de M unidades monetárias. Seja cj(k) o retorno obtido com a aplicação de 0 k M unidades monetárias no investimento j = 1,...,n. Determinar a aplicação ótima a ser feita em cada investimento, de modo a maximizar o retorno total. Resolver o problema para n = 3 e M = 4, considerando a matriz de retornos fornecida a seguir:



k c1(k) c2(k) c3(k)

0 0 0 0

1 3 1 2

2 7 2 4

3 11 4 6

4 12 8 8



• Estágio: – cada investimento k = 1, 2, 3 considerado

• Estado:– total ainda disponível para ser aplicado nos investimentos k, k+1, …, n– outra alternativa: total aplicado nos investimentos 1, 2, …, k

• Decisão:– quanto aplicar no investimento k

• Recursão:– Rk(x) = max0yx {ck(y) + Rk+1(x-y)}



• Condições de contorno:– R4(0) = 0

Todos os recursos devem ser usados nos três investimentos.

• Valor máximo do retorno obtido:– R1(4) = ?

Maximizar o retorno obtido com a aplicação de um total de quatro unidades nos investimentos 1, 2, 3.



Estadoinicial:R1(4) = ?

Estadofinal:R4(0) = 0 Investime

nto 1Investime

nto 2Investime

nto 3





nto 1Investime

nto 2Investime

nto 3

4

0





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12

0

1

2

4

8





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12

0

1

2

4

8

01

2

4





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12

0

1

2

4

8

01

2

40

12





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12

0

1

2

4

8

01

2

40

120

1





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12

0

1

2

4

8

01

2

40

120

10





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12

0

1

2

4

8

01

2

40

120

10 0

4

6

8

2





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12

0

1

2

4

8

01

2

40

120

10 0

4

6

8

20





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12

0

1

2

4

8

01

2

40

120

10 0

4

6

8

20

8

2

4

6

0





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12

0

1

2

4

8

01

2

40

120

10 0

4

6

8

20

8

2

4

6

0

8





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12

0

1

2

4

8

01

2

40

120

10 0

4

6

8

20

8

2

4

6

0

8

6





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12

0

1

2

4

8

01

2

40

120

10 0

4

6

8

20

8

2

4

6

0

8

6

4





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12

0

1

2

4

8

01

2

40

120

10 0

4

6

8

20

8

2

4

6

0

8

6

4

2





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12

0

1

2

4

8

01

2

40

120

10 0

4

6

8

20

8

2

4

6

0

8

6

4

2

0





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12

0

1

2

4

8

01

2

40

120

10 0

4

6

8

20

8

2

4

6

0

8

6

4

2

0

13





nto 1Investime

nto 2Investime

nto 3

4

0

4

3

2

1

0

4

3

2

1

0

03

7

11

12

0

1

2

4

8

01

2

40

120

10 0

4

6

8

20

8

2

4

6

0

8

6

4

2

0

13

Solução ótima:projeto 1: 3 unidadesprojeto 2: 0 unidadesprojeto 3: 1 unidadeRetorno total = 13



• (II) Problema de substituição de equipamentos: Uma empresa precisa de uma máquina para produzir determinado produto ao longo dos próximos N anos. Os seguintes dados são disponíveis:P = preço de compra de uma máquina novac(i) = custo anual de operação de uma máquina de idade it(i) = preço obtido na troca de uma máquina de idade ir(i) = valor de residual uma máquina de idade i

No início do período de programação, a empresa dispõe de uma máquina com M anos de uso. Determinar a política ótima de substituição desta máquina ao longo dos N anos, de modo a minimizar a soma dos custos anuais. Considerar N = 5 (horizonte), M = 2 (idade da máquina no início do horizonte), P = 50 (preço de compra de uma máquina nova) e os demais custos e preços informados na tabela a seguir.



Observar que o modelo pode ser estendido para considerar preços diferentes para uma máquina nova a cada ano, taxa de desconto, troca por máquinas mais novas mas já usadas, etc.



idade i 0 1 2 3 4 5 6

c(i) 10 13 20 40 70 100 110

t(i) - 32 21 11 5 0 0

r(i) - 25 17 8 0 0 0



• Estágio: – cada ano k = 1, 2, ..., N do horizonte

• Estado:– idade da máquina no ano k

• Decisão:– o que fazer com a máquina no ano k: trocá-la por uma nova ou mantê-

la em funcionamento

• Recursão:– Vk(i): custo ótimo total do ano k até o final do horizonte a partir de uma

máquina de idade i



• Recursão:– Vk(i): custo ótimo total do ano k até o final do horizonte a partir de

uma máquina de idade I

– Máquinas novas são sempre compradas no dia 1 de janeiro de cada ano e completam um ano de vida em 1 de janeiro do ano seguinte.

– Caso uma máquina de idade i seja trocada por uma nova no início do ano k: Vk(i) = p - t(i) + c(0) + Vk+1(1)

– Caso contrário: Vk(i) = c(i) + Vk+1(i+1)

– Vk(i) = mínimo {p - t(i) + c(0) + Vk+1(1), c(i) + Vk+1(i+1)}



• Condições de contorno:– VN+1(i) = -r(i)

A máquina é vendida por seu valor residual ao final do horizonte.

• Início do ano 1: máquina tem idade M

• Custo mínimo ao longo do horizonte:– V1(M) = ?



Ano 1 Ano 2 Ano 3 Ano 4Ano N=5Ano 6



2




2

Ano 1Ano 1 Ano 2 Ano 3 Ano 4Ano N=5Ano 6



2

3

1Ano 1 Ano 2 Ano 3 Ano 4Ano N=5Ano 6

2039



2

3


2039



2

3

1

2


20

28

39 13



2

3

1

4

2


20

40

28

3949

13



2

3

1

4

2


20

40

28

3949

13



2

3

1

4

2

1

5


20

40

70

28

3949

55

13



2

3

1

4

2

1

5

3

2


20

40

70

28 28

3949

39

55

13 13

20



2

3

1

4

2

1

5

3

2


20

40

70

28 28

3949

39

55

13 13

20



2

3

1

4

2

1

5

3

2

1

6


20

40

100

70

28 28

3949

39

55

13 13

20

60



2

3

1

4

2

1

5

3

2

1

6

4

3

2


20

40

100

70

28 28 28

3949

39 3949

55

13 13 13

20 20

4060



2

3

1

4

2

1

5

3

2

1

6

4

3

2


20

40

100

70

28 28 28

3949

39 3949

55

13 13 13

20 20

4060



2

3

1

4

2

1

5

3

2

1

6

4

3

2

1 1

7


20

40

110

100

70

28 28 28

3949

39 3949

55

13 13 13

20 20

4060

60



2

3

1

4

2

1

5

3

2

1

6

4

3

2

1

5

4

3

2

1

7


20

40

110

100

70

28 28 28 28

3949

39 39 39

49 4955

55

13 13 13 13

20 20 204040

7060

60



2

3

1

4

2

1

5

3

2

1

6

4

3

2

1

5

4

3

2

1

7


20

40

110

100

70

28 28 28 28

3949

39 39 39

49 4955

55

13 13 13 13

20 20 204040

7060

60

-25

-17

-8

-0

-0

-0



2

3

1

4

2

1

5

3

2

1

6

4

3

2

1

5

4

3

2

1

7


20

40

110

100

70

28 28 28 28

3949

39 39 39

49 4955

55

13 13 13 13

20 20 204040

7060

60

-25

-17

-8

-0

-0

-0



2

3

1

4

2

1

5

3

2

1

6

4

3

2

1

5

4

3

2

1

7


20

40

110

100

70

28 28 28 28

3949

39 39 39

49 4955

55

13 13 13 13

20 20 204040

7060

60

-25

-17

-8

-0

-0

-0

35

30

24

14

-4



2

3

1

4

2

1

5

3

2

1

6

4

3

2

1

5

4

3

2

1

7


20

40

110

100

70

28 28 28 28

3949

39 39 39

49 4955

55

13 13 13 13

20 20 204040

7060

60

-25

-17

-8

-0

-0

-0

35

30

24

14

-4

56

45

35

24



2

3

1

4

2

1

5

3

2

1

6

4

3

2

1

5

4

3

2

1

7


20

40

110

100

70

28 28 28 28

3949

39 39 39

49 4955

55

13 13 13 13

20 20 204040

7060

60

-25

-17

-8

-0

-0

-0

35

30

24

14

-4

56

45

35

24

79

63

48



2

3

1

4

2

1

5

3

2

1

6

4

3

2

1

5

4

3

2

1

7


20

40

110

100

70

28 28 28 28

3949

39 39 39

49 4955

55

13 13 13 13

20 20 204040

7060

60

-25

-17

-8

-0

-0

-0

35

30

24

14

-4

56

45

35

24

79

63

48

97

76



2

3

1

4

2

1

5

3

2

1

6

4

3

2

1

5

4

3

2

1

7


20

40

110

100

70

28 28 28 28

3949

39 39 39

49 4955

55

13 13 13 13

20 20 204040

7060

60

-25

-17

-8

-0

-0

-0

35

30

24

14

-4

56

45

35

24

79

63

48

97

76

115



2

3

1

4

2

1

5

3

2

1

6

4

3

2

1

5

4

3

2

1

7


20

40

110

100

70

28 28 28 28

3949

39 39 39

49 4955

55

13 13 13 13

20 20 204040

7060

60

-25

-17

-8

-0

-0

-0

35

30

24

14

-4

56

45

35

24

79

63

48

97

76

115

Solução ótima: trocar a máquinanos anos 1, 2 e 4Custo total = 115



• (III) Problema simplificado de planejamento da operação: Considere-se um sistema formado por uma usina hidráulica com reservatório (ou um sistema equivalente) e uma usina térmica capaz de complementar toda a demanda. São conhecidas as afluências mensais, as demandas mensais, a vazão turbinada máxima mensal da usina hidráulica e os volumes inicial e final do reservatório. Equacionar um modelo passível de ser resolvido por programação dinâmica para a otimização da operação, minimizando o custo de complementação térmica.



• Dados:– Horizonte: k = 1, 2, …, N– Demanda no mês k: d(k)– Afluência no mês k: a(k)– Vazão turbinada máxima no mês k: p(k)– Custo unitário da geração térmica no mês k: c(k) – Volume mínimo do reservatório no mês k: m(k)– Volume máximo do reservatório no mês k: M(k)– Volume inicial do reservatório: V(1) = Vi

– Volume final do reservatório: V(N+1) = Vf



• Estágio:– cada mês k = 1, 2, …, N do horizonte de planejamento

• Estado:– volume x(k) do reservatório no mês k

• Decisão:– vazão turbinada u(k) na usina hidráulica no mês k

geração térmica t(k) no mês k calculada a partir de u(k) e d(k):t(k) = max {0,d(k)-produção(u(k))}



• Recursão:– x(k+1) = x(k) + a(k) - u(k)– m(k) x(k) M(k)– x(1) = Vi

– x(N+1) = Vf

– 0 u(k) p(k)– t(k) = max {0,d(k)-produção(u(k))}– minimizar k=1,…,n c(k).t(k)



• Considerações:

– Não-linearidades• produção na usina hidráulica em função da vazão turbinada• custo de complementação térmica

– Discretização dos volumes e das vazões turbinadas• aumento do espaço de estados

– Outras variáveis de decisão• vertimento v(k) no mês k: x(k+1) = x(k) + a(k) - u(k) - v(k)• produção térmica no mês k: d(k) = produção(u(k)) + t(k) + deficit(k)• aumento do espaço de decisões



• Considerações (continuação):

– Múltiplos reservatórios• estado do sistema descrito por um vetor de volumes• aumento do espaço de estados• “explosão combinatória”

– Demandas e/ou afluências não-determinísticas• modelo de programação dinâmica estocástica


• G = (V, E) grafo orientado |V| = n

• Obter o valor do caminho mais curto entre cada par de nós• Caminho mais curto de i a j:

• Se o caminho curto de i a j passa por k, então ele usa o caminho mais curto de 1 a k e o caminho mais curto de k a j.

Cii = 0Cij = + (i,j) ENão há ciclos negativos

Ri j

ciclo

Todos os caminhos mais curtos


• Se k é o índice do nó de maior índice entre i e j, então o caminho mais cursto de i a k não passa por nenhum nó de índice maior do que k–1.

• Ak(i,j): comprimento do caminho mais curto de i a j passando por nenhum vértice de índice maior do que k.

• A(i,j): comprimento do caminho mais curto de i a j.


– Obter o caminho mais curto de i a j pode ser visto como a determinação do nó de maior índice que faz parte deste caminho.

– Em seguida, achar dois caminhos mais curtos:

de i a j sem usar nós de índice maior dode k a j que k-1


• A(i, j) = min {Cij,A’(i, j)}

• A’(i, j) = min {Ak-1(i,k) + Ak-1(k,j)} 1 k n

• A0(i, j) = Cij

• O caminho mais curto de i e j não passando por um nó de índice maior do que k ou passa pelo nó k ou não:Se passa : Ak(i, j) = Ak-1(i,k) + Ak-1(k,j)Se não passa: Ak(i, j) = Ak-1(i,j)

Ak(i, j) = min {Ak-1(i,k) + Ak-1(k,j), Ak-1(i,j)} A1, A2, A3, ..., An A = An



Exemplo:

para i = 1 até n façapara j = 1 até n faça

a(i,j) Cij

para k = 1 até n façapara i = 1 até n faça

para j = 1 até n faça ak(i,j) min{ak-1(i,j), ak-1(i,k) + ak-1(k,j)}

T(n) = O(n3)

1 2

3

6

411

23

0 4 116 0 23 0

C =



0 4 66 0 23 7 0

A2 =

0 4 116 0 23 0

A0 =0 4 116 0 23 7 0

A1 =

0 4 65 0 23 7 0

A3 =



• Seqüência de matrizes A1,A2, ..., An

1. Parentetizar para definir a ordem em que as matrizes serão multiplicadas.2. Multiplicar as matrizes duas a duas segundo o algoritmo tradicional.

• Um produto de matrizes está completamente parentetizado1. se é uma matriz única2. se é o produto de duas matrizes completamente parentetizados envolvido

por parênteses.

(A1 (A2 (A3 A4) ) )

(A1 ( (A2 A3 ) A4 ) )

( (A1 (A2 A3 ) ) A4 )

( (A1 A2 ) (A3 A4 ) )

( ( (A1 A2 ) A3 ) A4 )

Encadeamento ótimo do produto de matrizes

Qual é a influência da ordem?


Algoritmo

A: r q A B pqr operaçõesB: q r

Exemplo: A1A2A3

Matrix_Multiply (A, B)se colunas(A) linhas(B) então

errosenão para i 1 até linha (A) faça

para j 1 até coluna(B) faça C[i,j] 0 para k 1 até coluna(A) faça

C[i,j] C[i,j] + A[i,k] B[k,j] retorne C

A1: 10 x 100A2: 100 x 5A3: 5 x 50

( (A1A2)A3) 5.000 + 2.500 = 7.500(A1(A2A3)) 25.000 + 50.000 = 75.000


Problema

• Dada uma cadeia A1, ..., An de n matrizes, onde a matriz A, tem dimensões pi-1 pi, completamente parentetizar o produto A1, ..., An de forma a minimizar o mínimo de operações de multiplicações escalares.

• Número de parentetizações:P(n): números de alternativas para parentetizar completamente o produto de n matrizes.

2),()(

1,1)( 1

1

nknPkP

nnP n

k

222211

k n-k

Parentetizar

k = 1, 2, ..., n-1

)1()( ncnP

2/3

421

1)(nn

nn

nCn


Cálculo dos custo ótimos

• Um problema para cada i, j satisfazendo 1 i j n

• Um algoritmo recursivo resolve o mesmo problema muitas vezes. Aproveitar a estrutura dos subproblemas que se recobrem para acelerar.

222222

Em vez de recursividade enfoque botton-up

)(2

2nOnn

problemas (pares)


• Parentetização ótima separa o produto entre Ak e Ak+1 para algum k=1, ..., n-1

• Para algum k:

• A parentetização de A1 A2 ... Ak tem que ser ótima, assim como a de Ak+1 ... An

Caracterização da estrutura de uma solução ótima

222233

Ai...j = Ai ...Aj

A1 ... k Ak+1... n·

custo total = custo + custo


Solução recursiva• Definir recursivamente o valor da função ótima em termos das

soluções dos subproblemas.• Subproblema: determinar o custo mínimo

Princípio da otimalidade

222244

m[i,j] de parentetizar Ai Ai+1...Aj para 1 i j n

custo ótimo : m[1,n]


• m[i,j] = ?i = j: a cadeia é formada por uma só matriz m[i, j] = 0i < j: usar a estrutura de uma solução ótima

• Hipótese: a parentetização de Ai...j separa a cadeia entre Ak e Ak+1 onde i k < j.• Então:


222255

m[i,j] = m[i,k] + m[k+1, j] + Pi-1 Pk Pj

Ai...k Ak+1 ...j

Pi-1 Pk Pk Pj


• k pode assumir valores entre i e j-1. Logo,

• m[i, j] =

onde i k < j

• S[i, j] = valor de k onde deve ser separado o produto Ai ...Aj

• S[i, j] = k tal que

m[i,j] = m[i,k] + m[k+1, j] + Pi-1 Pk Pj


222266

i k j

0,min

m[i,k] +m[k+1, j] + Pi-1 Pk Pj

i = ji < j


Algoritmo

222277

Recursive_ Matrix_Chain(P, i, j)se i=j então

retorne 0m[i, j] para k 1 até j-1 faça

q Recursive_ Matrix_Chain(P, i, k) + Recursive_ Matrix_Chain(P, k+1, j) + Pi-1 Pk Pj

se q < m[i, j] então m[i, j] qretorne m[i, j]


Complexidade

222288

n > 1

1

1

1)2()()(2)(n

i

nOnOiTnT

)1)()1()()()(

)1()1(1

1

n

k

OknTKTnT

OT

i = 1, 2, ..., n-1 T(i)

T(K)

T(n-k)

n = 1



222299

i k j

1...4

1...1 2...4 1...2 3...4 1...3 4...4

2...2 3...4 2...3 4...4 1...1 2...2 3...3 4...4 1...1 2...3 1...2 3...3

3...3 4...4 2...2 3...3 2...2 3...3 1...1 2...2


• Preencher a matriz m como resolvendo-se o problema de parentetização em matrizes cujo comprimento aumenta:

• m[i, j] =

onde i k j


230230

i = ji < j

0,min

m[i,k] +m[k+1, j] +Pi-1 Pk Pj

calcular o produto de j-i+1 matrizes

depende apenas do custo de processar produtos de menor de j-i+1 matrizes

m[i, j] 0Em seguida: m[i, i+1] i = 1, 2, ..., n-1custos mínimos para cadeias de l =2 matrizes



231231

Matrix_Chain_Order(P)n length(P) - 1para i 1 até n faça

m[1, i] 0para l 2 até n faça

para i 1 até n-l+1 façaj i + l – 1m[i, j] para k i até j-1 faça q m[i, k] + m[k+1, j] + Pi-1 Pk Pj se q < m[i, j] então

m[i, j] qs[i, j] k

retorne m, s

Matriz A: tem dimensões Pi-1 Pi

A entrada é uma seqüência (P0, P1, ..., Pn) = P de comprimento n+1


Exemplo

232232

0 0 0 0 0 01

2

3

4

5

6 1

2

3

4

5

6

m

A1 A2 A3 A4 A5 A6

15.125j i

A1 = 30 x 35 A4 = 5 x 10A2 = 35 x 15 A5 = 10 x 20A3 = 15 x 5 A6 = 20 x 25

T(n) = O(n3)


Exemplo

233233

A[1, 6] = 3 (A1 A2 A3) (A4 A5 A6)

A[1, 3] = 1 A[4, 6] = 5( (A1 ( A2 A3) ) ( (A4 A5 ) A6) )

1 2 3 4 52

3

4

5

6 1

2

3

4

5

s

j i

1 3 3 5

3 3 3

3 3

3


Algoritmo

232344

Lookup_Chain(P, i, j)se m[i, j] < então

retorne m[i, j]se i = j então

m[i, j] 0else para k i até j-1 faça

q Lookup_Chain(P, i, k) + Lookup_Chain(P, k+1, j) + Pi-1 Pk Pj

se q < m[i, j] entãom[i, j] q

retorne m[i, j]Cada m[i, j] é preenchido em uma chamada a Lookup_Chain. Cada Chamada é O(n) T(n) = O(n3)


Algoritmo

232355

Matrix_Chain_2(P)n length [P] – 1para i 1 até n faça

para j 1 até n faça m[i, j]

retorne Lookup_Chain (P, 1, n)

• Será que é possível melhorar o algoritmo recursivo, mantendo uma tabela com as soluções dos problemas ?

• No início, a tabela tem um flag para dizer que os valores não foram processados.

• Hipótese: o conjunto de todos os possíveis subproblemas é conhecido, assim como a correspondência entre posição na tabela e subproblemas.


Exemplo

232366

i k j

1...4

1...1 2...4 1...2 1...3

2...2 3...4 2...3 4...4

3...3 4...4 2...2 3...3


Exemplo

232377

i k j

1...4

1...1 2...4 1...2 1...3

2...2 3...4 2...3 4...4

3...3 4...4 2...2 3...3


Exemplo

232388

i k j

1...4

1...1 2...4 1...2 1...3

2...2 3...4 2...3 4...4

3...3 4...4 2...2 3...3

Nós: T(n) = O(n2)Sucessores/nó: T(n) = O(n)


Algoritmo

239239

Matrix_Chain_Multiply(A, s, i,j)se j > i então

x Matrix_Chain_Multiply (A, s, i, s[i,j])y Matrix_Chain_Multiply (A, s, s[i,j]+1, y)retorne Matrix_Multiply(x, y)

senão retorne A


Subseqüência mais longa

240240

X = (x1, x2, ..., xn)

Z = (z1, z2, ..., zn)

Z é uma subseqüência de x se existe uma subseqüência crescente (i1, i2, ..., ik) de índices de x tais que para todos

J = 1, 2, ..., k Xij = Zj

Exemplo: X = (A, B, C, B, D, A, B)

Y = (B, C, D, B)

• Dados 2 seqüências X e Y, diz-se que Z é uma subseqüência comum de X e Y se Z é uma subseqüência de X e de Y.

X = (A B C B D A B)

Y = (B D C A B A)

SML = (B C B A) (B D A B)



241241

• Força bruta: X: m elementos 2m subseqüências

exponencial• Teorema:

X = (x1, x2, ..., xm)Y = (y1, y2, ..., yn)

Z = (z1, z2, ..., zk) SML (x, y)• Então: (1) se Xm = Yn, então Zk = Xm = Yn e Zk-1 é uma SML de Xm-1 e Ym-1

(2) se Xm Yn, então:(a) Zk Xm Z = SML (Xm-1 , Y)(b) Zk Yn Z = SML (X , Yn-1)



242242

• Uma SML contém uma SML de prefixos das duas seqüências.

• Obter a SML se traduz em examinar um ou dois subproblemas:

Xm = Yn, obter SML (Xm-1 , Yn-1)

Xm Yn, obter SML (Xm-1 , Y)

obter SML (X , Yn-1)

estes dois subproblemas exigem a solução de SML (Xm-1 , Yn-1)


Recorrência

243243

• c[i, j] = comprimento de SML (xi, yi)

• i = 0 ou j = 0 c[i, j] = 0

• c[i, j] =

0, i = 0 ou j = 0c[i-1, j-1] + 1, i, j > 0 xi = yj

c[i, j-1], max i, j > 0 xi yj

c[i-1, j]


Algoritmo recursivo: exponencial

244244

• Há apenas m-n subproblemas distintos P.D

• c[0...m, 0...n] calculada linha a linha da esquerda para a direita.

• b[i, j] tabela auxiliar aponta para a entrada da tabela correspondente à solução do subproblema ótimo escolhido durante o calculo de c[i, j]


Exemplo

245245

0 1 2 3 4 5 6yi B D C A B A

0 Xi 0 0 0 0 0 0 0

1 A 0 0 0 0 1 1 1

2 B 0 1 1 1 1 2 2

3 C 0 1 1 2 2 2 2

4 B 0 1 1 2 2 3 3

5 D 0 1 2 2 2 3 3

6 A 0 1 2 2 3 3 4

7 B 0 1 2 2 3 4 4


Exemplo

246246

0 1 2 3 4 5 6yi B D C A B A

0 Xi 0 0 0 0 0 0 0

1 A 0 0 0 0 1 1 1

2 B 0 1 1 1 1 2 2

3 C 0 1 1 2 2 2 2

4 B 0 1 1 2 2 3 3

5 D 0 1 2 2 2 3 3

6 A 0 1 2 2 3 3 4

7 B 0 1 2 2 3 4 4


Algoritmo

247247

SML(X, Y)m compr [x]n compr [y]para i 1 até m faça c[i, 0] 0para j 1 até n faça c[0, j] 0para i 1 até m faça

para j 1 até n façase xi = yj então c[i, j] c[i-1, j-1] + 1 b[i, j] senão se c[i-1, j] c[i, j-1] então c[i, j] c[i-1, j] b[i, j] senão c[i, j] c[i, j-1] b[i, j]

retorne c, bT(n) = O(m · n)

j - 1 ji -1

i


Programação dinâmica estocástica

248248

• Jogo: Tabuleiro dividido em três regiões de mesma área Ficha lançada sobre o tabuleiro

• Regiões I, II, III equiprováveis• Se a ficha cair na região I, o jogador escolhe entre as roletas A e B

A: I I p = ¼ l = 2 I II p = ¾ l = 4

• Região II : roletas C e D• Região III: roletas E e F

I IIIII



249249

• Três jogadas Qual roleta escolher a cada rodada?

I II

III

1/2 10

1/2 10 C

D

1/4 0

3/4 12

1/2 16

1/2 10FE

1/4 36

1/4 12

1/6 0

B

B

3/4 4

5/6 6



250250

A

B

C

D

E

F

6

5

10

915

13

K = 3K = 2

A

B

1/6 · 0 + 5/6 · 6 = 5

1/4 · 12 + 3/4 · 4 = 6

I

III

II

III

II

I I

II

III

I



251251

A

B

C

D

E

F

6

5

10

915

13

K = 1K = 2

1/6 · 0 + 5/6 · 6 = 5

1/4 · 12 + 3/4 · 4 = 6

6

10

15

I

III

II

III

II

A

BI I

II

III

I



252252

A

B

C

D

E

F

12

4

10

15

K = 1

I: A 1/4 · (12 + 6) + 3/4 · (4 + 10) = 15

6

10

6

K = 0

I: B 1/6 · () + 6) + 5/6 · (6 + 15) = 18.5

I

III

II

III

II

I



253253

A

B

C

D

E

F

12

4

10

25.5

15

K = 1

I: A 1/4 · (12 + 6) + 3/4 · (4 + 10) = 15

6

10

6

K = 2

I: B 1/6 · () + 6) + 5/6 · (6 + 15) = 18.5

15

27.8

22.8

18

18.5

I

III

II

I

III

II


Lucro esperado

254254

A

B

C

D

E

F 38.3

27.8

K = 0 I – B

II – D

III – E

22.8

18.5

27.7

40.5

35.3

30.6

31.2

K = 1 I – B

II – D

III – E

K = 1 I – A

II – C

III – E

I

III

II

I

III

II


Lucro esperado

255255

• PPD pode ter alguns elementos determinísticos, tais como o estado inicial ou o resultado de algumas decisões.

• PPD: uma mudança de estado envolve duas fases

• decisão

• resultado aleatório de decisão tomada

7.355.40313.35

312.31

31

• Lucro esperado:


Qual o maior ganho que pode ser obtido com esta estratégia?

256256

I

II

III

I I

II

III

I

II

III

II

III

B 0

6

D0

12

E36

8

B 0

6

D 012

E36

8

A 12

C

10

12

E36

8

4

10

54 42 12

60 48 10

78 48 36

5/96

3/64

5/24

3/16

1/4

1

5/96 1/16 1/4 Lucro máximo = 78 probabilidade = 1/3 + 5/96 = 5/288Lucro mínimo = 4

probabilidade = 1/144



ECA

EDB

EDB

,,

257257

• Solução: conjunto de decisões ótimas para cada estágio {decisões ótimas}: estratégia ótima

• Estratégia ótima:

• Lucro/ganho esperado ótimo =

• Maior e menor ganho possíveis com estratégia ótima? Probabilidadaes?

7.355.40313.35

312.31

31


Como joga um jogador que se considera

258258

1. Completamente azarado ?(conservador)

2. Completamente sortudo ?(arriscado)

Documents

Parte 3 Técnicas de projeto de algoritmos. Setembro 2004Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro2 Divisão e conquista Algoritmos gulosos