2-Introdução à Programação Dinâmica

IA 718 Tópicos em Sistemas Inteligentes

ProfFernandoGomide DCA-FEEC-Unicamp

1. Introdução2. Problema do caminho mínimo3. Solução com programação dinâmica4. Análise de complexidade5. Programação dinâmica forward6. Exemplos

Conteúdo

DCA-FEEC-Unicamp

1-Introdução

� Programação dinâmica– metodologia de otimização

– problemas que requerem decisões sequenciais interelacionadas

– decisão tem um custo imediato e afeta contexto decisões futuras

� Objetivo– como obter a sequência de decisões

– minimização custo total em um número de estágios

– compromisso entre custo imediato e futuro

DCA-FEEC-Unicamp

Processos de decisão multiestágios

� Decisão multiestágios– processo que pode ser desdobrado em um número de etapas

seqüenciais, ou estágios

� Estado– condição do processo num dado estágio é o estado neste estágio

� Decisões– opções que se tem em cada estágio

– cada decisão causa uma transição do estado

DCA-FEEC-Unicamp

� Estratégia (política)– uma seqüência de decisões

– uma decisão para cada estado do processo

� Retorno– custo, benefício, associado a cada estágio de decisão

– pode variar com o estágio e o estado

� Questão– determinar a política ótima (aquela que resulta no melhor retorno)

DCA-FEEC-Unicamp

Princípio de otimalidade de Bellman

Uma estratégia ótima apresenta a propriedade segundo a qual, a despeito das decisões tomadas para se atingir um estado particular num certo estágio, as decisões restantes a partir deste estado devem constituir uma estratégia ótima.

[Richard Bellman, 1957]

A

x1

G

1 n N

x2

DCA-FEEC-Unicamp

Qual é o caminho de menoresfôrço (tempo, custo, dis -tância, etc.) entre q e r ?

• 20 caminhos distinos• 5 adições por caminho• 19 comparações

2-Problema do caminho mínimo

q

r

d

e h

f il

g

k

j mo

n p

1

0

3

4

4

2 4

5 2

7 1 3

1 3

5

2 8 2

2 4 1

5 2 2

c

DCA-FEEC-Unicamp

vi melhor caminho de i até rvq = min {1+ vc , 0 +vd}

vc = min {5 + ve , 4 +vf}vd = min {7 + vf , 3 +vg}………………………..

vl = 5 + vo

vm= min {2 + vo , 8 +vp}vn = 4 + vp

vo = 2vp = 1

vr= 0

q

r

vc

d

e h

f il

g

k

j mo

n p

1

0

3

4

4

2 4

5 2

7 1 3

1 3

5

2 8 2

2 4 1

5 2 2

c

vd

va

3-Solução com programação dinâmica

DCA-FEEC-Unicamp

S estadoPS sucessor de Sno caminho ótimo de Saté r

24 adições9 comparações

q

r

vc

d

e h

f il

g

k

j mo

n p

1

0

3

4

4

2 4

5 2

7 1 3

1 3

5

2 8 2

2 4 1

5 2 2

c

vq=13

Po = r Pp = r

Pl = o Pm= o Pn = p

Ph = l Pi = m Pj = m Pk= n

Pe = i Pf = j Pg = j ou k

Pc = f Pd= g

Pq = c

Estratégia ótima

DCA-FEEC-Unicamp

� Função objetivo (custo, utilidade, etc.): aditivamente separável

� Ambientes estocásticos: sistemas Markovianos

� Enumeração exaustiva: O(|A|n)

– |A| número decisões (ações) em cada estágio (passo)

� Programação dinâmica: O(n|A||S|)

– |S| número de estados possíveis– n: número de estágios

4-Análise de complexidade

DCA-FEEC-Unicamp

5-Programação dinâmica forward

vi melhor caminho de q até i

q

r

vc

d

e h

f il

g

k

j mo

n p

1

0

3

4

4

2 4

5 2

7 1 3

1 3

5

2 8 2

2 4 1

5 2 2

c

vd

va

vr = min {2+ vo , 1 +vp}vo = min {5+ vl , 2 +vm}vm= min {4 + vi , 2 +vj}vl = min {3 + vh , 3 + vi}vn = min {2 + vj , 2 +vk}......................................ve = min {5 + vc}vf = min {4+ vc , 7 +vd}vg = min {3 + vd}

vd = 0vc = 1

vq = 0

DCA-FEEC-Unicamp

6-Exemplos

� Determinístico: caminho mínimo

rjv

Lj,iiI

Lj,ijI

jic

j,iL

Ι

j

j

i

ij

paradeocustomínim

)(quetalnósdeconjnto

)(quetalnósdeconjnto

paradecusto

)(arcosdeconjunto

nósdeconjunto

=

∈∃=

∈∃=

===

−

+ q

1

3

2

r

8

15

3

14

5

10

17

DCA-FEEC-Unicamp

Ii, vcminvminv jijIj

iij

∈∀+←+∈

)}(, {

� Equação de Bellman

� Solução iterativa

0151018264

0151018263

0151018302

015101001001

0100100100100

r321qIteração

custo do caminho a partir do nó

DCA-FEEC-Unicamp

� Algoritmo de Pape

fimsenão1passoentãoSederemover3

defimno}{entãose

entãose

v

2.

detopodonóremover1

candidatosdelista}{

0

i

φ≠∪=∉

=<

+=

∈∀

∈

=

=≠

=

+

C.Cj.

Ci;iCCCi

v̂vvv̂

vcˆ

Ij

CCj.

qC

rj

rjMv

iiii

jij

j

j

� Pape (e Djkstra) são instâncias do algoritmo geral

DCA-FEEC-Unicamp

� Algoritmo geral caminho mínimo

remover nó i da lista de candidatos C

para cada arco (i, j) ∈ L

se vj > vi + cij então

vj = vi + cij

adicionar j àV se j ∉ C

DCA-FEEC-Unicamp

Proposição:sejam v1, v2, ....,vN escalares satisfazendo

vj ≤ vi + cij ∀(i, j) ∈ L

e seja P um caminho iniciando em um nó i1 e terminando em um nó ik. Se

vj = vi + cij para todos arcos (i, j) de P

então P é menor caminho de i1 para ik.

Prova

Somando vj = vi + cij para arcos de P → valor de P = vik – vi1

Somando vj ≤ vi + cij para arcos de P ' → valor de P ' ≥ PLogo, P é o menor caminho.

DCA-FEEC-Unicamp

� Estocástico: atribuição dinâmica

=

=trabalhonodias#

oequipamenttipo

técnicolocalzação

a

a

a

at

3

2

1

Aatat

ta

RR

aA

at#R

∈==

=

)(

devaloresdosconjnto

atributocomécnicos

– atributos de um técnico

– conjunto de todos técnicos

DCA-FEEC-Unicamp

Bbtbt

tb

Bbtbt

tb

DD

tbD

D̂D̂

ttb#D̂

bB

b

∈

∈

==

=

−=

==

)(

instantenoinstaladoseratipooequipamenttotal

)(

serviço)(necessita1eentreinstaladostipoosequipament

devaloresdosconjunto

tipo)ão,(localizaçoequipamentumdeatributos

– demanda serviços técnicos

DCA-FEEC-Unicamp

– decisões

φ

φ

∪∪=

=

=

=∈

=

dDDD

d

D

Dd

D

DH

D

H

H

ecnicot'umcomnada"fazer"decisão

demandap/técncioenviandodecisõesconjnto

particularlocalumrepresenta

casap/técnicoenviandodecisõesconjunto

DCA-FEEC-Unicamp

– impacto decisões nos atributos: função transição

′==δ

=

′

+

contráriocaso0

)(se1)(

)(1

ad,aad,a

d,aaa

tM

ta

tM

t

– indicação das decisões tomadas

Dd,Aatadt

tad

xx

adx

∈∈==

)(

atributotécnicoaplicadaédecisãovezesnúmero

DCA-FEEC-Unicamp

– indicação das decisões tomadas

Dd,Aatdat

tda

cc

adc

∈∈==

)(

atributotécnicoaplicadaédecisãocusto

� Modelo míope

0≥

∈≤

=

∑

∑

∑ ∑

∈

∈

∈ ∈

tad

Dtb

Aatad

Ddtatad

Aa Ddatdatd

x

x

Dd,Dx

Rx.a.s

xcmin

d

t

DCA-FEEC-Unicamp

– Dinâmica do sistema

Db,t

Aatadb,tb,t

Aa Ddadata,t

Dd,D̂xDD

)d,a(xR

ddd∈+−=

′δ=

+∈

+

∈′ ∈′+

∑

∑ ∑

11

1

– Estado do sistema

)( ttt D,RS

DCA-FEEC-Unicamp

� Modelo atribuição dinâmica

))()(( 11 ++∈

γ+= tttttXx

t SEVx,SCminVtt

}0{ ≥∈≤== ∑∑∈∈

tadD

tbAa

tadDd

tatadtt x;Dd,Dx;Rx|xXd

DCA-FEEC-Unicamp

Este material refere-se às notas de aula do curso IA 718 Tópicos em Sistemas Inteligentes da Faculdade de Engenharia Elétrica e de Computação da Unicamp. Não substitui o livro texto, as referências recomendadas e nem as aulas expositivas. Este material não pode ser reproduzido sem autorização prévia dos autores. Quando autorizado, seu uso é exclusivo para atividades de ensino e pesquisa em instituições sem fins lucrativos.

Observação

DCA-FEEC-Unicamp