IA718IntroducaoProgramacaoDinamica_2

Prévia do material em texto

2-Introdução à Programação 
Dinâmica
IA 718 Tópicos em Sistemas Inteligentes
ProfFernandoGomide DCA-FEEC-Unicamp
1. Introdução
2. Problema do caminho mínimo
3. Solução com programação dinâmica
4. Análise de complexidade
5. Programação dinâmica forward
6. 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 menor
esfô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 i l
g
k
j m
o
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é r
vq= 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= 2
vp= 1
vr= 0
q
r
vc
d
e h
f i l
g
k
j m
o
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 estado
PS sucessor de S no caminho ótimo de S até r
24 adições
9 comparações
q
r
vc
d
e h
f i l
g
k
j m
o
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 i l
g
k
j m
o
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= 0
vc = 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 jij
Ij
ii
j
∈∀+←
+∈
)}(, { 
� 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
rjM
v
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 ' ≥ P
Logo, 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
t
M
ta
t
M
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
D
tb
Aa
tad
Dd
tatad
Aa Dd
atdatd
x
x
Dd,Dx
Rx.a.s
xcmin
d
t
DCA-FEEC-Unicamp
– Dinâmica do sistema
D
b,t
Aa
tadb,tb,t
Aa Dd
adata,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 ++
∈
γ+= ttttt
Xx
t SEVx,SCminV
tt
}0{ ≥∈≤== ∑∑
∈∈
tad
D
tb
Aa
tad
Dd
tatadtt x;Dd,Dx;Rx|xX d
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